栈：后进先出的线性表，如何实现增删查？

本文主要讲解栈这种数据结构，它是一种后进先出（LIFO）的线性表，并探讨如何实现栈的增加、删除、查找操作。由于栈的特殊性，通常不涉及“改”操作，更多关注的是入栈和出栈。

栈的定义

栈（Stack）是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。这一端被称为栈顶（top），另一端被称为栈底（bottom）。当栈中没有元素时，称为空栈。

栈的特点是后进先出（Last In First Out, LIFO），也就是说，最后进入栈的元素最先出去。

栈的基本操作

栈的基本操作包括：

入栈（Push）：将一个新元素放入栈顶。
出栈（Pop）：从栈顶移除一个元素。
查看栈顶元素（Peek/Top）：获取栈顶元素的值，但不移除它。
判断栈是否为空（isEmpty）：检查栈中是否还有元素。
获取栈的大小（Size）：返回栈中元素的个数。

栈的实现方式

栈可以用数组或链表来实现。

数组实现

用数组实现栈，需要指定栈的大小，并且需要一个指针指向栈顶。

优点：

实现简单。
访问栈顶元素的时间复杂度为O(1)。

缺点：

栈的大小固定，容易造成空间浪费或溢出。
插入和删除操作需要移动元素，时间复杂度为O(n) (虽然通常只在栈顶操作，复杂度近似O(1)，但极端情况下，例如需要扩容时，复杂度会变为O(n))

链表实现

用链表实现栈，不需要指定栈的大小，并且需要一个指针指向栈顶。

优点：

栈的大小可以动态扩展。
插入和删除操作不需要移动元素，时间复杂度为O(1)。

缺点：

需要额外的空间存储指针。
访问栈顶元素的时间复杂度为O(1)。

栈的应用

栈在计算机科学中有很多应用，例如：

函数调用栈：用于保存函数调用时的参数、返回地址等信息。
表达式求值：用于将中缀表达式转换为后缀表达式，并进行求值。
括号匹配：用于检查括号是否匹配。
浏览器的前进后退功能：后退时，从栈顶取出最近访问的页面。
Undo/Redo 功能：撤销和重做操作。

栈的增删查

增加（入栈 Push）： 将元素添加到栈顶。
删除（出栈 Pop）： 移除栈顶元素。
查（查看栈顶元素 Peek/Top）： 获取栈顶元素，但不移除。需要注意的是，栈主要关注栈顶元素，查找特定元素通常不是栈的主要用途。如果要查找栈中特定元素，需要出栈直到找到目标元素或栈为空。

代码示例 (Python - 数组实现)

class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.stack = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, item):
        if self.is_full():
            print("Stack is full")
            return
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            print("Stack is empty")
            return None
        item = self.stack[self.top]
        self.stack[self.top] = None # Optional: Clear the reference
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            print("Stack is empty")
            return None
        return self.stack[self.top]

    def size(self):
        return self.top + 1

# Example Usage:
s = Stack(5)
s.push(1)
s.push(2)
s.push(3)

print(s.peek()) # Output: 3
print(s.pop())  # Output: 3
print(s.size()) # Output: 2

心缕工纺

栈（Stack）是一种特殊的线性表