首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列

热度指数：1009534 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： $n\le1000$

要求：存储n个元素的空间复杂度为 $O(n)$ ，插入与删除的时间复杂度都是 $O(1)$

示例1

输入

["PSH1","PSH2","POP","POP"]

输出

1,2

说明

"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

示例2

输入

["PSH2","POP","PSH1","POP"]

输出

2,1

算法知识视频讲解

查看答案及解析

推荐

张佃鹏

class Solution
{
public:
    void push(int node) {
       stack1.push(node); 
    }

    int pop() {
        int a;
        if(stack2.empty()){
            while(!stack1.empty()){
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
        
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

用两个栈实现一个队列的功能?要求给出算法和思路!

<分析>：

入队：将元素进栈A

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；

如果不为空，栈B直接出栈。

用两个队列实现一个栈的功能?要求给出算法和思路!

<分析>：

入栈：将元素进队列A

出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列以此放入队列A中。

编辑于 2015-08-18 23:15:03 回复(73)

Python

scau_lidakun

第二个栈通过第一个栈转换成队列，关键在于pop的时候，如果第二个栈不为空，先把第二个栈的pop出
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)

def pop(self):
# return xx
if len(self.stack2) != 0:
return self.stack2.pop(-1)
else:
self.daozhi()
if len(self.stack2) == 0:
return None
else:
return self.stack2.pop()
def daozhi(self):
if len(self.stack1) != 0:
for i in range(len(self.stack1)):
self.stack2.append(self.stack1.pop(-1))

发表于 2021-05-25 18:57:47 回复(0)

Python

牛客214508586号

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA=[]
        self.stackB=[]
    def push(self, node):
        self.stackA.append(node)
            
        # write code here
    def pop(self):
        if not self.stackB:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
        return self.stackB.pop()
        # return xx

定义两个栈：1.队尾栈stackA 2.队头栈stackB

1.队列压入只需要对队尾栈stackA进行append，时间复杂度为O(1)

2.队头取出操作：须进行一个判断，队头栈是否为空（说明队头栈尚未被压入值，或者已执行过n次取出操作将队头栈取空了）且队尾栈是否有值，通过类似汉诺塔问题的解决思路，将队尾栈数据倒序送入队头栈

发表于 2021-04-19 20:55:38 回复(0)

Python

牛客771940155号

py中没有栈的数据结构，使用列表模拟。栈A始终保持从栈底到栈顶和队列顺序一致，栈B是入栈的辅助空间。下面的出栈入栈操作随影到列表的pop() 和append()

两个栈模拟队列的push pop操作，栈A为空push操作直接入栈，pop操作返回空。栈A不为空时
push操作：将栈A元素依次出栈**栈栈B，然后将push元素入栈A，再将栈B元素依次出栈**栈A
pop操作：栈A直接出栈

发表于 2021-04-10 23:57:49 回复(0)

Python

牛客313692148号

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack_in = []
self.stack_out = []

def push(self, node):
# write code here
self.stack_in.append(node)
def pop(self):
# return xx
if self.stack_out:
return self.stack_out.pop()
while self.stack_in:
temp = self.stack_in.pop()
self.stack_out.append(temp)
return self.stack_out.pop()

发表于 2021-03-29 15:30:27 回复(0)

Python

想玩飞盘的六边形战士正在背八股

# -*- coding:utf-8 -*-
class Solution:
    
    def __init__(self):
        self.stack1 = [] # 入栈
        self.stack2 = [] # 出栈
    
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        # 如果出栈的没有值，先把入栈的数据全部拿过去
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        # 出栈的数据弹出
        return self.stack2.pop()

发表于 2021-03-27 10:44:41 回复(0)

Python

食堂在逃干饭王

定义栈a和栈b，push时全部push到栈a中，pop时，若栈b不为空，则直接pop栈b的栈顶元素，否则将栈a的全部元素依次push到栈b后，再对栈b进行pop。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.a = []
        self.b = []
    def push(self, node):
        self.a.append(node)
    def pop(self):
        if len(self.b) > 0:
            return self.b.pop()
        while(len(self.a) > 0):
            self.b.append(self.a.pop())
        return self.b.pop()

发表于 2021-02-07 19:20:45 回复(0)

Python

MingCode

"""
Python3 用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
思路：
栈A用来作入队列
栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）
在Python环境下，原生的list即为一个栈实现，我们直接通过定义两个list即可定义出两个栈：
1、首先要明确队列的特性是先进先出，栈的特性是先进后出；
2、A进队列的方法里我们只要有容器能装元素就行了，所以直接往栈1里压；
3、在出队列方法B里，要保证出队列的是最先进入的元素：

4、在往栈2压完一批元素后，栈1进了新的元素想往栈2压的时候，栈2必须把上一批的元素清空了才行(也就是栈2必须是空的)。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = [] # 入栈
        self.stack2 = [] # 出栈
    def push(self, node):
        # write code here
        self.stack1.append(node) # 入值
    def pop(self):
        # return xx
        if self.stack2 == []: # 将入栈存入B栈
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2021-01-17 19:04:48 回复(0)

Python

喜欢疯狂星期四的牛牛准备进厂

class Solution:
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, node):
self.s1.append(node)
def pop(self):
if len(self.s2) == 0:
for _ in range(len(self.s1)):
self.s2.append(self.s1.pop())

return self.s2.pop()

s1一直入栈，s2一直出栈，时间复杂度均为O(1)

发表于 2020-11-22 16:13:43 回复(0)

Python

杰杰201911092306272

解题思路： 1、初始化两个栈，list实现； 2、push操作直接往栈1append元素； 3、pop操作分两种情况：1、如果栈2不空，则栈2出栈；2、如果栈2为空，则将栈1所有元素出栈，然后写入栈2后，再将栈2元素出栈。
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if self.stack2:
            return self.stack2.pop()
        elif not self.stack1:
            return None
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

发表于 2020-10-27 15:41:52 回复(0)

Python

酒鬼考拉

Python3 两个栈，zhan1用于存放，zhan2用于输出。

push()

1.将zhan1清空，将zhan2元素遍历放入zhan1

2.再将新元素append到zhan1

3.再更新zhan2(将新的zhan1遍历放入zhan2)

pop()

1.将zhan2清空，将zhan1元素遍历放入zhan2

2.取得并删除zhan2[0]

3.再更新zhan1(将新的zhan2遍历放入zhan1)

4.返回zhan2[0]

class Solution:
    def __init__(self):
        self.zhan1 = []
        self.zhan2 = []
    def push(self, node):
        self.zhan2_to_zhan1()
        self.zhan1.append(node)
        self.zhan1_to_zhan2()
    def pop(self):
        self.zhan1_to_zhan2()
        r = self.zhan2[0]
        del self.zhan2[0]
        self.zhan2_to_zhan1()
        return r
    def zhan1_to_zhan2(self):
        self.zhan2.clear()
        for i in self.zhan1:
            self.zhan2.append(i)
    def zhan2_to_zhan1(self):
        self.zhan1.clear()
        for i in self.zhan2:
            self.zhan1.append(i)

发表于 2020-09-16 23:59:59 回复(0)

Python

LV52

这题出的有问题吧，直接写一个队列的实现就完事了啊，哪有栈什么事。

发表于 2020-08-21 11:09:00 回复(0)

Python

莱布尼兹的n+3阶

对python好像很不友好，因为对于java而言可以直接导入stack，但python没有，那么就要先自己定义生成stack才能继续了(实际上把list安装栈来出栈入栈就好了）

如果直接使用list来操作很简单(但显然不满足题目要求)

```python

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.items = []
def push(self, node):
return self.items.insert(0,node)
def pop(self):
return self.items.pop()
```

所以需要用两个list表示栈（也就是要把这里的list当成stack使用，即“先进后出”）

```

class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
#将stack1全部放入stack2中
if self.stack2 == []:
while self.stack1 != []:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

```

发表于 2020-07-29 16:56:30 回复(0)

Python

牛客1349号

python实现

一个队列实现,也能过。。。

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.res_list = []
    def push(self, node):
        # write code here
        self.res_list.append(node)
    def pop(self):
        # return xx
        if self.res_list:
            res = self.res_list.pop(0)
            return res

两个队列实现

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.res_list1 = []
        self.res_list2 = []
    def push(self, node):
        # write code here
        self.res_list1.append(node)
    def pop(self):
        # return xx
        if self.res_list2:
            res = self.res_list2.pop()
            return res
        if not self.res_list1:
            return
        if self.res_list1:
            while self.res_list1:
                self.res_list2.append(self.res_list1.pop())
            
            res = self.res_list2.pop()
            return res

发表于 2020-07-27 00:57:12 回复(0)

Python

DDooo

class Solution:
    def __init__(self):
        self.s1 = [] 
        self.s2 = []
        
    def push(self, node):
        self.s1.append(node)
        
    def pop(self):
        if self.s2 == []:
            while self.s1 :
                a = self.s1.pop()
                self.s2.append(a)
        return self.s2.pop()

需要注意的几点：

1，

if self.s2==[]

此句判断栈2是否为空

2，

定义的函数pop里面调用的pop是库函数，而定义的pop是队列的pop函数。

3，

最后一句

return self.s2.pop()

是s2不为空则执行的语句。

发表于 2020-07-22 10:16:13 回复(0)

Python

橘子汽水超人2号

Python Solution

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA=[]
        self.stackB=[]
    def push(self, node):
        self.stackA.append(node)
    def pop(self):
        if self.stackB:
            tmp = self.stackB[-1]
            del self.stackB[-1]
            return tmp
        elif not self.stackA: return 'None'
        else: # 把栈A中的全部放入B中，再取其中一个
            while self.stackA:
                self.stackB.append(self.stackA[-1])
                del self.stackA[-1]
            return self.pop()

编辑于 2020-05-30 17:45:12 回复(0)

Python

BurNIng_TTTTTT

还栈、队的，Python的list不是随便解决这问题吗？？？sjbb

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1 = list()

    def push(self, node):
        # write code here
        self.s1.append(node)
    def pop(self):
        # return xx
        aa = self.s1[0]
        del self.s1[0]
        return aa

编辑于 2020-06-19 15:28:30 回复(0)

Python

Newkerrr

class Solution:
    def __init__(self):
        self.a=[]
    def push(self, node):
        self.a.append(node)
        # write code here
    def pop(self):
        return self.a.pop(0)

发表于 2020-03-26 16:23:39 回复(1)

Python

落汐

Python语言，做法是利用类属性，所有该类实例都可以共享列表L

# -*- coding:utf-8 -*-

class Solution:
L=[]
def push(self, node):
Solution.L.append(node)
def pop(self):
return Solution.L.pop(0)

编辑于 2020-03-09 17:18:24 回复(0)

Python

还是搬砖吧

无比对称，完美通过！

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
         
    def push(self, node):
        (1489)# write code here
        while self.stackB != []:
            self.stackA.append(self.stackB.pop())
        return self.stackA.append(node)
        
    def pop(self):
        # return xx
        while self.stackA != []:
            self.stackB.append(self.stackA.pop())
        return self.stackB.pop()

发表于 2020-03-05 20:58:35 回复(0)

Python

vammm

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.sa=[]
        self.sb=[]
    def push(self, node):
        (1413)# write code here
        self.sa.append(node)
        
    def pop(self):
        # return xx
        if len(self.sa)==0:
            return None
        while len(self.sa)!=1:
            self.sb.append(self.sa.pop())
        renum=self.sa.pop()
        if len(self.sb)>0:
            self.sa.append(self.sb.pop())
        return renum

发表于 2020-03-05 11:02:17 回复(0)

提交观点

问题信息

栈

难度：

92条回答 2819收藏 319049浏览

通过挑战的用户

查看代码

牛客60976...

2023-02-03 16:09:26
牛客30382...

2022-12-23 15:32:22
brucesun42

2022-11-27 11:15:39
幸运的打工人一...

2022-11-15 15:15:23
牛客29768...

2022-11-14 11:41:38

用两个栈实现队列

输入

输出

说明

输入

输出

push()

pop()

Python Solution

问题信息

热门推荐

通过挑战的用户

相关试题