首页 > 试题广场 >

用两个栈实现队列

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

热度指数：1023304 时间限制：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)

Python3

蒲公英的朝暮

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

class Solution:

def __init__(self):

self.stack1 = []

self.stack2 = []

def push(self, node):

# write code here

# 原则是push后要保留一个stack为空, 入队操作的对象始终是stack1

self.stack1.append(node)

def pop(self):

# return xx

size1 = len(self.stack1)

size2 = len(self.stack2)

# stack2中自顶向下的元素顺序与入队顺序一致, stack1中则相反

# stack2不为空时, 优先从stack2弹栈

if size2 > 0:

return self.stack2.pop()

elif size1 > 0:

# 借助已经为空的stack2, 从stack1进行弹栈操作

for i in range(size1-1):

self.stack2.append(self.stack1.pop())

return self.stack1.pop()

else:

return None

发表于 2025-01-27 17:50:46 回复(0)

Python3

牛客418952426号

class Solution:

def __init__(self):

self.stack = []

self.stack2 = []

def push(self, node):

self.stack.append(node)

def pop(self):

if not self.stack2:

while self.stack:

self.stack2.append(self.stack.pop())

if self.stack2:

return self.stack2.pop()

else:

raise IndexError("pop from empty stack")

if __name__ == "__main__":

s = Solution()

s.push(1)

s.push(2)

s.push(3)

print(s.pop())

发表于 2025-01-17 21:15:10 回复(0)

Python3

阿巴阿巴___

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
        self.stack2 = self.stack1[::-1]
    def pop(self):
        # return xx
        result = self.stack2.pop()
        self.stack1 = self.stack2[::-1]
        return result

发表于 2024-09-15 20:53:25 回复(0)

Python3

牛客997458500号

# -*- 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):
        while self.stack1:
            self.stack2.append(self.stack1.pop(0))
        return self.stack2.pop(0)

发表于 2024-08-06 17:12:25 回复(0)

Python3

川流不息憨憨

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        # write code here
        if not self.stack1:
            self.stack1.append(node)
            self.stack1.extend(self.stack2)
            self.stack2.clear()
        elif not self.stack2:
            self.stack2.append(node)
            self.stack2.extend(self.stack1)
            self.stack1.clear()
    def pop(self):
        if self.stack1:
            return self.stack1.pop()
        elif self.stack2:
            return self.stack2.pop()

编辑于 2024-03-18 20:34:09 回复(0)

Python3

可道非常道

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []  # 用于插入操作
        self.stack2 = []  # 用于删除操作
    
    def push(self, node):
        self.stack1.append(node)  # 将元素插入到stack1中
    
    def pop(self):
        if not self.stack2:  # 如果stack2为空，则将stack1中的元素逐个弹出并压入stack2，实现对元素的逆序
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()  # 弹出stack2的栈顶元素，实现对队列头部的删除操作

发表于 2023-10-18 10:29:12 回复(0)

Python3

殁月呀

class Solution:

def __init__(self):

self.stack1 = []

self.stack2 = []

def push(self, node):

# write code here

self.stack1.append(node)

self.stack2.append('爱干嘛干嘛！')

def pop(self):

# return xx

return self.stack1.pop(0)

发表于 2023-08-26 09:35:55 回复(0)

Python3

pzq

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if len(self.stack2) == 0:
            while self.stack1:
                val = self.stack1.pop(-1)
                self.stack2.append(val)
        return self.stack2.pop(-1)

发表于 2023-06-15 00:15:04 回复(0)

Python3

Lxyapc

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

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    # 使用python list 当作栈来使用，则 append 和 pop对最尾的元素进行压栈出栈操作
    # 当然对list 使用pop(0), insert 之类的操作更简单，但是与栈无关。
    # stack1 : 正常的数据表， 
    # stack2 : 倒装的数据表，
    # 且上述两个表中只有一个有效，另一个为空。
    # 题中给出数据范围： n<=1000, 输出9999表示数据为空()。


    def peek(self):    # 既然是实现队列，顺手写一个peek()
        if not self.stack2:  # 如果倒装数据为空，构建倒装数据栈
            while (self.stack1):
                self.stack2.append(self.stack1.pop())       
        return self.stack2[len(self.stack2)-1] if self.stack2 else 9999


    def push(self, node):  # 维护正向数据，数据入列
        if not self.stack1:   # 如果正向数据为空，把倒装数据装回来
            while (self.stack2):
                self.stack1.append(self.stack2.pop())     
        self.stack1.append(node)  # 加入新的数据


    def pop(self): # 维护倒装数据，数据出列
        self.peek() 
        return self.stack2.pop() if self.stack2 else 9999

发表于 2023-02-28 00:19:42 回复(0)

Python3

你需要至高之拳

# -*- 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 len(self.stack2)==0: #没有的情况下要转换，有的情况下先把stack2删完再转换
while len(self.stack1)!=0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

发表于 2023-02-21 16:02:48 回复(0)

Python3

~根本停不下来~

# -*- 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

# for i in range(len(self.stack1)):

# self.stack2.append(self.stack1.pop())

# res = self.stack2.pop()

# for i in range(len(self.stack2)):

# self.stack1.append(self.stack2.pop())

return self.stack1.pop(0)

发表于 2022-09-24 10:49:49 回复(0)

Python3

mgxjq

为啥一堆直接pop(0)的, 你能pop(0)就不是stack了啊

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:
while (len(self.stack1) != 0):
self.stack2.append(self.stack1.pop())
value = self.stack2.pop()
return value

发表于 2022-01-09 15:23:12 回复(3)

Python3

henryboy233

# -*- 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 self.stack1.pop(0)
        # return xx

发表于 2021-12-09 22:10:32 回复(0)

Python3

小小小小燃

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:
            for item in self.stack1[::-1]:
                self.stack2.append(self.stack1.pop())
        
        return self.stack2.pop()

发表于 2021-11-15 19:47:27 回复(0)

Python3

网易内推offer小助手

# -*- coding:utf-8 -*-
class Solution:
    '''
    1.当插入时，直接插入 stack1
    2.当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，
    如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，
    再弹出 stack2 栈顶元素
    '''
    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:
            while(len(self.stack1)!=0):
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2021-09-26 15:45:36 回复(0)

Python3

牛客338194879号

# -*- 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
        while len(self.stack1)!=0:
            item = int(self.stack1[0])
            self.stack2.append(item)
            self.stack1.pop(0)
        r = self.stack2[0]
        self.stack2.pop(0)
        return r

发表于 2021-08-31 21:02:13 回复(0)

Python3

可恶，被他装到了

class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []

def push(self, node):
# write code here
self.stack1.append(node)

def pop(self):
if len(self.stack1) > 0:
pop_value = int(self.stack1[0])
del self.stack1[0]
return pop_value
else:
return None

发表于 2021-08-11 16:09:07 回复(1)