189 8069 5689

Python中如何用栈实现队列-创新互联

Python中如何用栈实现队列，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站设计、成都网站制作、天坛街道网络推广、小程序开发、天坛街道网络营销、天坛街道企业策划、天坛街道品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；创新互联为所有大学生创业者提供天坛街道建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

用栈实现队列

题目：

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

  • 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 stack1;
 private Stack 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

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注创新互联-成都网站建设公司行业资讯频道，感谢您对创新互联的支持。


文章标题：Python中如何用栈实现队列-创新互联
路径分享：http://cdxtjz.cn/article/degcoi.html

其他资讯