使用两个队列实现堆栈

之前有人问过类似的问题，但这里的问题与之相反，使用两个队列作为堆栈。 这个问题…

给定两个标准操作（入enqueue ， dequeue ， isempty ， size ）的isempty ，用标准操作（ pop ， push ， isempty ， size ）实现一个栈。

应该有两个版本的解决scheme。

• 版本A ：推送物品时堆叠应该是有效的; 和
• 版本B ：popup一个项目时，堆栈应该是有效的。

我比任何特定的语言实现更感兴趣的algorithm。 不过，我欢迎用我熟悉的语言（ java ， c＃ ， python ， vb ， javascript ， php ）expression的解决scheme。

Answer 1

版本A（高效推送）：

• 推：
  • 排队在队列1中
• stream行：
  • 当队列1的大小大于1时，将队列中的项目从队列1排队到队列2
  • 退出并返回队列1的最后一项，然后切换队列1和队列2的名称

版本B（高效stream行）：

• 推：
  • 排队在队列2中
  • 将队列1中的所有项排入队列2，然后切换队列1和队列2的名称
• stream行：
  • 队列1的请求

Answer 2

最简单的（也许是唯一的）这样做的方法是将新元素推入空队列，然后将其他队列出队，然后进入先前的空队列。 用这种方式，最新的总是在队列的前面。 这将是版本B，对于版本A，您只需通过将元素出队到第二个队列（除最后一个队列之外）来逆转进程。

第0步：

 "Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

步骤1：

 "Stack" +---+---+---+---+---+ | 1 | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

第2步：

 "Stack" +---+---+---+---+---+ | 2 | 1 | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | 2 | 1 | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

第3步：

 "Stack" +---+---+---+---+---+ | 3 | 2 | 1 | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 3 | 2 | 1 | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

Answer 3

我们可以用一个队列来做到这一点：

推：

1. 排队新的元素。
2. 如果n是队列中元素的数量，则删除并插入元素n-1次。

stream行：

1. 出队

。

 push 1 front +----+----+----+----+----+----+ | 1 | | | | | | insert 1 +----+----+----+----+----+----+ push2 front +----+----+----+----+----+----+ | 1 | 2 | | | | | insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | 2 | 1 | | | | remove and insert 1 +----+----+----+----+----+----+ insert 3 front +----+----+----+----+----+----+ | | 2 | 1 | 3 | | | insert 3 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | 1 | 3 | 2 | | remove and insert 2 +----+----+----+----+----+----+ front +----+----+----+----+----+----+ | | | | 3 | 2 | 1 | remove and insert 1 +----+----+----+----+----+----+ 

示例实现：

 int stack_pop (queue_data *q) { return queue_remove (q); } void stack_push (queue_data *q, int val) { int old_count = queue_get_element_count (q), i; queue_insert (q, val); for (i=0; i<old_count; i++) { queue_insert (q, queue_remove (q)); } } 

Answer 4

 import java.util.*; /** * * @author Mahmood */ public class StackImplUsingQueues { Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); public int pop() { if (q1.peek() == null) { System.out.println("The stack is empty, nothing to return"); int i = 0; return i; } else { int pop = q1.remove(); return pop; } } public void push(int data) { if (q1.peek() == null) { q1.add(data); } else { for (int i = q1.size(); i > 0; i--) { q2.add(q1.remove()); } q1.add(data); for (int j = q2.size(); j > 0; j--) { q1.add(q2.remove()); } } } public static void main(String[] args) { StackImplUsingQueues s1 = new StackImplUsingQueues(); // Stack s1 = new Stack(); s1.push(1); s1.push(2); s1.push(3); s1.push(4); s1.push(5); s1.push(6); s1.push(7); s1.push(8); s1.push(9); s1.push(10); // s1.push(6); System.out.println("1st = " + s1.pop()); System.out.println("2nd = " + s1.pop()); System.out.println("3rd = " + s1.pop()); System.out.println("4th = " + s1.pop()); System.out.println("5th = " + s1.pop()); System.out.println("6th = " + s1.pop()); System.out.println("7th = " + s1.pop()); System.out.println("8th = " + s1.pop()); System.out.println("9th = " + s1.pop()); System.out.println("10th= " + s1.pop()); } } 

Answer 5

我们可以用一个队列来实现一个堆栈吗？ 我可以使用两个队列，但考虑单个队列会更有效率。 这里是代码：

  public void Push(T val) { queLower.Enqueue(val); } public T Pop() { if (queLower.Count == 0 ) { Console.Write("Stack is empty!"); return default(T); } if (queLower.Count > 0) { for (int i = 0; i < queLower.Count - 1;i++ ) { queLower.Enqueue(queLower.Dequeue ()); } } return queLower.Dequeue(); } 

Answer 6

 queue<int> q1, q2; int i = 0; void push(int v) { if( q1.empty() && q2.empty() ) { q1.push(v); i = 0; } else { if( i == 0 ) { while( !q1.empty() ) q2.push(q1.pop()); q1.push(v); i = 1-i; } else { while( !q2.empty() ) q1.push(q2.pop()); q2.push(v); i = 1-i; } } } int pop() { if( q1.empty() && q2.empty() ) return -1; if( i == 1 ) { if( !q1.empty() ) return q1.pop(); else if( !q2.empty() ) return q2.pop(); } else { if( !q2.empty() ) return q2.pop(); else if( !q1.empty() ) return q1.pop(); } } 

Answer 7

这是我的答案 – “stream行”效率低下。 似乎所有立刻想到的algorithm都具有N个复杂度，其中N是列表的大小：您是select在“stream行”上工作，还是在“推”

列表返回和第四的algorithm可能会更好，因为不需要计算大小，尽pipe您仍然需要循环和比较空白。

你可以certificate这个algorithm不能写得比N快，因为有关队列中最后一个元素的信息只有通过知道队列的大小才可用，并且你必须销毁数据才能到达那个元素，因此第二个队列。

增加速度的唯一方法就是不要首先使用队列。

 from data_structures import queue class stack(object): def __init__(self): q1= queue q2= queue #only contains one item at most. a temp var. (bad?) def push(self, item): q1.enque(item) #just stick it in the first queue. #Pop is inefficient def pop(self): #'spin' the queues until q1 is ready to pop the right value. for N 0 to self.size-1 q2.enqueue(q1.dequeue) q1.enqueue(q2.dequeue) return q1.dequeue() @property def size(self): return q1.size + q2.size @property def isempty(self): if self.size > 0: return True else return False 

Answer 8

一般情况下，我的解决scheme适用于O（1）。 有两个队列： out 。 看伪代码：

 PUSH(X) = in.enqueue(X) POP: X = if (out.isEmpty and !in.isEmpty) DUMP(in, out) return out.dequeue DUMP(A, B) = if (!A.isEmpty) x = A.dequeue() DUMP(A, B) B.enqueue(x) 

Answer 9

正如已经提到的，是不是一个队列就可以做到这一点？ 这可能不太实际，但有点滑。

 push(x): enqueue(x) for(queueSize - 1) enqueue(dequeue()) pop(x): dequeue() 

Answer 10

这里是一些简单的伪代码，push是O（n），pop / peek是O（1）：

 Qpush = Qinstance() Qpop = Qinstance() def stack.push(item): Qpush.add(item) while Qpop.peek() != null: //transfer Qpop into Qpush Qpush.add(Qpop.remove()) swap = Qpush Qpush = Qpop Qpop = swap def stack.pop(): return Qpop.remove() def stack.peek(): return Qpop.peek() 

Answer 11

让S1和S2是用于实现队列的两个堆栈。

 struct Stack { struct Queue *Q1; struct Queue *Q2; } 

我们确保一个队列总是空的。

推送操作：无论队列是否为空，都插入该元素。

• 检查队列Q1是否为空。 如果Q1为空，则将其中的元素排入队列。
• 否则将元素放入Q1。

Push (struct Stack *S, int data) { if(isEmptyQueue(S->Q1) EnQueue(S->Q2, data); else EnQueue(S->Q1, data); }

时间复杂度：O（1）

popup操作：将n-1个元素传送到其他队列，并从队列中删除最后一个，以执行popup操作。

• 如果队列Q1不是空的，那么从Q1到Q2传输n-1个元素，然后对Q1的最后一个元素进行DeQue并返回。
• 如果队列Q2不为空，则将Q2中的n-1个元素传输到Q1，然后对Q2的最后一个元素进行DeQueue并返回。

`

 int Pop(struct Stack *S){ int i, size; if(IsEmptyQueue(S->Q2)) { size=size(S->Q1); i=0; while(i<size-1) { EnQueue(S->Q2, Dequeue(S->Q1)) ; i++; } return DeQueue(S->Q1); } else{ size=size(S->Q2); while(i<size-1) EnQueue(S->Q1, Dequeue(S->Q2)) ; i++; } return DeQueue(S->Q2); } } 

时间复杂度：pop操作的运行时间是O（n），因为每次调用pop时，我们将所有的元素从一个队列转移到另一个队列。

Answer 12

 Q1 = [10, 15, 20, 25, 30] Q2 = [] exp: { dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25] now Q1 dequeue gives "30" that inserted last and working as stack } swap Q1 and Q2 then GOTO exp 

Answer 13

 import java.util.LinkedList; import java.util.Queue; class MyStack { Queue<Integer> queue1 = new LinkedList<Integer>(); Queue<Integer> queue2 = new LinkedList<Integer>(); // Push element x onto stack. public void push(int x) { if(isEmpty()){ queue1.offer(x); }else{ if(queue1.size()>0){ queue2.offer(x); int size = queue1.size(); while(size>0){ queue2.offer(queue1.poll()); size--; } }else if(queue2.size()>0){ queue1.offer(x); int size = queue2.size(); while(size>0){ queue1.offer(queue2.poll()); size--; } } } } // Removes the element on top of the stack. public void pop() { if(queue1.size()>0){ queue1.poll(); }else if(queue2.size()>0){ queue2.poll(); } } // Get the top element. You can make it more perfect just example public int top() { if(queue1.size()>0){ return queue1.peek(); }else if(queue2.size()>0){ return queue2.peek(); } return 0; } // Return whether the stack is empty. public boolean isEmpty() { return queue1.isEmpty() && queue2.isEmpty(); } } 

Answer 14

这里还有一个解决scheme：

对于PUSH： – 在队列1中添加第一个元素。 – 当添加第二个元素等时，首先将队列2中的元素排入队列，然后将队列1中的所有元素复制到队列2。 对于POP只是从插入最后一个元素的队列中取出元素。

所以，

 public void push(int data){ if (queue1.isEmpty()){ queue1.enqueue(data); } else { queue2.enqueue(data); while(!queue1.isEmpty()) Queue2.enqueue(queue1.dequeue()); //EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2 

}}

 public int pop(){ int popItem=queue2.dequeue(); return popItem; }' 

有一个问题，我无法弄清楚，如何重新命名队列？

Answer 15

 #include <bits/stdc++.h> using namespace std; queue<int>Q; stack<int>Stk; void PRINT(stack<int>ss , queue<int>qq) { while( ss.size() ) { cout << ss.top() << " " ; ss.pop(); } puts(""); while( qq.size() ) { cout << qq.front() << " " ; qq.pop(); } puts("\n----------------------------------"); } void POP() { queue<int>Tmp ; while( Q.size() > 1 ) { Tmp.push( Q.front() ); Q.pop(); } cout << Q.front() << " " << Stk.top() << endl; Q.pop() , Stk.pop() ; Q = Tmp ; } void PUSH(int x ) { Q.push(x); Stk.push(x); } int main() { while( true ) { string typ ; cin >> typ ; if( typ == "push" ) { int x ; cin >> x; PUSH(x); } else POP(); PRINT(Stk,Q); } } 

Answer 16

Python代码只使用一个队列

  class Queue(object): def __init__(self): self.items=[] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): if(not self.isEmpty()): return self.items.pop() def isEmpty(self): return self.items==[] def size(self): return len(self.items) class stack(object): def __init__(self): self.q1= Queue() def push(self, item): self.q1.enqueue(item) def pop(self): c=self.q1.size() while(c>1): self.q1.enqueue(self.q1.dequeue()) c-=1 return self.q1.dequeue() def size(self): return self.q1.size() def isempty(self): if self.size > 0: return True else: return False 

Answer 17

这里是完整的工作代码在C＃中：

它已经实现了单队列，

推：

 1. add new element. 2. Remove elements from Queue (totalsize-1) times and add back to the Queue 

stream行：

 normal remove using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace StackImplimentationUsingQueue { class Program { public class Node { public int data; public Node link; } public class Queue { public Node rear; public Node front; public int size = 0; public void EnQueue(int data) { Node n = new Node(); n.data = data; n.link = null; if (rear == null) front = rear = n; else { rear.link = n; rear = n; } size++; Display(); } public Node DeQueue() { Node temp = new Node(); if (front == null) Console.WriteLine("Empty"); else { temp = front; front = front.link; size--; } Display(); return temp; } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node n = front; while (n != null) { Console.WriteLine(n.data); n = n.link; } } } } public class Stack { public Queue q; public int size = 0; public Node top; public Stack() { q = new Queue(); } public void Push(int data) { Node n = new Node(); n.data = data; q.EnQueue(data); size++; int counter = size; while (counter > 1) { q.EnQueue(q.DeQueue().data); counter--; } } public void Pop() { q.DeQueue(); size--; } } static void Main(string[] args) { Stack s= new Stack(); for (int i = 1; i <= 3; i++) s.Push(i); for (int i = 1; i < 3; i++) s.Pop(); Console.ReadKey(); } } } 

Answer 18

这里是我的Java代码，使用队列进行堆栈实现。

  import java.util.LinkedList; import java.util.Queue; /* @Rishabh Sairawat */ public class StackImplementationiUsingQueue { Queue<Integer> q1=new LinkedList<Integer>(); Queue<Integer> q2=new LinkedList<Integer>(); //push operation public void push(int data){ this.q1.add(data); } //pop operation public int pop(){ if(this.q1.isEmpty()){ System.out.println("No Element found !"); } else { int x; while(this.q1.size()>1){ x=this.q1.remove(); this.q2.add(x); } x=q1.remove(); this.q1.addAll(q2); return x; } return -1; } public static void main(String[] args) { StackImplementationiUsingQueue stack=new StackImplementationiUsingQueue(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); } 

}

Answer 19

这是非常简单的解决scheme，它使用一个队列，并提供function，如堆栈。

 public class CustomStack<T> { Queue<T> que = new Queue<T>(); public void push(T t) // STACK = LIFO / QUEUE = FIFO { if( que.Count == 0) { que.Enqueue(t); } else { que.Enqueue(t); for (int i = 0; i < que.Count-1; i++) { var data = que.Dequeue(); que.Enqueue(data); } } } public void pop() { Console.WriteLine("\nStack Implementation:"); foreach (var item in que) { Console.Write("\n" + item.ToString() + "\t"); } var data = que.Dequeue(); Console.Write("\n Dequeing :" + data); } public void top() { Console.Write("\n Top :" + que.Peek()); } } 

所以在上面这个名为“CustomStack”的类中，我所做的只是检查队列中是否为空，如果为空则插入一个，然后再插入，然后删除插入。 通过这个逻辑首先会最后。 例如：在队列中，我插入1，现在试图插入2.第二次删除1，然后再次插入，所以它变成了相反的顺序。

谢谢。

Answer 20

这是我的解决scheme..

Concept_Behind :: push(struct Stack* S,int data) ::此函数在Q1中排队第一个元素，并在Q2中restpop(struct Stack* S) ::如果Q2不为空，则将所有元素转换为Q1并返回最后一个第二季度的元素（这意味着Q2是空的）将所有元素转换为Q2并返回Q1中的最后一个元素

Efficiency_Behind :: push(struct Stack*S,int data) :: O（1）//因为每个数据的单个排队pop(struct Stack* S) :: O（n）//因为传输最差每个stream行的n-1个数据。

 #include<stdio.h> #include<stdlib.h> struct Queue{ int front; int rear; int *arr; int size; }; struct Stack { struct Queue *Q1; struct Queue *Q2; }; struct Queue* Qconstructor(int capacity) { struct Queue *Q=malloc(sizeof(struct Queue)); Q->front=Q->rear=-1; Q->size=capacity; Q->arr=malloc(Q->size*sizeof(int)); return Q; } int isEmptyQueue(struct Queue *Q) { return (Q->front==-1); } int isFullQueue(struct Queue *Q) { return ((Q->rear+1) % Q->size ==Q->front); } void enqueue(struct Queue *Q,int data) { if(isFullQueue(Q)) { printf("Queue overflow\n"); return;} Q->rear=Q->rear+1 % Q->size; Q->arr[Q->rear]=data; if(Q->front==-1) Q->front=Q->rear; } int dequeue(struct Queue *Q) { if(isEmptyQueue(Q)){ printf("Queue underflow\n"); return; } int data=Q->arr[Q->front]; if(Q->front==Q->rear) Q->front=-1; else Q->front=Q->front+1 % Q->size; return data; } ///////////////////////*************main algo****************//////////////////////// struct Stack* Sconstructor(int capacity) { struct Stack *S=malloc(sizeof(struct Stack)); S->Q1=Qconstructor(capacity); S->Q2=Qconstructor(capacity); return S; } void push(struct Stack *S,int data) { if(isEmptyQueue(S->Q1)) enqueue(S->Q1,data); else enqueue(S->Q2,data); } int pop(struct Stack *S) { int i,tmp; if(!isEmptyQueue(S->Q2)){ for(i=S->Q2->front;i<=S->Q2->rear;i++){ tmp=dequeue(S->Q2); if(isEmptyQueue(S->Q2)) return tmp; else enqueue(S->Q1,tmp); } } else{ for(i=S->Q1->front;i<=S->Q1->rear;i++){ tmp=dequeue(S->Q1); if(isEmptyQueue(S->Q1)) return tmp; else enqueue(S->Q2,tmp); } } } ////////////////*************end of main algo my algo************ ///////////////*************push() O(1);;;;pop() O(n);;;;*******///// main() { int size; printf("Enter the number of elements in the Stack(made of 2 queue's)::\n"); scanf("%d",&size); struct Stack *S=Sconstructor(size); push(S,1); push(S,2); push(S,3); push(S,4); printf("%d\n",pop(S)); push(S,5); printf("%d\n",pop(S)); printf("%d\n",pop(S)); printf("%d\n",pop(S)); printf("%d\n",pop(S)); } 

Answer 21

 import java.util.LinkedList; import java.util.Queue; public class StackQueue { static Queue<Integer> Q1 = new LinkedList<Integer>(); static Queue<Integer> Q2 = new LinkedList<Integer>(); public static void main(String args[]) { push(24); push(34); push(4); push(10); push(1); push(43); push(21); System.out.println("Popped element is "+pop()); System.out.println("Popped element is "+pop()); System.out.println("Popped element is "+pop()); } public static void push(int data) { Q1.add(data); } public static int pop() { if(Q1.isEmpty()) { System.out.println("Cannot pop elements , Stack is Empty !!"); return -1; } else { while(Q1.size() > 1) { Q2.add(Q1.remove()); } int element = Q1.remove(); Queue<Integer> temp = new LinkedList<Integer>(); temp = Q1; Q1 = Q2; Q2 = temp; return element; } } } 

Answer 22

 #include "stdio.h" #include "stdlib.h" typedef struct { int *q; int size; int front; int rear; } Queue; typedef struct { Queue *q1; Queue *q2; } Stack; int queueIsEmpty(Queue *q) { if (q->front == -1 && q->rear == -1) { printf("\nQUEUE is EMPTY\n"); return 1; } return 0; } int queueIsFull(Queue *q) { if (q->rear == q->size-1) { return 1; } return 0; } int queueTop(Queue *q) { if (queueIsEmpty(q)) { return -1; } return q->q[q->front]; } int queuePop(Queue *q) { if (queueIsEmpty(q)) { return -1; } int item = q->q[q->front]; if (q->front == q->rear) { q->front = q->rear = -1; } else { q->front++; } return item; } void queuePush(Queue *q, int val) { if (queueIsFull(q)) { printf("\nQUEUE is FULL\n"); return; } if (queueIsEmpty(q)) { q->front++; q->rear++; } else { q->rear++; } q->q[q->rear] = val; } Queue *queueCreate(int maxSize) { Queue *q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = -1; q->size = maxSize; q->q = (int*)malloc(sizeof(int)*maxSize); return q; } /* Create a stack */ void stackCreate(Stack *stack, int maxSize) { Stack **s = (Stack**) stack; *s = (Stack*)malloc(sizeof(Stack)); (*s)->q1 = queueCreate(maxSize); (*s)->q2 = queueCreate(maxSize); } /* Push element x onto stack */ void stackPush(Stack *stack, int element) { Stack **s = (Stack**) stack; queuePush((*s)->q2, element); while (!queueIsEmpty((*s)->q1)) { int item = queuePop((*s)->q1); queuePush((*s)->q2, item); } Queue *tmp = (*s)->q1; (*s)->q1 = (*s)->q2; (*s)->q2 = tmp; } /* Removes the element on top of the stack */ void stackPop(Stack *stack) { Stack **s = (Stack**) stack; queuePop((*s)->q1); } /* Get the top element */ int stackTop(Stack *stack) { Stack **s = (Stack**) stack; if (!queueIsEmpty((*s)->q1)) { return queueTop((*s)->q1); } return -1; } /* Return whether the stack is empty */ bool stackEmpty(Stack *stack) { Stack **s = (Stack**) stack; if (queueIsEmpty((*s)->q1)) { return true; } return false; } /* Destroy the stack */ void stackDestroy(Stack *stack) { Stack **s = (Stack**) stack; free((*s)->q1); free((*s)->q2); free((*s)); } int main() { Stack *s = NULL; stackCreate((Stack*)&s, 10); stackPush((Stack*)&s, 44); //stackPop((Stack*)&s); printf("\n%d", stackTop((Stack*)&s)); stackDestroy((Stack*)&s); return 0; }