Skip to content

Commit bdb8eab

Browse files
committed
栈与队列
栈与队列
1 parent 1e657ec commit bdb8eab

7 files changed

Lines changed: 36 additions & 38 deletions

File tree

leetcode_stack/main.md

Lines changed: 15 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,19 @@
1-
## LeetCode栈
1+
# LeetCode栈与队列
2+
## 1.定义
3+
#### 队列
4+
队列是一种先进先出的线性表(FIFO:First In First Out),它只允许在表的前端进行删除操作,在表的后端进行插入操作。
5+
6+
![](../pic/leetcode_stack/duilie.png)
7+
8+
####
9+
栈是一种后进先出的线性表(LIFO:Last In First Out),它只允许在表尾部进行插入和删除操作。
10+
11+
![](../pic/leetcode_stack/stack.png)
12+
13+
## 2.题目
214
* [有效的括号](有效的括号.md)
15+
* [用栈实现队列](用栈实现队列.md)
16+
* [用队列实现栈](用队列实现栈.md)
317

418
<!--
519
2. [最小栈](最小栈.md)
Lines changed: 12 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
## 用栈实现队列
1+
# 232.用栈实现队列
2+
## 题目
23
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push、pop、peek、empty):
34

45
实现 MyQueue 类:
@@ -16,44 +17,36 @@
1617
* 出栈,入栈顺序,4,3,2,1, 出栈顺序1,2,3,4,
1718
* 正好两个栈的顺序结合效果等于队列的顺序
1819

20+
![](../pic/leetcode_stack/232_1.gif)
21+
1922
```python
2023
class MyQueue:
2124

2225
def __init__(self):
23-
"""
24-
Initialize your data structure here.
25-
"""
2626
self.stack_in = [] # 入栈
2727
self.stack_out = [] # 出栈
2828

2929
def push(self, x: int) -> None:
30-
"""
31-
Push element x to the back of queue.
32-
"""
30+
# 往队列中添加元素
3331
self.stack_in.append(x)
3432

3533
def pop(self) -> int:
36-
"""
37-
Removes the element from in front of queue and returns that element.
38-
"""
39-
self.peek()
34+
# 从队列中取出一个元素
35+
if not self.stack_out:
36+
self.stack_out = self.stack_in[::-1]
37+
self.stack_in = []
4038
return self.stack_out.pop()
4139

4240
def peek(self) -> int:
43-
"""
44-
Get the front element.
45-
"""
41+
# 获取队列的头部
4642
if not self.stack_out:
4743
self.stack_out = self.stack_in[::-1]
4844
self.stack_in = []
4945
return self.stack_out[-1]
5046

5147
def empty(self) -> bool:
52-
"""
53-
Returns whether the queue is empty.
54-
"""
55-
if self.stack_in or self.stack_out:
48+
# 判断队列是否为空
49+
if self.stack_out or self.stack_in:
5650
return False
5751
return True
58-
5952
```
Lines changed: 9 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
## 用队列实现栈
1+
# 225.用队列实现栈
2+
## 题目
23
使用队列实现栈的下列操作:
34
* push(x) -- 元素 x 入栈
45
* pop() -- 移除栈顶元素
@@ -8,33 +9,28 @@
89
## 代码
910
* 队列先进先出
1011
* 栈后进先出
11-
* 一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了。
12+
* 一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了
13+
14+
![](../pic/leetcode_stack/225_1.gif)
1215

1316
```python
1417
from queue import Queue
1518

1619
class MyStack:
1720

1821
def __init__(self):
19-
"""
20-
Initialize your data structure here.
21-
"""
2222
self.stack = Queue()
2323
self.top_ele = None
2424

2525

2626
def push(self, x: int) -> None:
27-
"""
28-
Push element x onto stack.
29-
"""
27+
# 入栈
3028
self.stack.put(x)
3129
self.top_ele = x
3230

3331

3432
def pop(self) -> int:
35-
"""
36-
Removes the element on top of the stack and returns that element.
37-
"""
33+
# 弹栈
3834
size = self.stack.qsize()
3935
while size > 1:
4036
ele = self.stack.get()
@@ -46,18 +42,13 @@ class MyStack:
4642

4743

4844
def top(self) -> int:
49-
"""
50-
Get the top element.
51-
"""
45+
# 获取栈顶元素
5246
return self.top_ele
5347

5448

5549
def empty(self) -> bool:
56-
"""
57-
Returns whether the stack is empty.
58-
"""
50+
# 栈是否为空
5951
if self.stack.qsize():
6052
return False
6153
return True
62-
6354
```

pic/leetcode_stack/225_1.gif

22.1 MB
Loading

pic/leetcode_stack/232_1.gif

194 KB
Loading

pic/leetcode_stack/duilie.png

30.5 KB
Loading

pic/leetcode_stack/stack.png

4.75 KB
Loading

0 commit comments

Comments
 (0)