【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

时间:2022-01-01 08:06:32

更多 LeetCode 题解笔记可以访问我的 github

@

描述

使用队列实现栈的下列操作:

  • push(x) -- 元素 x 入栈
  • pop() -- 移除栈顶元素
  • top() -- 获取栈顶元素
  • empty() -- 返回栈是否为空

注意:

  • 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

解法一:双队列,入快出慢

思路

为了实现栈这种数据结构后入先出(last in first out, LIFO)的效果,解法一借助于两个队列。其中,一个队列保存栈的所有元素(设为队列1 q1),另一个队列用于辅助实现入栈、出栈的效果(设为队列2 q2)。相关操作的底层实现细节见下面对应的小节。

入栈(push)

入栈时,直接将新的元素 x 压入队列1 q1 的队尾(rear),并且用变量 top 保存栈顶元素,方便后面的查看栈顶元素(peek)操作,具体的实现步骤见图1。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图1:将一个元素压入栈

代码(Java)实现如下:

/** Push element x onto stack. */
public void push(int x) {
top = x;
q1.add(x);
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

出栈(pop)

由于入栈时直接将元素入队到队列1 q1 中,因此,栈顶的元素位于队列1 q1 的尾部。为了能将栈顶元素(队列1 q1 尾部的元素)弹出,必须先将队列1 q1 队尾之前的元素出队。这里,我们借助另一个队列(辅助队列 q2)实现这一过程——将队列1 q1 队尾之前的元素出队并入队到队列2 q2 中。 之后,将队列1 q1 中唯一个元素(栈顶元素)出队。最后,再将两个队列的引用进行交换即可完成出栈操作。具体的实现步骤如图2所示。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图2:将一个元素出栈

代码(Java)实现如下:

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (q1.size() == 0) {
throw new NoSuchElementException("[ERROR] The queue is empty!");
} while (q1.size() > 1) {
top = q1.remove();
q2.add(top);
}
int res = q1.remove(); Queue<Integer> temp = q1;
q1 = q2;
q2 = temp; return res;
}

复杂度分析如下:

  • 时间复杂度:$ O(n) $,其中 \(n\) 表示未出栈前元素的数目。出栈操作需要从队列1 q1 出队 \(n\) 个元素,同时入队 \(n-1\) 个元素到队列2 q2,因此需要 \(2n - 1\) 次操作。因此 LinkedList 的添加和删除操作的时间复杂度是 \(O(1)\) 的,因此,总的时间复杂度为 \(O(n)\)
  • 空间复杂度:$ O(1) $

查看栈顶元素(peek)

因为我们用变量 top 保存了栈顶的元素,因此只需要返回该变量即可,代码(Java)实现如下:

/** Get the top element. */
public int top() {
return top;
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

是否为空(empty)

队列1 q1 中保存了栈中的所有元素,因此,如果想要知道栈是否为空,只需要判断队列1 q1 中是否还有元素,代码(Java)实现如下:

/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

Java 实现

import java.util.NoSuchElementException;
import java.util.LinkedList;
import java.util.Queue; class MyStack { /**
* The main queue using to store all the elements in the stack
*/
private Queue<Integer> q1;
/**
* The auxiliary queue using to implement `pop` operation
*/
private Queue<Integer> q2;
/**
* The top element in the stack
*/
private int top; /** Initialize your data structure here. */
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
} /** Push element x onto stack. */
public void push(int x) {
top = x;
q1.add(x);
} /** Removes the element on top of the stack and returns that element. */
public int pop() {
if (q1.size() == 0) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} while (q1.size() > 1) {
top = q1.remove();
q2.add(top);
}
int res = q1.remove(); Queue<Integer> temp = q1;
q1 = q2;
q2 = temp; return res;
} /** Get the top element. */
public int top() {
return top;
} /** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}
}

Python 实现

from collections import deque

class MyStack:

    def __init__(self):
"""
Initialize your data structure here.
"""
self._q1, self._q2, self._top = deque(), deque(), None def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self._top = x
self._q1.append(x) def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if not self._q1:
raise Exception("[ERROR] The stack is empty!") while len(self._q1) > 1:
self._top = self._q1.popleft()
self._q2.append(self._top)
res = self._q1.popleft() self._q1, self._q2 = self._q2, self._q1
return res def top(self):
"""
Get the top element.
:rtype: int
"""
return self._top def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return not self._q1

解法二:双队列,入慢出快

思路

与解法一相同的是,解法二也借助于两个队列。不同之处在于解法二在入栈时,已经在队列中将元素排列成出栈的顺序。因此,解法二实现的栈的入栈操作是 \(O(n)\) 的时间复杂度,而出栈操作则只需要 \(O(1)\) 的时间复杂度。相关操作的底层实现细节见下面对应的小节。

入栈(push)

为了使得队列1 q1 中的出队顺序和出栈顺序是一致的,需要借助另一个队列(辅助队列 q2)。每次有新的元素压入栈时,将该元素入队到队列2 q2 中。接着,将队列1 q1 中的所有元素出队并入队到队列2 q2 中。最后,再将两个队列的引用进行交换,则队列1 q1 中出队的顺序即为实际的出栈顺序。具体的操作步骤如图3所示。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图3:将一个元素压入栈

代码(Java)实现如下:

/** Push element x onto stack. */
public void push(int x) {
q2.add(x);
while (!q1.isEmpty()) {
q2.add(q1.remove());
} Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}

复杂度分析如下:

  • 时间复杂度:\(O(n)\),其中 \(n\) 表示入栈前元素的数目。入栈操作需要 \(n+1\) 个入队操作,同时还需要 \(n\) 个出队操作,因此,总共需要 \(2n + 1\) 个操作。由于 LinkedList 的添加和删除操作的时间复杂度是 \(O(1)\) 的,因此,总的时间复杂度是 \(O(n)\) 的
  • 空间复杂度:\(O(1)\)

出栈(pop)

由于在入栈时已经将队列中的元素排列成出栈的顺序,因此,只需要出队队列1 q1 中队首的元素即可。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图4:将一个元素出栈

代码(Java)实现如下:

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (q1.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return q1.remove();
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

查看栈顶元素(peek)

同理,只需要返回队列1 q1 队首元素即可。

/** Get the top element. */
public int top() {
if (q1.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return q1.peek();
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

是否为空(empty)

这个操作和解法一的没什么不同,故不再赘言。

Java 实现

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue; class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2; /** Initialize your data structure here. */
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
} /** Push element x onto stack. */
public void push(int x) {
q2.add(x);
while (!q1.isEmpty()) {
q2.add(q1.remove());
} Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
} /** Removes the element on top of the stack and returns that element. */
public int pop() {
if (q1.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return q1.remove();
} /** Get the top element. */
public int top() {
if (q1.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return q1.peek();
} /** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty();
}
}

Python 实现

from collections import deque

class MyStack:

    def __init__(self):
"""
Initialize your data structure here.
"""
self._q1, self._q2 = deque(), deque() def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self._q2.append(x)
while self._q1:
self._q2.append(self._q1.popleft())
self._q1, self._q2 = self._q2, self._q1 def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if not self._q1:
raise Exception("[ERROR] The stack is empty!")
return self._q1.popleft() def top(self):
"""
Get the top element.
:rtype: int
"""
if not self._q1:
raise Exception("[ERROR] The stack is empty!")
return self._q1[0] def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return not self._q1

解法三:单队列

思路

上面两种解法都借助于两个队列,实际上,只借助于一个队列也可以实现栈的先入先出效果。

入栈(push)

入栈时,新添加的元素位于队列的队尾,但是对于栈而言,它其实是栈顶元素。为了使得新添加的元素位于队首,可以将其之前的所有元素出队并重新入队。最终,队列中元素的顺序和出栈的顺序是一致的。具体的操作步骤如下图所示。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图5:将一个元素压入栈

代码(Java)实现如下:

/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i = 0; i < queue.size() - 1; ++i) {
queue.add(queue.remove());
}
}

复杂度分析:

  • 时间复杂度:\(O(n)\),其中 \(n\) 表示入栈前栈内元素的数目。入栈操作需要 \(n\) 次的出队操作,同时也需要 \(n + 1\)次的入队操作,因此,需要总的操作次数为 \(2n + 1\) 次。由于 LinkedList 的添加和删除操作的时间复杂度是 \(O(1)\) 的,因此,总的时间复杂度为 \(O(n)\)
  • 空间复杂度:\(O(1)\)

出栈(pop)

由于在入栈时已经将队列中的元素排列成出栈的顺序,因此,只需要出队队列 q1 中队首的元素即可。

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)

图6:将一个元素出栈

代码(Java)实现如下:

/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (queue.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return queue.remove();
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

查看栈顶元素(peek)

同理,只需要返回队列 q1 的队首元素即可。

/** Get the top element. */
public int top() {
if (queue.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return queue.peek();
}

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

是否为空(empty)

队列 q1 中保存了栈中的所有元素,因此,如果想要知道栈是否为空,只需要判断队列 q1 中是否还有元素,代码(Java)实现如下:

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

复杂度分析如下:

  • 时间复杂度:$ O(1) $
  • 空间复杂度:$ O(1) $

Java 实现

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue; class MyStack {
private Queue<Integer> queue; /** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
} /** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i = 0; i < queue.size() - 1; ++i) {
queue.add(queue.remove());
}
} /** Removes the element on top of the stack and returns that element. */
public int pop() {
if (queue.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return queue.remove();
} /** Get the top element. */
public int top() {
if (queue.isEmpty()) {
throw new NoSuchElementException("[ERROR] The stack is empty!");
} return queue.peek();
} /** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
} /**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/

Python 实现

from collections import deque

class MyStack:

    def __init__(self):
"""
Initialize your data structure here.
"""
self._q = deque() def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self._q.append(x)
for _ in range(len(self._q) - 1):
self._q.append(self._q.popleft()) def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
if not self._q:
raise Exception("[ERROR] The stack is empty!")
return self._q.popleft() def top(self):
"""
Get the top element.
:rtype: int
"""
if not self._q:
raise Exception("[ERROR] The stack is empty!")
return self._q[0] def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return not self._q

【LeetCode题解】225_用队列实现栈(Implement-Stack-using-Queues)的更多相关文章

  1. LeetCode 225:用队列实现栈 Implement Stack using Queues

    题目: 使用队列实现栈的下列操作: push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Implement th ...

  2. &lbrack;Swift&rsqb;LeetCode225&period; 用队列实现栈 &vert; Implement Stack using Queues

    Implement the following operations of a stack using queues. push(x) -- Push element x onto stack. po ...

  3. leetcode:Implement Stack using Queues 与 Implement Queue using Stacks

    一.Implement Stack using Queues Implement the following operations of a stack using queues. push(x) - ...

  4. leetcode 155&period; Min Stack 、232&period; Implement Queue using Stacks 、225&period; Implement Stack using Queues

    155. Min Stack class MinStack { public: /** initialize your data structure here. */ MinStack() { } v ...

  5. 【LeetCode】232 &amp&semi; 225 - Implement Queue using Stacks &amp&semi; Implement Stack using Queues

    232 - Implement Queue using Stacks Implement the following operations of a queue using stacks. push( ...

  6. 232&period; Implement Queue using Stacks&comma;225&period; Implement Stack using Queues

    232. Implement Queue using Stacks Total Accepted: 27024 Total Submissions: 79793 Difficulty: Easy Im ...

  7. Implement Queue by Two Stacks &amp&semi; Implement Stack using Queues

    Implement Queue by Two Stacks Implement the following operations of a queue using stacks. push(x) -- ...

  8. &lbrack;LeetCode&rsqb; Implement Stack using Queues 用队列来实现栈

    Implement the following operations of a stack using queues. push(x) -- Push element x onto stack. po ...

  9. LeetCode 225 Implement Stack using Queues(用队列来实现栈)(&ast;)

    翻译 用队列来实现栈的例如以下操作. push(x) -- 将元素x加入进栈 pop() -- 从栈顶移除元素 top() -- 返回栈顶元素 empty() -- 返回栈是否为空 注意: 你必须使用 ...

随机推荐

  1. iOS-大神们的博客收集

    唐巧的技术博客 http://blog.devtang.comOneV's Den http://onevcat.com破船之家 http://beyondvincent.comNSHipster h ...

  2. SQL Server 2012 使用警报调度数据库作业通知操作员

    如果想让数据库满足某种条件时,触动警报,然后执行一系列作业,并通知管理员,则需要配置警报 比如,当数据库日志达到一定大小如10M时触动警报,执行以下3个作业步骤:备份日志.收缩日志文件到2M.完备数据 ...

  3. 【转】Android中如何使用Bundle传递对象&lbrack;使用Serializable或者Parcelable&rsqb; -- 不错

    原文网址:http://www.jcodecraeer.com/a/anzhuokaifa/androidkaifa/2012/1211/694.html Android中Bundle类的作用 Bun ...

  4. ARM map&lpar;Program size&rpar;

    1.Keil程式编译完之后,在List目录下会生成一个.map文件,里面包含各个存储块数据大小. Code:ARM 指令. RO(Read only)只读数据,如const int gu8test = ...

  5. 高考志愿填报:java 软件 程序员 目前的就业现状

    大约在17年前,也就是2000年,学计算机专业的学生可以有大部分都进入本专业,并且就业非常容易.哪怕只会office套件,想找个工作也很简单.那时候学计算机就是最热门的行业. 那时候,搞Java的还是 ...

  6. 极致21点开发DAY1

    最近在学习UI框架,无奈没有完整的项目学习,四处搜索找了这款游戏源码,在Unity2018上完美运行.于是乎开始学习开发这款游戏.今天主要完成的任务时拼UI.搭建了3个场景, StartScene, ...

  7. 安卓打开远程调试&lpar;免root&rpar;

    首先用数据线连接adb,在pc端执行: adb tcpip 5555 然后就能拔掉数据线了. pc执行这个: adb connect 172.19.208.2 就能连接上

  8. 归并排序的JavaScript实现

    思想 这是一种分治算法.将原始数组切分成较小的数组,直到每个小数组只有一项,然后在将小数组归并为排好序的较大数组,直到最后得到一个排好序的最大数组. 代码 function mergeSort(arr ...

  9. Java 处理批量数据提交

    在Java web开发过程中,处理表单数据是很重要一部分,常见的是form post处理单条数据的,但也会遇到一次提交多条数据到服务器的,如下:

  10. net上传文件的三种方法

    ASP.NET依托.net framework类库,封装了大量的功能,使得上传文件非常简单,主要有以下三种基本方法. 方法一:用Web控件FileUpload,上传到网站根目录. Test.aspx关 ...