数据结构：栈与队列的定义、核心操作与代码解析

在数据结构的学习中，栈和队列是绕不开的基础线性结构。它们本质上都是对数组或链表的规则化封装——通过限制数据的存取方式，满足不同场景的需求。栈遵循先进后出（LIFO），像弹匣一样只能从顶端操作；队列遵循先进先出（FIFO），像排队办事一样有序流转。

一、概念：两种秩序的本质区别

栈和队列的核心差异在于数据操作的顺序规则，这一规则直接决定了它们的应用场景和实现逻辑。

1. 栈

栈（Stack）遵循后进先出（Last In First Out, LIFO）原则，就像我们日常叠放的盘子——最后放上去的盘子，必须最先拿下来。这种结构对数据操作施加了严格限制：所有插入和删除操作都只能在栈的顶端（栈顶）完成，不支持随机访问中间元素。

生活中的撤销操作、程序中的函数调用栈，都是栈结构的典型体现：最新的操作或调用始终处于栈顶，需要时优先被处理。

2. 队列

队列（Queue）遵循先进先出（First In First Out, FIFO）原则，类似银行柜台前排队的人群——最先排队的人，最先办理业务。与栈不同，队列的操作分为两端：只能在队列的尾部（队尾）插入元素，在队列的头部（队头）删除元素，同样不支持随机访问。

操作系统的进程调度、打印机的任务队列，都依赖队列的顺序处理特性，确保任务按提交顺序公平执行。

二、栈的实现

栈的实现有两种经典方案：数组实现（顺序栈）和链表实现（链栈）。两者各有优劣，需根据实际场景选择——数组实现效率高但需预分配空间，链表实现动态扩容但有指针开销。

1. 数组实现（顺序栈）

数组实现的核心是用一个数组存储元素，并通过一个栈顶指针（通常是整数索引）标记栈顶位置。初始时栈顶指针为 -1 或者 0（表示栈空），如果是 -1 代表 top 始终指向栈顶元素，如果是 0 表示 top 始终指向栈顶元素的下一个位置，压栈时指针加 1，弹栈时指针减 1。

由于这两个数据结构的实现都很简单，具体的我在代码里注释。

#include<stdio.h> 
#include<stdlib.h> 
#include<assert.h> 
#include<stdbool.h> 
// 栈存储的数据类型 
typedef int STDataType; 
// 栈（基于动态数组实现） 
typedef struct stack { 
    STDataType* a; // 动态数组，存储栈元素 
    int top; // 栈顶指针：指向栈顶元素的下一个位置 
    int capacity; // 当前栈的最大容量 
}stack; 
// 栈的初始化 
void STInit(stack* ps) { 
    assert(ps); 
    ps->a =(STDataType* ) ((STDataType)*); 
     (ps->a == ) { 
        perror(); 
        ; 
    } 
    ps->capacity = ; 
    ps->top = ; 
}

  { 
    assert(ps); 
    (ps->a); 
    ps->a = ; 
    ps->capacity = ; 
    ps->top = ; 
}

  { 
    assert(ps); 
     (ps->capacity == ps->top) { 
        STDataType* tmp =(STDataType*)(ps->a, (STDataType)**ps->capacity ); 
         (tmp == ) { 
            perror(); 
            ; 
        } 
        ps->a = tmp; 
        ps->capacity = ps->capacity * ; 
    } 
    ps->a[ps->top++] = x; 
}

  { 
    assert(ps); 
    assert(!STEmpty(ps)); 
    ps->top--; 
}

  { 
    assert(ps); 
     ps->top; 
}

  { 
    assert(ps); 
     ps->top == ;
}

STDataType  { 
    assert(ps); 
    assert(!STEmpty(ps)); 
     ps->a[ps->top - ]; 
}