栈和队列的主要区别

一、栈和队列的基本介绍

栈（Stack）和队列（Queue）是两种经典的数据结构，用于在计算机程序中存储和管理数据。栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。队列是一种先进先出（FIFO）的数据结构，只允许在队列尾部进行插入操作，在队列头部进行删除操作。

下面是栈和队列的简单Python代码实现：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def is_empty(self):
        return len(self.items) == 0

二、基本操作的差异

栈和队列的主要区别在于它们的基本操作。在栈中，元素的插入和删除只能在栈顶进行，而队列中元素的插入只能在队列尾部进行，删除操作则只能在队列头部进行。这意味着在栈中最后插入的元素会被最先删除，而在队列中最先插入的元素会被最先删除。

下面是分别实现了栈和队列的基本操作代码：

# 栈
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0


# 队列
class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def is_empty(self):
        return len(self.items) == 0

三、性能差异

栈和队列的另一个主要区别是它们的性能差异。在栈中，插入和删除操作的时间复杂度都是O(1)，因为只需要操作栈顶的元素。而在队列中，插入操作的时间复杂度也是O(1)，但删除操作的时间复杂度为O(n)，因为需要将所有的元素向前移动一位。

下面是分别实现了栈和队列的性能比较代码：

import time

# 栈
s = Stack()
start = time.time()
for i in range(1000000):
    s.push(i)
while not s.is_empty():
    s.pop()
end = time.time()
print("Time used for Stack:", end-start)

# 队列
q = Queue()
start = time.time()
for i in range(1000000):
    q.enqueue(i)
while not q.is_empty():
    q.dequeue()
end = time.time()
print("Time used for Queue:", end-start)

四、应用场景的不同

栈和队列在不同的应用场景中有不同的用途。栈通常用于处理递归和回溯问题，以及表达式的计算和括号匹配。队列则常用于解决如广度优先搜索（BFS）等问题。同时，队列还常被用于实现具有缓冲区的数据传输。

下面是栈和队列分别应用于表达式括号匹配的代码实现：

# 栈应用：表达式括号匹配
def is_balanced(expr):
    s = Stack()
    for char in expr:
        if char in ['(', '[', '{']:
            s.push(char)
        elif char in [')', ']', '}']:
            if s.is_empty():
                return False
            top = s.pop()
            if not is_match(top, char):
                return False
    return s.is_empty()

def is_match(p1, p2):
    return (p1 == '(' and p2 == ')') or (p1 == '[' and p2 == ']') or (p1 == '{' and p2 == '}')

print(is_balanced("(Pangolin)[Python]"))  # True
print(is_balanced("{Python(Jupyter)}[Java]"))  # True
print(is_balanced("({Python][Jupyter)}"))  # False

# 队列应用：BFS实现图的遍历
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')
# 输出：A B C D E F