详解两个栈实现一个队列（python实现——经典面试题）

旧城等待， 2022-05-14 05:12 152阅读 0赞

## 1、题目说明 ##

使用两个栈结构，实现一个队列功能，实现队列的添加元素和弹出元素。

注意：

队列特点是只能在队列尾部添加元素，在队列头部删除元素，先进先出（FIFO/LILO）

## 2、结题思路 ##

两个栈可以巧妙的结合，第一个栈用来添加元素，而在第二个栈中弹出元素。

我们把所有添加元素的操作放在第一个栈中实现，当需要弹出元素时全部放在第二个栈中实现，当然，还会涉及有时候把第一个栈中的元素转移到第二个栈中已满足队列的逻辑。

## 3、代码实现 ##

class QueueWithTwoStacks(object):
        def __init__(self):
            self._stack1 = []
            self._stack2 = []
        def appendTail(self,x):
            self._stack1.append(x)
        def deleteHead(self):
            if self._stack2:
                return self._stack2.pop()
            else:
                if self._stack1:
                    while self._stack1:
                       self._stack2.append(self._stack1.pop())
                    return self._stack2.pop()
                else:
                    return None
        def getQueue(self):
            return self._stack1
    q = QueueWithTwoStacks()
    q.appendTail(1)
    q.appendTail(2)
    q.appendTail(3)
    print(q.getQueue())
    #q.deleteHead()
    print(q.deleteHead())
    print(q.deleteHead())
    print(q.deleteHead())

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关栈&队列面试题之两个队列实现一个栈

两个队列实现一个栈在之前我曾经实现了两个栈实现一个队列的面试题，其实思路也很简单就是充分利用栈的特性-后进先出，将输入的数据先输入栈1，将该栈1再输出到栈2，最后将栈

àì夳堔傛蜴生んèń/ 2022年09月26日 01:57/ 0 赞/ 156 阅读

相关栈&队列面试题之之两个栈实现一个队列

使用两个栈实现一个队列剖析：我们知道栈是后进先出的一种数据结构，而队列是先进先出的一种数据结构，如何用两个栈来模拟队列这种数据结构呢？利用栈的特性-后进的先出，

本是古典何须时尚/ 2022年09月25日 13:21/ 0 赞/ 140 阅读

相关面试题7：用两个队列实现一个栈

面试题7：用两个队列实现一个栈题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代

梦里梦外;/ 2022年07月12日 05:15/ 0 赞/ 280 阅读

相关面试题7：用两个队列实现一个栈

面试题7：用两个队列实现一个栈题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代

- 日理万妓/ 2022年07月12日 05:15/ 0 赞/ 332 阅读

相关 Python剑指offer之两个栈实现一个队列-两个队列实现一个栈

栈与队列之间的相互实现，是面试中的经典试题。两个栈实现一个队列入队：元素进栈A 出队：先判断栈B是否为空，为空则将栈A中的元素 pop 出来并 push 进栈B，

一时失言乱红尘/ 2022年05月31日 10:53/ 0 赞/ 148 阅读

相关详解两个队列实现一个栈（python实现——经典面试题）

1、任务详解使用两个队列数据结构实现一个栈，要求实现栈的出栈和进栈操作。 2、解题思路 push()操作：为了保证先进栈的元素一直在栈底，需要将两个队列交替

╰+哭是因爲堅強的太久メ/ 2022年05月14日 05:17/ 0 赞/ 96 阅读

相关详解两个栈实现一个队列（python实现——经典面试题）

1、题目说明使用两个栈结构，实现一个队列功能，实现队列的添加元素和弹出元素。注意：队列特点是只能在队列尾部添加元素，在队列头部删除元素，先进先出（FIFO/LI

旧城等待，/ 2022年05月14日 05:12/ 0 赞/ 153 阅读

相关两个队列实现一个栈+两个栈实现一个队列（Java 实现）

两个队列实现一个栈 1. 现有两个队列 q1 和 q2，入栈则将元素加到 q1 2. 出栈的时候先判读 q1 是否为空，因为 q1 中的元素总是后进来的，后进先出，除

浅浅的花香味﹌/ 2022年03月06日 03:18/ 0 赞/ 273 阅读

相关栈/两个栈实现一个队列

Java实现 / @auther: 巨未 @DATE: 2019/1/5 0005 18:29 @Descripti

た入场券/ 2021年09月23日 07:02/ 0 赞/ 373 阅读

相关队列/两个队列实现一个栈

顺序队列的实现 / @auther: 巨未 @DATE: 2019/1/5 20:17 @Description: 顺序队列

谁践踏了优雅/ 2021年09月23日 07:02/ 0 赞/ 367 阅读