假设我们有两个堆栈并且没有其他临时变量。
是否可以仅使用两个堆栈来“构建”队列数据结构？
Nitin
问问题
350875 次
21 回答
766
保留 2 个堆栈，我们称它们为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();
}
}
于 2008-09-16T04:42:02.777 回答
288
A - 如何反转堆栈
要了解如何使用两个堆栈构造队列，您应该清楚地了解如何反转堆栈。记住堆栈的工作原理，它与厨房里的盘子非常相似。最后洗过的盘子将位于干净堆栈的顶部，这在计算机科学中称为Last I n F irst O ut (LIFO)。
让我们把我们的堆栈想象成一个瓶子，如下所示；
如果我们分别压入整数 1,2,3，那么 3 将在栈顶。因为 1 将首先被压入，然后 2 将被放在 1 的顶部。最后，3 将被放在堆栈顶部，我们以瓶子表示的堆栈的最新状态如下所示；
现在我们将堆栈表示为一个瓶子，其中填充了值 3,2,1。我们想反转堆栈，使堆栈的顶部元素为 1，堆栈的底部元素为 3。我们能做什么？我们可以把瓶子倒过来拿，这样所有的值都应该按顺序颠倒？
是的，我们可以这样做，但那是一个瓶子。要执行相同的过程，我们需要有第二个堆栈，它将以相反的顺序存储第一个堆栈元素。让我们将填充的堆栈放在左侧，将新的空堆栈放在右侧。为了颠倒元素的顺序，我们将从左侧堆栈中弹出每个元素，并将它们推送到右侧堆栈。您可以在下图中看到我们这样做时会发生什么；
所以我们知道如何反转堆栈。
B - 使用两个堆栈作为队列
在前面的部分中，我已经解释了如何反转堆栈元素的顺序。这很重要，因为如果我们将元素推送和弹出堆栈，输出将完全按照队列的相反顺序。考虑一个例子，让我们将整数数组推入{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 ）；
那么如果我们执行出列操作会发生什么呢？每当执行出队操作时，队列将检查输出堆栈是否为空（请参见上面的伪代码）如果输出堆栈为空，则将在输出上提取输入堆栈，因此元素输入堆栈将被反转。在返回值之前，队列的状态如下：
查看输出堆栈（堆栈#2）中元素的顺序。很明显，我们可以从输出堆栈中弹出元素，这样输出就与我们从队列中出列一样。因此，如果我们执行两个出队操作，首先我们将{1, 2}分别得到。然后元素 3 将是输出堆栈的唯一元素，输入堆栈将为空。如果我们将元素 4 和 5 入队，那么队列的状态将如下所示；
现在Output Stack不是空的，如果我们执行dequeue操作，只会从Output Stack中弹出3个。然后状态将如下所示；
同样，如果我们再执行两次出队操作，在第一次出队操作时，队列将检查输出堆栈是否为空，这是真的。然后将 Input Stack 的元素弹出并推送到 Output Stack，直到 Input Stack 为空，此时 Queue 的状态如下；
容易看出，两个出队操作的输出将是{4, 5}
C - 用两个堆栈构造的队列的实现
这是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
于 2016-08-22T23:01:21.293 回答
80
您甚至可以只使用一个堆栈来模拟队列。第二个（临时）堆栈可以通过对插入方法的递归调用的调用堆栈来模拟。
将新元素插入队列时，原理保持不变：
- 您需要将元素从一个堆栈转移到另一个临时堆栈，以颠倒它们的顺序。
- 然后将要插入的新元素推入临时堆栈
- 然后将元素转移回原始堆栈
- 新元素将在栈底，最旧的元素在栈顶（首先被弹出）
仅使用一个 Stack 的 Queue 类如下所示：
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();
}
}
于 2008-09-16T20:58:59.807 回答
14
不过，时间复杂度会更糟。一个好的队列实现在恒定时间内完成所有事情。
编辑
不知道为什么我的回答在这里被否决了。如果我们编程，我们关心时间复杂度，使用两个标准栈来做一个队列是低效的。这是一个非常有效和相关的观点。如果其他人觉得有必要对此投反对票，我很想知道为什么。
更多细节：关于为什么使用两个堆栈比仅使用一个队列更糟糕：如果您使用两个堆栈，并且有人在发件箱为空时调用 dequeue，您需要线性时间才能到达收件箱的底部（如您所见在戴夫的代码中）。
您可以将队列实现为单链表（每个元素指向下一个插入的元素），保留一个指向最后插入元素的额外指针以进行推送（或使其成为循环列表）。在这个数据结构上实现队列和出队很容易在常数时间内完成。这是最坏情况下的常数时间，没有摊销。而且，正如评论似乎要求澄清的那样，最坏情况下的常数时间严格优于摊销常数时间。
于 2008-09-16T03:40:44.967 回答
8
设要实现的队列为 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.
方法 2 肯定比方法 1 好。方法 1 在 enQueue 操作中移动所有元素两次，而方法 2（在 deQueue 操作中）移动元素一次，只有在 stack2 为空时才移动元素。
于 2014-03-30T22:34:40.437 回答
4
使用堆栈实现队列的以下操作。
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();
}
}
于 2019-09-19T10:05:11.347 回答
3
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();
}
}
于 2017-05-31T00:08:56.520 回答
2
You'll have to pop everything off the first stack to get the bottom element. Then put them all back onto the second stack for every "dequeue" operation.
于 2008-09-16T04:26:11.707 回答
2
队列中的两个堆栈定义为stack1和stack2。
Enqueue： 入队的元素总是被推入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;
}
这个解决方案是从我的博客中借来的。在我的博客网页中可以找到更详细的分步操作模拟分析。
于 2012-12-29T02:02:15.273 回答
2
对于 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();
}
}
}
于 2016-11-15T05:55:56.280 回答
1
在 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()!)
}
}
}
}
于 2017-10-17T17:41:38.783 回答
1
虽然您会收到很多与实现具有两个堆栈的队列相关的帖子：1. 要么使 enQueue 过程成本更高 2. 要么使 deQueue 过程成本更高
https://www.geeksforgeeks.org/queue-using-stacks/
我从上面的帖子中发现的一种重要方法是仅使用堆栈数据结构和递归调用堆栈构建队列。
虽然有人可以争辩说这仍然使用两个堆栈，但理想情况下它只使用一个堆栈数据结构。
下面是问题的解释：
声明一个堆栈用于对数据进行入队和出队，并将数据推送到堆栈中。
而 deQueueing 有一个基本条件，即当堆栈大小为 1 时弹出堆栈的元素。这将确保 deQueue 递归期间没有堆栈溢出。
在 deQueueing 时首先从栈顶弹出数据。理想情况下，该元素将是位于堆栈顶部的元素。现在一旦完成，递归调用 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;
这样，您可以使用单个堆栈数据结构和递归调用堆栈创建队列。
于 2018-05-27T03:02:42.573 回答
1
下面是使用 ES6 语法的 javascript 语言解决方案。
堆栈.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"
于 2019-01-20T08:09:09.463 回答
0
With 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()
With 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
显然，这是一个很好的编码练习，因为它虽然效率低但很优雅。
于 2017-10-13T07:33:04.120 回答
0
我将在 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 操作具有前/后前缀，无论它们是指队列的前面还是后面。
上述代码的问题在于它不能非常有效地使用内存。实际上，它会无限增长，直到空间不足。这真的很糟糕。解决此问题的方法是尽可能简单地重用堆栈空间的底部。我们必须引入偏移量来跟踪这一点，因为 Go 中的切片一旦缩小就不能在前面增长。
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 个只是另一个的镜像。
于 2016-05-22T16:08:49.340 回答
0
我的 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;
}
}
?>
于 2021-04-22T02:42:18.007 回答
0
// 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();
}
}
于 2015-10-13T06:49:05.030 回答
0
**简单的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)于 2020-06-10T14:19:49.347 回答
-1
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();
}
}
对于每个入队操作，我们添加到堆栈的顶部1。对于每个出队，我们将stack1的内容清空到stack2中，并删除栈顶的元素。出队的时间复杂度为O(n)，因为我们必须将stack1复制到stack2。enqueue 的时间复杂度和普通栈一样
于 2012-04-11T17:54:14.877 回答
-1
这是我在 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;
}
}
}
注意：在这种情况下，弹出操作非常耗时。所以我不建议使用两个堆栈创建一个队列。
于 2017-09-24T13:32:41.467 回答
-2
使用两个 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();
}
}
于 2016-08-06T08:04:40.213 回答