数据结构之栈：从原理到实现

1. 什么是栈？

在数据结构中，栈（Stack）是一种非常基础的线性数据结构，它的特点是后进先出（LIFO, Last In First Out）。想象一个装盘子的架子，你只能从最上面拿盘子或放盘子，先放进去的盘子需要最后才能被取出。这种操作方式使得栈在许多程序设计中都非常有用。

栈的操作通常有两个核心功能：

入栈（Push）：将一个元素压入栈中。
出栈（Pop）：将栈顶的元素取出。

栈还有一个操作是：

查看栈顶元素（Peek或Top）：获取栈顶元素但不移除它。

2. 栈的结构

栈是一种受限的线性表，所有操作都仅限于栈顶。栈的实现方式通常有两种：

顺序栈：使用数组实现，栈的容量固定。
链式栈：使用链表实现，栈的容量可以动态变化。

栈的结构特点：

栈顶（Top）：栈中最先被访问的位置。
栈底（Bottom）：栈中最先压入的元素，始终在栈的底部。
栈只允许从栈顶插入或删除元素。

栈的核心属性：

容量（Capacity）：栈可以容纳的最大元素数量（顺序栈中需要指定容量，链式栈无需指定）。
大小（Size）：栈中当前的元素数量。

3. 栈的实现

我们将分别使用数组和链表来实现栈，并分析它们的优缺点。

（1）顺序栈

顺序栈使用数组来实现，栈的容量固定。在操作时，我们需要一个变量top来记录当前栈顶的位置。

顺序栈的定义和基本操作

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义栈结构
typedef struct {int *data;      // 动态数组，存放栈元素int top;        // 栈顶索引int capacity;   // 栈的容量
} Stack;// 初始化栈
Stack* createStack(int capacity) {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->data = (int*)malloc(sizeof(int) * capacity);stack->top = -1;         // 初始时，栈为空stack->capacity = capacity;return stack;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == -1;
}// 判断栈是否已满
bool isFull(Stack* stack) {return stack->top == stack->capacity - 1;
}// 入栈操作
void push(Stack* stack, int value) {if (isFull(stack)) {printf("栈已满，无法插入元素。\n");return;}stack->data[++stack->top] = value; // 栈顶指针加1后插入元素
}// 出栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无法删除元素。\n");return -1;}return stack->data[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无栈顶元素。\n");return -1;}return stack->data[stack->top];
}// 释放栈
void freeStack(Stack* stack) {free(stack->data);free(stack);
}

测试顺序栈


int main() {Stack* stack = createStack(5);push(stack, 10);push(stack, 20);push(stack, 30);printf("栈顶元素: %d\n", peek(stack));printf("出栈元素: %d\n", pop(stack));printf("栈顶元素: %d\n", peek(stack));freeStack(stack);return 0;
}

（2）链式栈

链式栈使用链表实现，栈的容量可以动态扩展，每次入栈或出栈操作都会动态分配或释放内存。

链式栈的定义和基本操作


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义链表节点
typedef struct Node {int data;             // 数据域struct Node* next;    // 指向下一个节点
} Node;// 定义栈结构
typedef struct {Node* top;            // 栈顶指针
} Stack;// 初始化栈
Stack* createStack() {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->top = NULL;return stack;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack->top == NULL;
}// 入栈操作
void push(Stack* stack, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = stack->top; // 新节点的next指向当前栈顶stack->top = newNode;       // 更新栈顶指针
}// 出栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无法删除元素。\n");return -1;}Node* temp = stack->top;int value = temp->data;stack->top = temp->next; // 更新栈顶指针free(temp);              // 释放内存return value;
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("栈为空，无栈顶元素。\n");return -1;}return stack->top->data;
}// 释放栈
void freeStack(Stack* stack) {while (!isEmpty(stack)) {pop(stack);}free(stack);
}

测试链式栈


int main() {Stack* stack = createStack();push(stack, 10);push(stack, 20);push(stack, 30);printf("栈顶元素: %d\n", peek(stack));printf("出栈元素: %d\n", pop(stack));printf("栈顶元素: %d\n", peek(stack));freeStack(stack);return 0;
}

4. 顺序栈和链式栈的对比

特性	顺序栈	链式栈
存储方式	数组，固定大小	链表，动态大小
动态扩展	需要手动扩展容量	内存动态分配，自动扩展
访问速度	较快	较慢
内存利用率	容量可能超出实际需求	精确分配
实现复杂度	简单	较复杂