一、栈
栈(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、双向队列应用
双向队列兼具栈与队列的逻辑,因此它可以实现这两者的所有应用场景,同时提供更高的自由度。