一、栈
栈（stack）是一种遵循先入后出逻辑的线性数据结构。
1、栈的常用操作
| 方法 |
描述 |
时间复杂度 |
push() |
元素入栈（添加至栈顶） |
O(1) |
pop() |
栈顶元素出栈 |
O(1) |
peek() |
访问栈顶元素 |
O(1) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
stack: list[int] = []
stack.append(1)
stack.append(2)
stack.append(3)
peek: int = stack[-1]
pop: int = stack.pop()
size: int = len(stack)
is_empty: bool = size == 0
stack: list[int] = []
stack.append(1)
stack.append(2)
stack.append(3)
peek: int = stack[-1]
pop: int = stack.pop()
size: int = len(stack)
is_empty: bool = size == 0
class LinkedListStack:
"""基于链表实现栈操作"""
def __init__(self):
"""构造函数"""
self._peek: ListNode | None = None
self._size: int = 0
def size(self) -> int:
"""栈的长度"""
return self._size
def is_empty(self) -> bool:
"""栈是否为空"""
return self._size == 0
def push(self, val: int):
"""入栈"""
node = ListNode(val)
node.next = self._peek
self._peek = node
self._size += 1
def pop(self) -> int:
"""出栈"""
num = self.peek()
self._peek = self._peek.next
self._size -= 1
return num
def peek(self) -> int:
"""获取栈顶元素"""
if self.is_empty():
raise IndexError("栈为空")
return self._peek.val
def to_list(self) -> list[int]:
"""转化为列表"""
arr = []
node = self._peek
while node:
arr.append(node.val)
node = node.next
arr.reverse()
return arr
|
2、栈的典型应用
- 浏览器中的后退和前进，软件中的撤销和反撤销
- 程序内存管理。
二、队列
队列（queue）是一种遵循先入先出规则的线性数据结构。
1、队列的常用操作
| 方法名 |
描述 |
时间复杂度 |
push() |
元素入队，即将元素添加至队尾 |
O(1) |
pop() |
队首元素出队 |
O(1) |
peek() |
访问队首元素 |
O(1) |
2、队列典型应用
三、双向队列
双向队列（double-ended queue）提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。
1、双向队列常用操作
| 方法名 |
描述 |
时间复杂度 |
push_first() |
将元素添加至队首 |
O(1) |
push_last() |
将元素添加至队尾 |
O(1) |
pop_first() |
删除队首元素 |
O(1) |
pop_last() |
删除队尾元素 |
O(1) |
peek_first() |
访问队首元素 |
O(1) |
peek_last() |
访问队尾元素 |
O(1) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| from collections import deque
deq: deque[int] = deque()
deq.append(2)
deq.append(5)
deq.append(4)
deq.appendleft(3)
deq.appendleft(1)
front: int = deq[0]
rear: int = deq[-1]
pop_front: int = deq.popleft()
pop_rear: int = deq.pop()
size: int = len(deq)
is_empty: bool = len(deq) == 0
class ListNode:
"""双向链表节点"""
def __init__(self, val: int):
"""构造方法"""
self.val: int = val
self.next: ListNode | None = None
self.prev: ListNode | None = None
class LinkedListDeque:
"""基于双向链表实现的双向队列"""
def __init__(self):
"""构造方法"""
self._front: ListNode | None = None
self._rear: ListNode | None = None
self._size: int = 0
def size(self) -> int:
"""获取双向队列的长度"""
return self._size
def is_empty(self) -> bool:
"""判断双向队列是否为空"""
return self._size == 0
def push(self, num: int, is_front: bool):
"""入队操作"""
node = ListNode(num)
if self.is_empty():
self._front = self._rear = node
elif is_front:
self._front.prev = node
node.next = self._front
self._front = node
else:
self._rear.next = node
node.prev = self._rear
self._rear = node
self._size += 1
def push_first(self, num: int):
"""队首入队"""
self.push(num, True)
def push_last(self, num: int):
"""队尾入队"""
self.push(num, False)
def pop(self, is_front: bool) -> int:
"""出队操作"""
if self.is_empty():
raise IndexError("双向队列为空")
if is_front:
val: int = self._front.val
fnext: ListNode | None = self._front.next
if fnext != None:
fnext.prev = None
self._front.next = None
self._front = fnext
else:
val: int = self._rear.val
rprev: ListNode | None = self._rear.prev
if rprev != None:
rprev.next = None
self._rear.prev = None
self._rear = rprev
self._size -= 1
return val
def pop_first(self) -> int:
"""队首出队"""
return self.pop(True)
def pop_last(self) -> int:
"""队尾出队"""
return self.pop(False)
def peek_first(self) -> int:
"""访问队首元素"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._front.val
def peek_last(self) -> int:
"""访问队尾元素"""
if self.is_empty():
raise IndexError("双向队列为空")
return self._rear.val
def to_array(self) -> list[int]:
"""返回数组用于打印"""
node = self._front
res = [0] * self.size()
for i in range(self.size()):
res[i] = node.val
node = node.next
return res
|
2、双向队列应用
双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
