栈

需熟练掌握栈的定义、操作和实现方式。

定义

栈是一个元素的集合，加入元素的操作叫做 “压栈”（push），而移除元素的操作叫做 “出栈”（pop）。它遵循 后进先出（LIFO, Last In First Out） 的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

基本操作

push(element): 将元素添加到栈的顶部。
pop(): 移除并返回栈顶的元素。如果栈为空，这个操作可能会抛出一个错误或返回特定的值（例如 null 或 undefined），具体取决于实现。
peek() 或 top(): 返回栈顶的元素但不移除它。这只是一个查看操作，栈的内容不会改变。如果栈为空，这个操作可能会抛出一个错误或返回特定的值。
isEmpty(): 判断栈是否为空。如果栈为空，返回 true；否则返回 false。
size() 或 length(): 返回栈中元素的数量。

实现

栈的实现方式有两种，顺序栈 和 链式栈。
顺序栈 是在 顺序表 的基础上实现 栈结构，
链式栈 是在链表的基础上实现 栈结构。

顺序栈

顺序栈是使用数组来实现的栈，利用数组的索引来模拟栈的操作。
与普通的线性表不同，栈的操作被限制在表的一端进行，这一端被称为 栈顶 (Top)，另一端被称为 栈底 (Bottom)。

顺序栈的关键在于 栈顶指针，栈顶指针是一个整数变量，用于指示栈顶元素在数组中的位置。其值的变化直接反映了栈中元素的变化。

当栈空时，一般将 栈顶指针设置为 1，当栈满时，栈顶指针指向数组中的最后一个元素。

当元素入栈时，将栈顶指针向后移动一个位置、然后放置新元素即可。当元素出栈时，需要将栈顶指针向前移动一个位置。

当然，入栈需要保证栈不满，出栈需要保证栈不空。

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    // 栈顶指针初始化为 -1，表示栈为空
    stack->top = -1; 
    return stack;
}

// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    // 先移动栈顶指针，再存放元素
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    // 先取出元素，再移动栈顶指针
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}

// 判断栈是否为空
// 当栈中没有元素时，栈顶指针通常指向一个特殊的位置，例如 -1。
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
// 当栈顶指针指向数组中的最后一个元素时，说明栈已经满了
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的 链式存储结构 利用 单链表 来实现栈的功能。

在 链式栈 实现中，一般 头结点不存放数据，仅作为链表的固定起点。栈顶元素始终为 head->next。这样依然可以保证入栈和出栈的时间复杂度为 $O(1)$。

链式栈具备以下 重要特性：

head 始终存在，不存储实际数据，只作为哨兵节点。
栈顶元素 始终位于 head->next。
空栈时，head->next == NULL。
入栈时在 head->next 前插入新节点；出栈时删除 head->next。

// 定义链式栈的节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;

// 定义链式栈（带头结点）
typedef struct {
Node* head;  // 指向头结点
} LinkedStack;

// 初始化栈（带头结点）
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->head = (Node*)malloc(sizeof(Node)); // 创建头结点
    if (!stack->head) {
        printf("Failed to allocate memory for head node\n");
        exit(1);
    }
    stack->head->next = NULL; // 初始为空栈
    return stack;
}

// 入栈操作（头插法）
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->head->next;
    stack->head->next = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* topNode = stack->head->next;
    *value = topNode->data;
    stack->head->next = topNode->next;
    free(topNode);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->head->next->data;
    return true;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->head->next == NULL;
}