人工智能之编程进阶 Python高级：第一章 栈和队列

# 创建一个栈
stack = []

# 压栈（push）—— 使用 append()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # [1, 2, 3]

# 弹栈（pop）—— 使用 pop()（默认弹出最后一个）
top = stack.pop()
print(top)    # 3
print(stack)  # [1, 2]

# 查看栈顶（不弹出）
if stack:
    top = stack[-1]
    print("栈顶:", top)  # 2

# 判断栈是否为空
if not stack:
    print("栈为空")

def is_valid_parentheses(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in '([{':
            stack.append(char)  # 左括号入栈
        else:
            if not stack or stack.pop() != pairs[char]:
                return False    # 不匹配
    return not stack  # 栈空则匹配成功

print(is_valid_parentheses("([{}])"))  # True
print(is_valid_parentheses("([)]"))    # False

queue = []

# 入队（在尾部添加）—— O(1)
queue.append('A')
queue.append('B')
queue.append('C')

# 出队（从头部弹出）—— O(n) ❌ 低效！
first = queue.pop(0)  # 删除并返回第一个元素

from collections import deque

# 创建队列
queue = deque()

# 入队（尾部添加）—— O(1)
queue.append('A')
queue.append('B')
queue.append('C')

# 出队（头部弹出）—— O(1)
first = queue.popleft()
print(first)  # 'A'
print(queue)  # deque(['B', 'C'])

# 查看队首（不弹出）
if queue:
    front = queue[0]
    print("队首:", front)  # 'B'

# 判断队列是否为空
if not queue:
    print("队列为空")

from queue import Queue

q = Queue()
q.put('A')      # 入队
q.put('B')
item = q.get()  # 出队（阻塞式）
print(item)     # 'A'

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            # 将邻居加入栈（顺序影响遍历方向）
            stack.extend(reversed(graph[node]))

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node])

# 自定义栈类
class Stack:
    def __init__(self):
        self._items = []
    
    def push(self, item):
        self._items.append(item)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()
    
    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)

# 自定义队列类
from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()
    
    def enqueue(self, item):
        self._items.append(item)
    
    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    
    def front(self):
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self._items[0]
    
    def is_empty(self):
        return len(self._items) == 0
    
    def size(self):
        return len(self._items)