假设我们有两个堆栈，没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
对于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#开发人员，这里是完整的程序:
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();
}
}
您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。
简单的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)
虽然你会得到很多与实现两个堆栈的队列相关的帖子: 1. 要么使enQueue进程的开销大大增加 2. 或者通过增加deQueue进程的开销
https://www.geeksforgeeks.org/queue-using-stacks/
我从上面的帖子中发现的一个重要方法是只使用堆栈数据结构和递归调用堆栈来构造队列。
虽然有人可能会说，从字面上看，这仍然是使用两个堆栈，但理想情况下，这只使用一个堆栈数据结构。
下面是问题的解释:
Declare a single stack for enQueuing and deQueing the data and push the data into the stack. while deQueueing have a base condition where the element of the stack is poped when the size of the stack is 1. This will ensure that there is no stack overflow during the deQueue recursion. While deQueueing first pop the data from the top of the stack. Ideally this element will be the element which is present at the top of the stack. Now once this is done, recursively call the deQueue function and then push the element popped above back into the stack.
代码如下所示:
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;
通过这种方式，您可以使用单个堆栈数据结构和递归调用堆栈创建队列。
