如何使用兩個堆棧實現隊列
Stack and Queue at a glance...
堆疊和排隊一目了然...
Stack:
堆棧：
The stack is an ordered list where insertion and deletion are done from the same end, top. The last element that entered first is the first one to be deleted (the basic principle behind the LIFO). That means it is a data structure which is implemented as LIFO.
堆棧是一個有序列表，其中插入和刪除從同一末端開始。 首先輸入的最后一個元素是要刪除的第一個元素(LIFO的基本原理)。 這意味著它是一個實現為LIFO的數據結構。
The main stack operations are (basic ADT operations)...
主堆棧操作為(基本ADT操作)...
push (int data): Insertion at top
push(int數據)：在頂部插入
int pop(): Deletion from top
int pop()：從頂部刪除
Queue:
隊列：
The queue is an ordered list in which insertions are done at one end (rear) and deletions are done from another end (front). The first element that got inserted is the first one to be deleted (basic principle of FIFO). That means it is a data structure which is implemented as FIFO.
隊列是一個有序列表，其中插入是在一端(后部)完成，而刪除是從另一端(前部)完成。 插入的第一個元素是要刪除的第一個元素(FIFO的基本原理)。 這意味著它是一個實現為FIFO的數據結構。
The main Queue operations are (basic ADT operations)...
主要的Queue操作是(基本ADT操作)...
EnQueue (int data): Insertion at rear end
EnQueue(int數據)：在后端插入
int DeQueue(): Deletion from front end
int DeQueue()：從前端刪除
使用兩個隊列實現堆棧 (Implementation of a stack using two queues)
Likewise, a queue can be implemented with two stacks, a stack can also be implemented using two queues. The basic idea is to perform stack ADT operations using the two queues.
同樣，一個隊列可以用兩個堆棧實現，一個堆棧也可以用兩個隊列實現。 基本思想是使用兩個隊列執行堆棧ADT操作。
So, we need to implement push(),pop() using DeQueue(), EnQueue() operations available for the queues.
因此，我們需要使用隊列可用的DeQueue()和EnQueue()操作來實現push()，pop()。
Implementation:
實現方式：
Let q1 and q2 be the two queues...
設q1和q2為兩個隊列...
struct stack{
struct queue *q1;
struct queue *q2;
}
Algorithm to implement push and pop:
實現推送和彈出的算法：
Push operation algorithm:
推送操作算法：
Check whether q1 is empty or not. If q1 is empty then EnQueue the element to q2.
檢查q1是否為空。 如果q1為空，則將元素排隊到q2。
Otherwise EnQueue to q1.
否則，排隊到q1。
push(struct stack *s,int data){
if(isempty(s->q1))
EnQueue(s->q2,data);
else
EnQueue(s->q1,data);
}
Pop operation algorithm
彈出操作算法
The basic idea is to transfer n-1 elements (let n be the total no of elements) to other queue and delete the last one from a queue to perform the pop operation.
基本思想是將n-1個元素(使n為元素總數)轉移到其他隊列，并從隊列中刪除最后一個元素以執行彈出操作。
If q1 is not empty then transfer n-1 elements from q1 to q2 and DeQueue the last element and return it.
如果q1不為空，則將n-1個元素從q1傳輸到q2，并對最后一個元素進行DeQueue并返回。
If q2 is not empty then transfer n-1 elements from q2 to q1 and DeQueue the last element and return it.
如果q2不為空，則將n-1個元素從q2傳輸到q1，并對最后一個元素進行DeQueue并返回。
int pop(struct stack *s){
int count,size;
if(isempty(s->q2)){
size=Size(s->q1);
count=0;
while(count<size-1){
//transferring n-1 elements
EnQueue(s->q2,DeQueue(s->q1));
count++;
}
//last element to be popped
return DeQueue(s->q1);
}
else{
size=Size(s->q2);
count=0;
while(count<size-1){
EnQueue(s->q1,DeQueue(s->q2));
count++;
}
return DeQueue(s->q1);
}
}
Time complexity analysis:
時間復雜度分析：
Push: O(1)
推：O(1)
Pop: O(n) , since transferring n-1 elements
彈出：O(n)，因為傳輸了n-1個元素
使用C ++的實現代碼(使用STL) (Implementation code using C++ (using STL))
#include <bits/stdc++.h>
using namespace std;
struct Stack{
queue<int> q1,q2;
void push(int x){
if(q1.empty()){
q2.push(x); //EnQueue operation using STL
}
else{
q1.push(x); //EnQueue operation using STL
}
}
int pop(){
int count,size,item;
if(q2.empty()){
size=q1.size(); //size=no of elements;
count=0;
while(count<size-1){ //transfering n-1 elements
q2.push(q1.front()); // DeQueue operation using STL
q1.pop();
count++;
}
item=q1.front();
q1.pop();
return item; //popping out the element
}
else{
size=q2.size();
count=0;
while(count<size-1){
q1.push(q2.front());
q2.pop();
count++;
}
item=q2.front();
q2.pop();
return item;
}
}
};
int main()
{
cout<<"implementing stack with two queues"<<endl;
cout<<"enter any integer to push and 0 to stop pushing"<<endl;
Stack s;
int x,count=0;
cin>>x;
while(x){
s.push(x);
cin>>x;
count++;
}
cout<<"now popping......."<<endl;
while(count){
cout<<s.pop()<<endl;
count--;
}
cout<<"executed successfully!!!"<<endl;
return 0;
}
Output
輸出量
implementing stack with two queues
enter any integer to push and 0 to stop pushing
1
2
3
0
now popping.......
3
2
1
executed successfully!!!
翻譯自: https://www.includehelp.com/data-structure-tutorial/implementation-of-stack-using-two-queues.aspx
如何使用兩個堆棧實現隊列
