您现在的位置是:首页 > 文章详情

LeetCode 232:用栈实现队列 Implement Queue using Stacks

日期:2019-08-09点击:264

题目:

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

  • push(x) -- 将一个元素放入队列的尾部。
  • pop() -- 从队列首部移除元素。
  • peek() -- 返回队列首部的元素。
  • empty() -- 返回队列是否为空。

Implement the following operations of a queue using stacks.

  • push(x) -- Push element x to the back of queue.
  • pop() -- Removes the element from in front of queue.
  • peek() -- Get the front element.
  • empty() -- Return whether the queue is empty.

示例:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

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

Notes:

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

解题思路:

队列先进后出,栈后进先出。用栈实现队列,可以用两个栈完成题解。入队列时用 stack1 存入节点,出队列时 stack1 内节点顺序出栈压入 stack2 中。

例如 1, 2, 3 元素顺序入队列 即存入栈stack1:[1, 2, 3] 出队列时顺序应为:1->2->3 但是栈先进先出,出栈顺序为:3->2->1 与出队列顺序不相符 借助另一个栈stack2 stack1内的元素顺序出栈并压入stack2 stack1:[1, 2, 3] ---> stack2:[3, 2, 1] 此时stack2出栈顺序:1->2->3 与出队列顺序相符

注意:在出队列时无需着急将 stack1 中的节点顺序压入 stack2。因为要实现的队列是先进后出,可以将 stack2 中的节点全部弹出之后 再将 stack1 内节点顺序压入stack2,这样可以将出栈的时间复杂度摊还到 O(1)。

Java:

class MyQueue { private Stack<Integer> stack1; private Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } public void push(int x) { stack1.push(x); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { //stack1节点顺序弹出并压入stack2 if (stack2.isEmpty()) {//条件是: stack2为空,而不是stack1非空, 这样摊还复杂度O(1) while (!stack1.isEmpty()) { stack2.push(stack1.pop());//stack1弹出节点并压入stack2 } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } }

Python:

Python语言没有栈和队列数据结构,只能用数组 List 或双端队列 deque 实现。

这类编程语言就压根不需要 用队列实现栈或用栈实现队列这种问题,因为栈和队列本身就必须借助List、deque实现。

所以这道题在这种语言中这就非常简单了,可以说是作弊。

class MyQueue: def __init__(self): self.queue = [] def push(self, x: int) -> None: self.queue.append(x) def pop(self) -> int: #弹出第一个元素 return self.queue.pop(0) def peek(self) -> int: #返回第一个元素 return self.queue[0] def empty(self) -> bool: return not self.queue

欢迎关注微.信公.众号:爱写Bug

原文链接:https://yq.aliyun.com/articles/713542
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章