假设我们有两个堆栈，没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
队列中的两个堆栈定义为stack1和stack2。
排队: euqueued的元素总是被推入stack1
出列: stack2的顶部可以被弹出，因为它是在stack2不为空时插入队列的第一个元素。当stack2为空时，我们从stack1中弹出所有元素，并将它们逐个推入stack2。队列中的第一个元素被压入stack1的底部。由于它位于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;
}
这个解决方案是从我的博客中借来的。我的博客网页上有详细的操作模拟分析。
其他回答
您甚至可以只使用一个堆栈模拟一个队列。第二个(临时)堆栈可以通过对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();
}
}
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();
}
}
队列中的两个堆栈定义为stack1和stack2。
排队: euqueued的元素总是被推入stack1
出列: stack2的顶部可以被弹出，因为它是在stack2不为空时插入队列的第一个元素。当stack2为空时，我们从stack1中弹出所有元素，并将它们逐个推入stack2。队列中的第一个元素被压入stack1的底部。由于它位于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;
}
这个解决方案是从我的博客中借来的。我的博客网页上有详细的操作模拟分析。
简单的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)
我将在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个只是另一个的镜像。
