假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
假设我们有两个堆栈,没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
下面是使用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"
其他回答
不过,时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。
Edit
不知道为什么我的答案在这里被否决了。如果我们编程,我们会关心时间复杂度,使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票,我很想知道为什么。
更详细一点:关于为什么使用两个堆栈比使用一个队列更糟糕:如果您使用两个堆栈,并且有人在发件箱为空时调用dequeue,则需要线性时间才能到达收件箱的底部(正如您可以在Dave的代码中看到的那样)。
您可以将队列实现为单链表(每个元素指向下一个插入的元素),保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易,只需常数时间即可完成。这是最坏情况的常数时间,不是平摊。而且,正如注释中要求澄清的那样,最坏情况下常数时间严格来说比平摊常数时间要好。
简单的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)
// 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();
}
}
使用堆栈实现队列的以下操作。
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();
}
}
您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。