由两个栈组成的队列

[编程题]由两个栈组成的队列

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

用两个栈实现队列，支持队列的基本操作。

输入描述:

第一行输入一个整数N，表示对队列进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。

如果S为"poll"，则表示弹出队列头部操作。

如果S为"peek"，则表示询问当前队列中头部元素是多少。

输出描述:

对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。

示例1

输入

6
add 1
add 2
add 3
peek
poll
peek

输出

1
2

备注:

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

算法知识视频讲解

Python 3

毓毓子最可爱

《程序员代码面试指南》Python题解 https://zhuanlan.zhihu.com/p/444550262

class MyQueue:
    def __init__(self):
        # 栈A用来存放数据的
        self.stack_A = []
        # 栈A中的数据数
        self.num_A = 0
        # 栈B用来存放栈A中的数据
        self.stack_B = []
        # 栈B中的数据数
        self.num_B = 0

    # 存放数据
    def add(self, x):
        # 将x放入栈A中
        self.stack_A.append(x)
        self.num_A += 1

    # 将栈A中的数据全部放入栈B中
    def A2B(self):
        # 只有栈B中没有数据时
        # 才将栈A中的数据放入
        # 否则的话直接弹出栈B中的数据即可
        if self.num_B == 0:
            while self.num_A > 0:
                self.stack_B.append(self.stack_A.pop())
                # 更新
                self.num_B += 1
                self.num_A -= 1

    # 获取队头元素
    def peek(self):
        self.A2B()
        if self.num_B > 0:
            return self.stack_B[-1]
        else:
            return None

    # 弹出队列头部元素
    def poll(self):
        self.A2B()
        # 元素个数减1
        self.num_B -= 1
        return self.stack_B.pop()


# 操作次数
n = int(input())
# 自己定义的由两个栈组成的队列
myqueue = MyQueue()
for i in range(n):
    # 操作字符串
    operator = input().split()
    if operator[0] == 'add':
        myqueue.add(operator[1])
    elif operator[0] == 'peek':
        print(myqueue.peek())
    elif operator[0] == 'poll':
        myqueue.poll()

发表于 2021-12-14 09:08:15 回复(0)