栈与队列的基本概念

栈（Stack）是一种后进先出（LIFO）的线性数据结构，操作仅限于栈顶。插入操作称为压栈（Push），删除操作称为弹栈（Pop）。栈的典型实现方式包括数组和链表。

队列（Queue）是一种先进先出（FIFO）的线性数据结构，插入操作在队尾（Enqueue），删除操作在队头（Dequeue）。队列的实现方式同样包括数组和链表，但通常需要处理循环队列以避免空间浪费。

栈的实现与应用

栈的数组实现需维护一个栈顶指针。压栈时指针上移并写入数据，弹栈时返回栈顶数据并下移指针。链表实现则通过头插法模拟栈顶。

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()

应用场景包括函数调用栈、表达式求值（如括号匹配）、浏览器历史记录等。递归的本质即是系统栈的调用过程。

队列的实现与变种

队列的数组实现需处理假溢出问题，循环队列通过模运算解决。链表实现则维护头尾指针。

class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.insert(0, item)
    
    def dequeue(self):
        return self.items.pop()

双端队列（Deque）允许两端操作，优先队列（Priority Queue）按优先级出队。应用包括任务调度、消息队列、BFS算法等。

栈与队列的对比

栈的LIFO特性适合需要回溯的场景，队列的FIFO特性保证公平性。栈的空间复杂度通常为O(n)，队列可能因扩展操作存在均摊时间复杂度。

实际工程中，栈常用于语法解析，队列用于缓冲管理。某些问题（如二叉树遍历）可通过两种结构相互转换实现不同需求。

常见问题与优化

栈溢出是递归算法的典型风险，需设置深度限制或改为迭代。队列的阻塞实现可用于生产者-消费者模型，环形缓冲区减少内存拷贝。

线程安全场景下需使用同步原语保护操作，无锁队列通过CAS（Compare-And-Swap）实现高性能并发。