Stacks#

Stack（堆栈）是一种线性数据结构，其操作遵循先进后出（LIFO），后进先出（FILO）的原则。

Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

../_images/stacks.png

operations#

下面是每个操作的基本描述和时间复杂度分析：

  • 入栈（push）操作：将元素压入栈顶。时间复杂度：O(1)

  • 出栈（pop）操作：从栈顶弹出元素。时间复杂度：O(1)

  • 查看栈顶元素（peek）操作：返回栈顶元素，但不弹出。时间复杂度：O(1)

  • 判断栈是否为空（isEmpty）操作：判断栈是否为空。时间复杂度：O(1)

 1class Stack:
 2    def __init__(self):
 3        self.items = []
 4
 5    def push(self, item):
 6        self.items.append(item)
 7
 8    def pop(self):
 9        if not self.is_empty():
10            return self.items.pop()
11
12    def peek(self):
13        if not self.is_empty():
14            return self.items[-1]
15
16    def is_empty(self):
17        return len(self.items) == 0
18
19    def size(self):
20        return len(self.items)