1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 9-2 题] “用队列实现栈”做题记录

[剑指 Offer 第 2 版第 9-2 题] “用队列实现栈”做题记录

第 9-2 题:用队列实现栈

同 LeetCode 第 225 题。

传送门:225. 用队列实现栈

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

  • push(x) — 元素 x 入栈
  • pop() — 移除栈顶元素
  • top() — 获取栈顶元素
  • empty() — 返回栈是否为空

注意:

  • 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

Python 代码:

  class MyStack:

        def __init__(self):
            """
            Initialize your data structure here.
            """

            self.queue = []

        def push(self, x):
            """
            Push element x onto stack.
            :type x: int
            :rtype: void
            """
            self.queue.append(x)
            # 将队列中前面已经逆序的元素放在 x 元素后面,使得整体逆序
            for _ in range(len(self.queue) - 1):
                ele = self.queue.pop(0)
                self.queue.append(ele)

        def pop(self):
            """
            Removes the element on top of the stack and returns that element.
            :rtype: int
            """
            if self.queue:
                return self.queue.pop(0)

        def top(self):
            """
            Get the top element.
            :rtype: int
            """
            if self.queue:
                return self.queue[0]

        def empty(self):
            """
            Returns whether the stack is empty.
            :rtype: bool
            """
            return len(self.queue) == 0

    # Your MyStack object will be instantiated and called as such:
    # obj = MyStack()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.empty()

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 9-2 题] “用队列实现栈”做题记录

链接:https://www.javajike.com/article/3309.html

« [剑指 Offer 第 2 版第 9-1 题] “用两个栈实现队列”做题记录
[剑指 Offer 第 2 版第 15 题] “二进制中1的个数”做题记录»

相关推荐

QR code