使用两个队列实现堆栈

小开

最佳答案

版本 A (有效推动) :

推:
- 在队列1中排队
- 当队列1的大小大于1时，将排队项从队列1导入队列2
- Dequeue 并返回 queue e1的最后一项，然后切换 queue e1和 queue e2的名称

版本 B (高效流行音乐) :

推:
- 在队列2中排队
- 在队列2中对队列1的所有项进行排队，然后切换队列1和队列2的名称
- 从队列1开始

小开

最简单(也许是唯一)的方法是将新元素推入空队列，然后将另一个元素排队，并对先前的空队列进行排队。这样，最新的总是排在队伍的前面。这将是版本 B，对于版本 A，您只需通过将元素排队到除最后一个队列之外的第二个队列中来逆转该过程。

第0步:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+


Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

第一步:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+


Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

第二步:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+


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

第三步:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+


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

小开

这就是我的答案——“砰”的效率低下的地方。似乎所有立即浮现在脑海中的算法都有 N 个复杂度，其中 N 是列表的大小: 无论你选择在“弹出”上做工作还是在“推”上做工作

将列表反向交易和排名第四的算法可能更好, 因为不需要计算大小，尽管仍然需要循环并与空值进行比较。

你可以证明这个算法不可能比 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

小开

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());
}
}

小开

正如前面提到的，单个队列不就可以了吗? 它可能不太实用，但是有点滑。

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


pop(x):
dequeue()

小开

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();
}
}

小开

我们可以只使用一个队列来实现一个堆栈吗？我可以使用两个队列，但是考虑单个队列会更有效率。密码如下:

    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();


}

小开

我们可以用一个队列来完成:

推:

对新元素进行排队。
如果 n是队列中的元素数，那么删除并插入元素 n-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));
}
}

小开

还有一个办法:

推动: - 在队列1中添加第一个元素。 - 当添加第二个元素等等时, 首先对队列2中的元素进行排队，然后将队列1中的所有元素复制到队列2中。 - for 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;
}'

有一个问题，我不能弄清楚，如何重命名队列? ? ？

小开

下面是我的解决方案，它适用于平均情况下的 O (1)。有两个队列: in和 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)

小开

下面是一些简单的伪代码，push 是 O (n) ，pop/eek 是 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()

小开

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

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

我们确保一个队列始终为空。

推送操作: 无论哪个队列不是空的，都在其中插入元素。

检查队列 Q1是否为空。如果 Q1为空，则对其中的元素进行排队。
否则将元素排队到 Q1中。

Push (struct Stack * S，int data) { If (isEmptyQueue (S-> Q1) 排队(S-> Q2，数据) ; Else EnQueue (S-> Q1，data) ; }

时间复杂度: O (1)

Pop Operation: 将 n-1元素转移到其他队列并从队列中删除 last，以执行 Pop 操作。

如果队列 Q1不是空的，那么将 n-1元素从 Q1传递到 Q2，然后，DeQueue 将 Q1的最后一个元素返回。
如果队列 Q2不是空的，那么将 n-1元素从 Q2传递到 Q1，然后，DeQueue 将 Q2的最后一个元素返回。

`

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 时，pop 操作的运行时间为 O (n) ，我们将所有元素从一个队列传输到另一个队列。

小开

#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);
}
}

小开

这是我的解决办法。

概念背后: push(struct Stack* S,int data): : 这个函数在 Q1中排列第一个元素，在 Q2中休止如果 Q2不为空，则将所有元素转移到 Q1并返回 Q2中的最后一个元素 Else (这意味着 Q2是空的)将所有元素转移到 Q2并返回 Q1中的最后一个元素

效率: push(struct Stack*S,int data): : O (1)//因为每个数据只有一个队列 pop(struct Stack* S): : O (n)//因为每次弹出传输最差的 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));
}

小开

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;
}
}
}

小开

#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;
}

小开

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

小开

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();
}
}

小开

只使用一个队列的 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

小开

下面是 c # 中的完整工作代码:

它是通过单队列实现的,

推:

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

流行音乐:

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();
}
}
}

小开

这是一个非常简单的解决方案，它使用一个 Queue 并提供类似 Stack 的功能。

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，再次插入，使其成为反向顺序。

谢谢你。

小开

下面是一个非常简单的 Java 解决方案，它支持高效的 push 操作。

算法 -

声明两个 Queue q1和 q2。
Push operation-Enqueue element to queue q1.
弹出操作-确保队列 q2不为空。如果为空, 然后从 q1中取出所有元素，除了最后一个元素和将它一个一个地排队到 q2。从 q1中取出最后一个元素，然后存储为弹出元素。交换队列 q1和 q2。返回存储的弹出元素
查看操作-确保队列 q2不是空的。如果它是空的, 然后从 q1中取出所有元素，除了最后一个元素和将它一个一个地排队到 q2。从 q1中取出最后一个元素，然后将其作为窥视元素存储。将其排队返回到队列 q2并进行交换队列 q1和 q2。返回存储的窥视元素。

下面是上述算法的代码-

class MyStack {


java.util.Queue<Integer> q1;
java.util.Queue<Integer> q2;
int SIZE = 0;


/** Initialize your data structure here. */
public MyStack() {
q1 = new LinkedList<Integer>();
q2 = new LinkedList<Integer>();


}


/** Push element x onto stack. */
public void push(int x) {
q1.add(x);
SIZE ++;


}


/** Removes the element on top of the stack and returns that element. */
public int pop() {
ensureQ2IsNotEmpty();
int poppedEle = q1.remove();
SIZE--;
swapQueues();
return poppedEle;
}


/** Get the top element. */
public int top() {
ensureQ2IsNotEmpty();
int peekedEle = q1.remove();
q2.add(peekedEle);
swapQueues();
return peekedEle;
}


/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();


}


/** move all elements from q1 to q2 except last element */
public void ensureQ2IsNotEmpty() {
for(int i=0; i<SIZE-1; i++) {
q2.add(q1.remove());
}
}


/** Swap queues q1 and q2 */
public void swapQueues() {
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
}

小开

C # 中的高效解决方案

public class MyStack {
private Queue<int> q1 = new Queue<int>();
private Queue<int> q2 = new Queue<int>();
private int count = 0;


/**
* Initialize your data structure here.
*/
public MyStack() {
}


/**
* Push element x onto stack.
*/
public void Push(int x) {
count++;
q1.Enqueue(x);
while (q2.Count > 0) {
q1.Enqueue(q2.Peek());
q2.Dequeue();
}
var temp = q1;
q1 = q2;
q2 = temp;
}


/**
* Removes the element on top of the stack and returns that element.
*/
public int Pop() {
count--;
return q2.Dequeue();
}


/**
* Get the top element.
*/
public int Top() {
return q2.Peek();
}


/**
* Returns whether the stack is empty.
*/
public bool Empty() {
if (count > 0) return false;
return true;
}
}

小开

template <typename T>
class stackfmtoq {
queue<T> q1;
queue<T> q2;
public:
void push(T data) {
while (!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
q2.push(data);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
}
T pop() {
if (q2.empty()) {
cout << "Stack is Empty\n";
return NULL;
}
T ret = q2.front();
q2.pop();
return ret;
}
T top() {
if (q2.empty()) return NULL;
return q2.front();
}
};

小开

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;


public class ImplementationOfStackUsingTwoQueue {


private static Deque<Integer> inboxQueue = new LinkedList<>();
private static Queue<Integer> outboxQueue = new LinkedList<>();
    

public void pushInStack(Integer val){
inboxQueue.add(val);
}
    

public void popFromStack(){
        

if(outboxQueue.isEmpty()){
while(!inboxQueue.isEmpty()){
outboxQueue.add(inboxQueue.pollLast());
}
}
}
    

public static void main(String[] args) {
        

ImplementationOfStackUsingTwoQueue obj = new ImplementationOfStackUsingTwoQueue();
        

obj.pushInStack(1);
obj.pushInStack(2);
obj.pushInStack(3);
obj.pushInStack(4);
obj.pushInStack(5);
System.out.println("After pushing the values in Queue" + inboxQueue);
        

obj.popFromStack();
System.out.println("After popping the values from Queue" + outboxQueue);
}
}

小开

一种易于理解和执行的不同方法可以是:

添加操作—— > 总是在空队列中添加元素，并在添加该元素后将其他非空队列中的所有元素移动到此队列中。
弹出操作—— > 哪个队列不是空的，就对其执行删除/轮询并返回。
Top 操作—— > 不管哪个队列不是空的，都可以查看并返回。
打印—— > 不管哪个队列不是空的，都打印它。