小开

不过，时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。

编辑

不知道为什么我的答案在这里被否决了。如果我们编程，我们会关心时间复杂度，使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票，我很想知道为什么。

再详细一点:关于为什么使用两个堆栈比只有一个队列更糟糕:如果你使用两个堆栈，并且有人在发件箱是空的时候调用dequeue，你需要线性时间来到达收件箱的底部(正如你可以在Dave的代码中看到的那样)。

您可以将队列实现为单链表(每个元素指向下一个插入的元素)，保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易，只需常数时间即可完成。这是最坏情况的常数时间，不是平摊。而且，正如注释中要求澄清的那样，最坏情况下常数时间严格来说比平摊常数时间要好。

小开

您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。

小开

保留两个堆栈，我们称它们为inbox和outbox。

排队:

将新元素推入inbox

出列:

如果outbox为空，则通过弹出inbox中的每个元素并将其推入outbox来重新填充它

弹出并返回outbox中的顶部元素

使用这种方法，每个元素只在每个堆栈中存在一次——这意味着每个元素将被压入两次，弹出两次，从而给出平摊常数时间操作。

下面是Java中的实现:

public class Queue<E>
{


private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();


public void queue(E item) {
inbox.push(item);
}


public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}


}

小开

您甚至可以只使用一个堆栈模拟一个队列。第二个(临时)堆栈可以通过对insert方法的递归调用的调用堆栈来模拟。

在队列中插入新元素时，原理保持不变:

您需要将元素从一个堆栈转移到另一个临时堆栈，以反转它们的顺序。
然后将要插入的新元素推入临时堆栈
然后将元素转移回原始堆栈
新元素将在堆栈的底部，而最老的元素在顶部(第一个被弹出)

一个Queue类只使用一个Stack，如下所示:

public class SimulatedQueue<E> {
private java.util.Stack<E> stack = new java.util.Stack<E>();


public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}


public E remove() {
return stack.pop();
}
}

小开

public class QueueUsingStacks<T>
{
private LinkedListStack<T> stack1;
private LinkedListStack<T> stack2;


public QueueUsingStacks()
{
stack1=new LinkedListStack<T>();
stack2 = new LinkedListStack<T>();


}
public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
{
while(source.Head!=null)
{
dest.Push(source.Head.Data);
source.Head = source.Head.Next;
}
}
public void Enqueue(T entry)
{


stack1.Push(entry);
}
public T Dequeue()
{
T obj;
if (stack2 != null)
{
Copy(stack1, stack2);
obj = stack2.Pop();
Copy(stack2, stack1);
}
else
{
throw new Exception("Stack is empty");
}
return obj;
}


public void Display()
{
stack1.Display();
}




}

对于每一个入队列操作，我们都将其添加到stack1的顶部。每次出队列时，我们都将stack1的内容清空到stack2中，并删除堆栈顶部的元素。出队列的时间复杂度是O(n)，因为我们必须将stack1复制到stack2。队列的时间复杂度与常规堆栈相同

小开

队列中的两个堆栈定义为遍和stack2。

< >强排队: euqueue的元素总是被推入遍

< >强出列: stack2的顶部可以弹出，因为它是stack2不为空时插入队列的第一个元素。当stack2为空时，我们从遍中弹出所有元素，并将它们逐个推入stack2。队列中的第一个元素被推入遍的底部。由于它位于stack2的顶部，因此可以在弹出和推入操作后直接弹出它

下面是相同的c++示例代码:

template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);


void appendTail(const T& node);
T deleteHead();


private:
stack<T> stack1;
stack<T> stack2;
};


template<typename T> void CQueue<T>::appendTail(const T& element) {
stack1.push(element);
}


template<typename T> T CQueue<T>::deleteHead() {
if(stack2.size()<= 0) {
while(stack1.size()>0) {
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}




if(stack2.size() == 0)
throw new exception("queue is empty");




T head = stack2.top();
stack2.pop();




return head;
}

此解决方案借鉴于我的博客。我的博客网页上有详细的操作模拟分析。

小开

设要实现的队列为q，用于实现q的堆栈为stack1和stack2。

q可以通过两个方式实现:

方法1(通过使enQueue操作成本高)

该方法确保新输入的元素始终位于堆栈1的顶部，这样deQueue操作就会从堆栈1弹出。要将元素放在stack1的顶部，可以使用stack2。

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

方法2(通过提高deQueue操作的成本)

在此方法中，在队列操作中，新元素在stack1的顶部输入。在去队列操作中，如果stack2为空，则所有元素都被移动到stack2，最后返回stack2的顶部。

enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).


deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.

方法二肯定比方法一好。方法1在enQueue操作中移动所有元素两次，而方法2(在deQueue操作中)移动元素一次，并且仅在stack2为空时移动元素。

小开

// Two stacks s1 Original and s2 as Temp one
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();


/*
* Here we insert the data into the stack and if data all ready exist on
* stack than we copy the entire stack s1 to s2 recursively and push the new
* element data onto s1 and than again recursively call the s2 to pop on s1.
*
* Note here we can use either way ie We can keep pushing on s1 and than
* while popping we can remove the first element from s2 by copying
* recursively the data and removing the first index element.
*/
public void insert( int data )
{
if( s1.size() == 0 )
{
s1.push( data );
}
else
{
while( !s1.isEmpty() )
{
s2.push( s1.pop() );
}
s1.push( data );
while( !s2.isEmpty() )
{
s1.push( s2.pop() );
}
}
}


public void remove()
{
if( s1.isEmpty() )
{
System.out.println( "Empty" );
}
else
{
s1.pop();


}
}

小开

我将在Go中回答这个问题，因为Go在其标准库中没有丰富的集合。

由于堆栈真的很容易实现，我想我应该尝试使用两个堆栈来完成一个双端队列。为了更好地理解我是如何得到我的答案的，我将实现分为两部分，第一部分希望更容易理解，但它是不完整的。

type IntQueue struct {
front       []int
back        []int
}


func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}


func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}


func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}


func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}


func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}


func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}

它基本上是两个堆栈，我们允许堆栈的底部相互操纵。我还使用了STL命名约定，其中堆栈的传统push、pop、peek操作都有一个front/back前缀，无论它们是指队列的前面还是后面。

上面代码的问题是它没有非常有效地使用内存。事实上，它会不断增长，直到空间耗尽。这太糟糕了。解决这个问题的方法是尽可能重用堆栈空间的底部。我们必须引入一个偏移量来跟踪这一点，因为围棋中的切片一旦收缩就不能在前面生长。

type IntQueue struct {
front       []int
frontOffset int
back        []int
backOffset  int
}


func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}


func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}


func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}


func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}


func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}


func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}

有很多小函数，但6个函数中有3个只是另一个的镜像。

小开

使用两个java.util.Stack对象实现队列:

public final class QueueUsingStacks<E> {


private final Stack<E> iStack = new Stack<>();
private final Stack<E> oStack = new Stack<>();


public void enqueue(E e) {
iStack.push(e);
}


public E dequeue() {
if (oStack.isEmpty()) {
if (iStack.isEmpty()) {
throw new NoSuchElementException("No elements present in Queue");
}
while (!iStack.isEmpty()) {
oStack.push(iStack.pop());
}
}
return oStack.pop();
}


public boolean isEmpty() {
if (oStack.isEmpty() && iStack.isEmpty()) {
return true;
}
return false;
}


public int size() {
return iStack.size() + oStack.size();
}


}

小开

如何反转堆栈

要理解如何使用两个堆栈构造队列，您应该清楚地了解如何反转堆栈。记住堆叠是如何工作的，它非常类似于你厨房里的盘子堆。最后一个洗过的盘子将放在干净盘子堆的最上面，这在计算机科学中被称为last 我n __abc2first Out (LIFO)。

让我们想象我们的堆栈像一个瓶子，如下所示;

如果我们分别压入整数1,2,3，那么3将在堆栈的顶部。因为1会先被推，然后2会被放在1的上面。最后，将3放在堆栈的顶部，我们的堆栈的最新状态表示为一个瓶子，如下所示;

现在我们的堆栈表示为一个装满值3,2,1的瓶子。我们想要反转堆栈使堆栈顶部的元素为1而堆栈底部的元素为3。我们能做什么?我们可以拿起瓶子，把它倒着拿，这样所有的值都应该按顺序颠倒?

是的，我们可以这样做，但那是一个瓶子。为了完成同样的过程，我们需要有第二个堆栈，它将以相反的顺序存储第一个堆栈元素。让我们把已填充的堆栈放到左边，把新的空堆栈放到右边。为了颠倒元素的顺序，我们将从左堆栈中取出每个元素，并将它们推入右堆栈。你可以在下图中看到我们这样做时发生了什么;

我们知道如何反转堆栈。

使用两个堆栈作为队列

在前面的部分中，我已经解释了如何反转堆栈元素的顺序。这一点很重要，因为如果我们将元素推入和弹出到堆栈中，输出将完全按照队列的相反顺序进行。考虑一个例子，让我们将整数数组{1, 2, 3, 4, 5}推入堆栈。如果我们弹出元素并打印它们，直到堆栈为空，我们将得到与推入顺序相反的数组，它将是{5, 4, 3, 2, 1}记住，对于相同的输入，如果我们将队列出队列直到队列为空，输出将是{1, 2, 3, 4, 5}。因此很明显，对于相同的元素输入顺序，队列的输出与堆栈的输出完全相反。正如我们知道如何使用一个额外的堆栈反转一个堆栈，我们可以使用两个堆栈构造一个队列。

我们的队列模型将由两个堆栈组成。一个堆栈将用于enqueue操作(左边的堆栈#1，将被称为输入堆栈)，另一个堆栈将用于dequeue操作(右边的堆栈#2，将被称为输出堆栈)。看看下面的图片;

我们的伪代码如下;

入队操作

Push every input element to the Input Stack

出列操作

If ( Output Stack is Empty)
pop every element in the Input Stack
and push them to the Output Stack until Input Stack is Empty


pop from Output Stack

让我们分别对整数{1, 2, 3}进行排队。整数将被压入位于左侧的输入堆栈 (堆栈# 1);

那么如果执行出队列操作会发生什么呢?每当执行出队列操作时，queue将检查输出堆栈是否为空(参见上面的伪代码)。如果输出堆栈为空，则输入堆栈将在输出上提取，因此输入堆栈的元素将反转。在返回值之前，队列的状态如下所示;

检查输出堆栈(堆栈#2)中元素的顺序。很明显，我们可以从输出堆栈中弹出元素，这样输出将与从队列中退出队列时相同。因此，如果执行两个出队列操作，首先将分别得到{1, 2}。那么元素3将是输出堆栈中唯一的元素，而输入堆栈将为空。如果我们将元素4和5编入队列，那么队列的状态将如下所示;

现在输出堆栈不是空的，如果我们执行出队列操作，只有3个将从输出堆栈中弹出。这样的状态如下所示;

同样，如果我们再执行两个出队列操作，在第一个出队列操作时，queue将检查Output Stack是否为空，这是true。然后弹出输入堆栈的元素，并将它们推到输出堆栈，直到输入堆栈为空，然后队列的状态将如下所示;

很容易看出，两个出队列操作的输出将是{4, 5}

用两个栈构造队列的实现

下面是Java中的一个实现。我不打算使用现有的Stack实现所以这里的示例将会重新发明轮子;

C - 1) MyStack类:简单的堆栈实现

public class MyStack<T> {


// inner generic Node class
private class Node<T> {
T data;
Node<T> next;


public Node(T data) {
this.data = data;
}
}


private Node<T> head;
private int size;


public void push(T e) {
Node<T> newElem = new Node(e);


if(head == null) {
head = newElem;
} else {
newElem.next = head;
head = newElem;     // new elem on the top of the stack
}


size++;
}


public T pop() {
if(head == null)
return null;


T elem = head.data;
head = head.next;   // top of the stack is head.next


size--;


return elem;
}


public int size() {
return size;
}


public boolean isEmpty() {
return size == 0;
}


public void printStack() {
System.out.print("Stack: ");


if(size == 0)
System.out.print("Empty !");
else
for(Node<T> temp = head; temp != null; temp = temp.next)
System.out.printf("%s ", temp.data);


System.out.printf("\n");
}
}

C - 2) MyQueue类:使用两个堆栈的队列实现

public class MyQueue<T> {


private MyStack<T> inputStack;      // for enqueue
private MyStack<T> outputStack;     // for dequeue
private int size;


public MyQueue() {
inputStack = new MyStack<>();
outputStack = new MyStack<>();
}


public void enqueue(T e) {
inputStack.push(e);
size++;
}


public T dequeue() {
// fill out all the Input if output stack is empty
if(outputStack.isEmpty())
while(!inputStack.isEmpty())
outputStack.push(inputStack.pop());


T temp = null;
if(!outputStack.isEmpty()) {
temp = outputStack.pop();
size--;
}


return temp;
}


public int size() {
return size;
}


public boolean isEmpty() {
return size == 0;
}


}

C - 3)演示代码

public class TestMyQueue {


public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();


// enqueue integers 1..3
for(int i = 1; i <= 3; i++)
queue.enqueue(i);


// execute 2 dequeue operations
for(int i = 0; i < 2; i++)
System.out.println("Dequeued: " + queue.dequeue());


// enqueue integers 4..5
for(int i = 4; i <= 5; i++)
queue.enqueue(i);


// dequeue the rest
while(!queue.isEmpty())
System.out.println("Dequeued: " + queue.dequeue());
}


}

C - 4)样品输出

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

小开

对于c#开发人员，这里是完整的程序:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace QueueImplimentationUsingStack
{
class Program
{
public class Stack<T>
{
public int size;
public Node<T> head;
public void Push(T data)
{
Node<T> node = new Node<T>();
node.data = data;
if (head == null)
head = node;
else
{
node.link = head;
head = node;
}
size++;
Display();
}
public Node<T> Pop()
{
if (head == null)
return null;
else
{
Node<T> temp = head;
//temp.link = null;
head = head.link;
size--;
Display();
return temp;
}
}
public void Display()
{
if (size == 0)
Console.WriteLine("Empty");
else
{
Console.Clear();
Node<T> temp = head;
while (temp!= null)
{
Console.WriteLine(temp.data);
temp = temp.link;
}
}
}
}


public class Queue<T>
{
public int size;
public Stack<T> inbox;
public Stack<T> outbox;
public Queue()
{
inbox = new Stack<T>();
outbox = new Stack<T>();
}
public void EnQueue(T data)
{
inbox.Push(data);
size++;
}
public Node<T> DeQueue()
{
if (outbox.size == 0)
{
while (inbox.size != 0)
{
outbox.Push(inbox.Pop().data);
}
}
Node<T> temp = new Node<T>();
if (outbox.size != 0)
{
temp = outbox.Pop();
size--;
}
return temp;
}


}
public class Node<T>
{
public T data;
public Node<T> link;
}


static void Main(string[] args)
{
Queue<int> q = new Queue<int>();
for (int i = 1; i <= 3; i++)
q.EnQueue(i);
// q.Display();
for (int i = 1; i < 3; i++)
q.DeQueue();
//q.Display();
Console.ReadKey();
}
}
}

小开

c#中的解决方案

public class Queue<T> where T : class
{
private Stack<T> input = new Stack<T>();
private Stack<T> output = new Stack<T>();
public void Enqueue(T t)
{
input.Push(t);
}


public T Dequeue()
{
if (output.Count == 0)
{
while (input.Count != 0)
{
output.Push(input.Pop());
}
}


return output.Pop();
}
}

小开

这是我的解决方案在Java使用链表。

class queue<T>{
static class Node<T>{
private T data;
private Node<T> next;
Node(T data){
this.data = data;
next = null;
}
}
Node firstTop;
Node secondTop;
    

void push(T data){
Node temp = new Node(data);
temp.next = firstTop;
firstTop = temp;
}
    

void pop(){
if(firstTop == null){
return;
}
Node temp = firstTop;
while(temp != null){
Node temp1 = new Node(temp.data);
temp1.next = secondTop;
secondTop = temp1;
temp = temp.next;
}
secondTop = secondTop.next;
firstTop = null;
while(secondTop != null){
Node temp3 = new Node(secondTop.data);
temp3.next = firstTop;
firstTop = temp3;
secondTop = secondTop.next;
}
}
    

}

在这种情况下，弹出操作是非常耗时的。因此，我不建议使用两个堆栈创建队列。

小开

使用O(1) dequeue()，它与pythonquick的回答相同:

// time: O(n), space: O(n)
enqueue(x):
if stack.isEmpty():
stack.push(x)
return
temp = stack.pop()
enqueue(x)
stack.push(temp)


// time: O(1)
x dequeue():
return stack.pop()

使用O(1) enqueue()(这在本文中没有提到，所以这个答案)，它也使用回溯来冒泡并返回最底部的项。

// O(1)
enqueue(x):
stack.push(x)


// time: O(n), space: O(n)
x dequeue():
temp = stack.pop()
if stack.isEmpty():
x = temp
else:
x = dequeue()
stack.push(temp)
return x

显然，这是一个很好的编码练习，因为它效率很低，但仍然很优雅。

小开

在Swift中使用两个堆栈的队列实现:

struct Stack<Element> {
var items = [Element]()


var count : Int {
return items.count
}


mutating func push(_ item: Element) {
items.append(item)
}


mutating func pop() -> Element? {
return items.removeLast()
}


func peek() -> Element? {
return items.last
}
}


struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()


mutating func enqueue(_ item: Element) {
inStack.push(item)
}


mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}


mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}


private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}

小开

虽然你会得到很多与实现两个堆栈的队列相关的帖子: 1. 要么使enQueue进程的开销大大增加 2. 或者通过使deQueue进程更加昂贵

https://www.geeksforgeeks.org/queue-using-stacks/

我从上面的帖子中发现的一个重要方法是只使用堆栈数据结构和递归调用堆栈来构造队列。

虽然有人可能会说，从字面上看，这仍然是使用两个堆栈，但理想情况下，这只使用一个堆栈数据结构。

下面是问题的解释:

声明一个堆栈用于数据的enqueue和deQueing，并将数据推入堆栈。

而dequeuing有一个基本条件，即当堆栈大小为1时，堆栈中的元素将弹出。这将确保在deQueue递归期间没有堆栈溢出。

在退出队列时，首先从堆栈顶部弹出数据。理想情况下，该元素将是堆栈顶部的元素。完成此操作后，递归地调用deQueue函数，然后将上面弹出的元素推回堆栈。

代码如下所示:

if (s1.isEmpty())
System.out.println("The Queue is empty");
else if (s1.size() == 1)
return s1.pop();
else {
int x = s1.pop();
int result = deQueue();
s1.push(x);
return result;

通过这种方式，您可以使用单个堆栈数据结构和递归调用堆栈创建队列。

小开

下面是使用ES6语法的javascript语言解决方案。

Stack.js

//stack using array
class Stack {
constructor() {
this.data = [];
}


push(data) {
this.data.push(data);
}


pop() {
return this.data.pop();
}


peek() {
return this.data[this.data.length - 1];
}


size(){
return this.data.length;
}
}


export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";


class QueueUsingTwoStacks {
constructor() {
this.stack1 = new Stack();
this.stack2 = new Stack();
}


enqueue(data) {
this.stack1.push(data);
}


dequeue() {
//if both stacks are empty, return undefined
if (this.stack1.size() === 0 && this.stack2.size() === 0)
return undefined;


//if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
if (this.stack2.size() === 0) {
while (this.stack1.size() !== 0) {
this.stack2.push(this.stack1.pop());
}
}


//pop and return the element from stack 2
return this.stack2.pop();
}
}


export { QueueUsingTwoStacks };

用法如下:

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';


let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");


console.log(que.dequeue());  //output: "A"

小开

使用堆栈实现队列的以下操作。

push(x)——将元素x推到队列的后面。

pop()——从队列前面移除元素。

peek()——获取前端元素。

empty()——返回队列是否为空。

class MyQueue {


Stack<Integer> input;
Stack<Integer> output;


/** Initialize your data structure here. */
public MyQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}


/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}


/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}


/** Get the front element. */
public int peek() {
if(output.isEmpty()) {
while(!input.isEmpty()) {
output.push(input.pop());
}
}
return output.peek();
}


/** Returns whether the queue is empty. */
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}

小开

简单的JS解决方案**

注:我从其他人的评论中获得了一些想法

/*


enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).


deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.


*/
class myQueue {
constructor() {
this.stack1 = [];
this.stack2 = [];
}


push(item) {
this.stack1.push(item)
}


remove() {
if (this.stack1.length == 0 && this.stack2.length == 0) {
return "Stack are empty"
}


if (this.stack2.length == 0) {


while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2.pop()
}




peek() {
if (this.stack2.length == 0 && this.stack1.length == 0) {
return 'Empty list'
}


if (this.stack2.length == 0) {
while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}


return this.stack2[0]
}


isEmpty() {
return this.stack2.length === 0 && this.stack1.length === 0;
}


}


const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()


console.log(q)

小开

我的PHP解决方案

<?php
$_fp = fopen("php://stdin", "r");
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
$queue = array();
$count = 0;
while($line = fgets($_fp)) {
if($count == 0) {
$noOfElement = $line;
$count++;
continue;
}
$action = explode(" ",$line);
$case = $action[0];
switch($case) {
case 1:
$enqueueValue = $action[1];
array_push($queue, $enqueueValue);
break;
case 2:
array_shift($queue);
break;
case 3:
$show = reset($queue);
print_r($show);
break;
default:
break;
}
}
?>

如何使用两个堆栈实现队列?