深入浅析C语言中堆栈和队列

堆栈（Stack）

堆栈是一种先进后出（Last In First Out，LIFO）的线性数据结构，只允许在一端进行插入和删除操作。堆栈在C语言中常用于函数调用时的参数传递、表达式求值和程序中断处理等场景。

实现堆栈的基本操作

下面是堆栈的基本操作，可以用数组来实现：

初始化

#define MAX_SIZE 100  // 假设堆栈最大容量是100
int stack[MAX_SIZE];  // 堆栈数组
int top = -1;  // 栈顶指针，初始值为-1

void init() {
    top = -1;
}

压栈

void push(int value) {
    if (top == MAX_SIZE - 1) {
        printf("stack overflow!\n");
        return;
    }
    stack[++top] = value;
}

弹栈

int pop() {
    if (top == -1) {
        printf("stack underflow!\n");
        return -1;
    }
    return stack[top--];
}

取栈顶元素

int peek() {
    if (top == -1) {
        printf("stack is empty!\n");
        return -1;
    }
    return stack[top];
}

堆栈的示例说明

下面是一条实例说明堆栈的应用：

假设今天你要去超市买东西，商店里要求使用购物车。但是你发现购物车不够了，只剩下一个，于是你就将自己的小车丢在了车车的上方，继续进行购物。

你这个行为实际是使用了一个堆栈。

你新拿到的物品排在栈顶，你所有的购物结果能够获取的物品，就是从栈顶开始弹出所有的物品。

队列（Queue）

队列是一种先进先出（First In First Out，FIFO）的线性数据结构，队列有两个指针：队头指针和队尾指针，分别用于插入和删除操作。队列在C语言中常用于模拟进程调度、缓存队列和消息传递等场景。

实现队列的基本操作

下面是队列的基本操作，可以用数组来实现：

初始化

#define MAX_SIZE 100  // 假设队列最大容量是100
int queue[MAX_SIZE];   // 队列数组
int front = 0;  // 队头指针，初始值为0
int rear = -1;  // 队尾指针，初始值为-1

void init() {
    front = 0;
    rear = -1;
}

元素入队

void push(int value) {
    if (rear == MAX_SIZE - 1) {
        printf("queue overflow!\n");
        return;
    }
    queue[++rear] = value;
}

元素出队

int pop() {
    if (front > rear) {
        printf("queue underflow!\n");
        return -1;
    }
    return queue[front++];
}

队头元素

int peek() {
    if (front > rear) {
        printf("queue is empty!\n");
        return -1;
    }
    return queue[front];
}

队列的示例说明

下面是一条实例说明队列的应用：

假设有一只猫，它想在门外等主人回来。当它到达门口时，就在看门的地方坐下来。然后它看到一只老鼠从草丛中跑了出来，于是就追它。但是它并没有追上老鼠，所以它走回原来的位置等待主人回来。猫不停地重复这个过程，直到主人回来。

这个过程可以用队列来模拟。在队列里，猫的相对位置被维护。当猫追老鼠时，位置会前进，当猫回到原来的位置时，位置又会后退。这里主人即构成队列的对象，背上放有猫。