type
status
date
slug
summary
tags
category
icon
password
一道简单题,使用队列实现栈,主要思想就是使用双队列一个用作对外展现,另一个用于对内的栈的实现。
📝 题目描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(
push
、top
、pop
和 empty
)。实现
MyStack
类:void push(int x)
将元素 x 压入栈顶。
int pop()
移除并返回栈顶元素。
int top()
返回栈顶元素。
boolean empty()
如果栈是空的,返回true
;否则,返回false
。
注意:
- 你只能使用队列的基本操作 —— 也就是
push to back
、peek/pop from front
、size
和is empty
这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 2, 2, false] 解释: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
🤗 实现
首先对于对于数据结构的描述:
对于
top
、empty
、pop
方法直接使用队列库中的方法即可:接下来就是stack实现的最重要部分
push
操作:push
操作首目的是向stack
尾部插入数据,即这个queue1
的头部,但是队列无法直接从头部插入,于是我们使用queue2
,先将要插入的数据放入queue2
中,然后再将queue1
中的数据倒入queue2
中,于是实现了插入队列头部,但是我们要将queue1
作为对外展现的队列,于是将queue1
与queue2
交换。📎 参考文章
- c++ STL库文档:
- leetcode官方题解:
- Author:灵檠
- URL:https://blog.ly-qing.lol/article/aab435e2-29e6-493c-af6d-99af011a0c7f
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts