栈限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶表头端称为栈底。不含元素的表的空表称为空栈。栈遵循后进先出原则栈的两种表现形式顺序栈和链栈顺序栈用数组实现分配一块连续内存结构底层一维数组data[ ]top栈顶指针下标指向栈顶元素top-1代表栈空。#include stdlib.h#define MAX 5typedef struct {int data[MAX]; int top;} Stack;顺序栈的基本操作入栈出栈访问栈顶元素判断栈是否为空以及是否栈满。#include stdio.h #include stdlib.h #define MAX 5 typedef struct { int data[MAX]; int top; } Stack; void initStack(Stack *stack) { stack-top -1; } int isEmpty(Stack *stack) { return stack-top -1; } int isFull(Stack *stack) { return stack-top MAX - 1; } void push(Stack *stack, int value) { if (isFull(stack)) { printf(Stack is full\n); return; } stack-data[stack-top] value; } int pop(Stack *stack) { if (isEmpty(stack)) { printf(Stack is empty\n); return -1; } return stack-data[stack-top--]; } int peek(Stack *stack) { if (isEmpty(stack)) { printf(Stack is empty\n); return -1; } return stack-data[stack-top]; } int main() { Stack stack; initStack(stack); push(stack, 10); push(stack, 20); push(stack, 30); printf(Top element is: %d\n, peek(stack)); printf(Popped element is: %d\n, pop(stack)); printf(Top element after pop is: %d\n, peek(stack)); return 0; }链栈用单链表实现的栈不带头结点/带头结点均可链表头部作为栈顶.把栈顶放在链表头入栈出栈都在表头不需要遍历时间复杂度也就为O1).链栈结点结构typedef struct SNode{ int data; struct SNode *next; }SNode,*LinkStack;top栈顶指针指向链表第一个结点topNULL为空栈。链栈基本操作初始化topNULL判空top NULL入栈新建结点新结点nexttoptop新结点头插法出栈判空保存旧toptoptop-next;释放旧结点访问栈顶元素先判断定义整型指针指向栈顶数据域*valtop-data#include stdio.h #include stdlib.h // 链栈结点结构体 typedef struct SNode { int data; // 数据域 struct SNode *next; // 指针域 } SNode, *LinkStack; // 1.初始化链栈 void InitStack(LinkStack *top) { *top NULL; // 栈顶置空空栈 } // 2.判栈空 int StackEmpty(LinkStack top) { if(top NULL) return 1; // 空返回1 else return 0; } // 3.入栈头插法 int Push(LinkStack *top, int val) { // 新建结点 SNode *p (SNode *)malloc(sizeof(SNode)); if(p NULL) { // 内存分配失败 printf(内存分配失败\n); return 0; } p-data val; p-next *top; // 新结点指向原来栈顶 *top p; // top更新为新结点新结点成为栈顶 return 1; } // 4.出栈用val接收弹出元素 int Pop(LinkStack *top, int *val) { if(StackEmpty(*top)) { printf(栈为空无法出栈\n); return 0; } SNode *p *top; // p保存栈顶结点 *val p-data; // 取出栈顶数据 *top (*top)-next;// top下移 free(p); // 释放原栈顶结点 return 1; } // 5.取栈顶元素不删除 int GetTop(LinkStack top, int *val) { if(StackEmpty(top)) { printf(栈为空无栈顶元素\n); return 0; } *val top-data; return 1; } // 6.遍历链栈从栈顶到栈底输出 void TraverseStack(LinkStack top) { SNode *p top; printf(链栈元素(栈顶→栈底)); while(p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 7.销毁链栈释放全部结点 void DestroyStack(LinkStack *top) { SNode *p, *q; p *top; while(p ! NULL) { q p-next; free(p); p q; } *top NULL; } // 测试主函数 int main(void) { LinkStack st; int ret, topVal; InitStack(st); Push(st, 10); Push(st, 20); Push(st, 30); TraverseStack(st); GetTop(st, topVal); printf(栈顶元素%d\n, topVal); Pop(st, ret); printf(弹出元素%d\n, ret); TraverseStack(st); DestroyStack(st); return 0; }顺序栈与链栈的区别对比项顺序栈链栈存储结构连续数组链表离散结点栈满有会溢出无受总内存限制空间分配静态预先分配可动态扩容动态 malloc随用随开入出栈时间O(1)O(1)空间开销仅存数据数据 指针额外开销判空条件top‑1topNULL适用场景规模已知规模波动大队列先进先出的线性表只允许在表的一端进行插入而在另一端删除元素。允许插入的一端叫做队尾允许删除的一端叫做队头。队列的基本操作创建队列typedef struct{int data[MAXSIZE];int front; int rear;}SqQueue;初始化队首下标和队尾下标都为0判空队列没有元素入队先确认是否队满队满无法入队未满则插入队尾队尾下标加1出队先确认是否队空队空无法出队队首有元素就删除该元素队头后移顺序非循环队列极易出现假溢出现象front后面还有大量空间rear到数组末尾就认为队列满而无法继续入队可采用循环顺序队列来解决假溢出访问队首元素若队列不为空返回队首元素#include stdio.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SqQueue; // 初始化队列 void InitQueue(SqQueue *q) { q-front 0; q-rear 0; } // 判断队列是否为空 int IsEmpty(SqQueue *q) { return q-front q-rear; } // 入队操作 int Enqueue(SqQueue *q, int x) { if (q-rear MAXSIZE) { printf(队列已满无法入队); return 0; } q-data[q-rear] x; q-rear; return 1; } // 出队操作 int Dequeue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法执行出队操作); return 0; } *x q-data[q-front]; q-front; return 1; } //访问队首元素 int Getqueue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法进行访问); return 0; } *x q-data[q-front]; return 1; }链队列用单链表实现队列由数据结点和存放头尾指针的队列结构两部分组成采用带表头结点的单链表设置队头指针front指向头结点队尾指针rear指向队尾数据结点。判空front rear入队在队尾 rear 处插入新结点更新 rear出队删除头结点后继结点删除最后一个结点时必须将 rear 赋值为 front避免 rear 悬空。链队列没有假溢出动态分配结点长度不受预先定义常量限制。顺序队列数组链队列链表存储数组静态空间动态 malloc 结点容量预先 MAXSIZE 固定理论无上限受内存假溢出普通顺序队列有循环队列解决无假溢出时间复杂度入队出队 O (1)入队出队 O (1)空间开销数组每个结点额外 next 指针开销#include stdio.h #includestdlib.h // 数据结点 typedef struct QNode { int data; struct QNode *next; } QNode; // 链队列封装头尾指针 typedef struct { QNode *front; QNode *rear; } LinkQueue; void InitQueue(LinkQueue *q) { q-front q-rear (QNode *)malloc(sizeof(QNode)); q-front-next NULL; } int IsEmpty(LinkQueue *q) { return q-front q-rear; } int Enqueue(LinkQueue *q, int x) { QNode *s (QNode *)malloc(sizeof(QNode)); if (s NULL) { printf(内存分配失败); return 0; } s-data x; s-next NULL; q-rear-next s; //尾结点指向新结点 q-rear s; //rear后移到新的队尾 return 1; } int Dequeue(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf(链队列为空无法出队); return 0; } QNode *p q-front-next; //p指向真正队头数据结点初始化时frontrear代表此时front、rear都指向头结点头结点不存有效数据 *x p-data; q-front-next p-next; // 如果删的是最后一个结点rear要回指向头结点防止rear变成野指针 if (q-rear p) { q-rear q-front; } free(p); return 1; } int Getfront(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法访问); return 0; } *x q-front-next-data; return 1; }循环队列顺序数组实现利用取模运算%把数组看成环形解决普通顺序队列的假溢出问题牺牲一个储存单元区分队空、队满。结构体定义例MAXSIZE5数组下标01234牺牲一格最多存四个元素#define MAXSIZE 5 // 队列最大容量实际最多存 MAXSIZE‑1 个元素 typedef struct{ int data[MAXSIZE]; int front; // 队头指向队头元素下标 int rear; // 队尾指向**下一个要插入的空位** } SqQueue;初始化与判空条件与普通顺序队列一致判满条件牺牲一个单元不能存满全部数组留一个空位用来区分空和满int IsFull(SqQueue *q){ return (q-rear 1) % MAXSIZE q-front; }虽然循环队列本质成环但不能采用frontrear队列空、队列满都会出现frontrear条件冲突入队操作先判满将数据放入data[rear];rear(rear1)%MAXSIZE;int EnQueue(SqQueue *q, int x){ if(IsFull(q)){ printf(队列满\n); return 0; } q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; return 1; }出队操作判空取出data[front];front指向下一个位置front(front1)%MAXSIZE实现环形回转解决假溢出。int DeQueue(SqQueue *q, int *x){ if(IsEmpty(q)){ printf(队列空\n); return 0; } *x q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }示例说明模运算全过程执行示例 MAXSIZE5最多 4 个元素初始front0,rear0 →空En(q,10): data[0]10; rear(01)%51En(q,20): data[1]20; rear2En(q,30): data[2]30; rear3En (q,40): data [3]40; rear4 →此时队列满(41)%50 front0data[4]就是牺牲的空闲位置不存数据。 数据结构——栈和队列（顺序栈/链栈，普通顺序队列，链队列，循环队列）
栈限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶表头端称为栈底。不含元素的表的空表称为空栈。栈遵循后进先出原则栈的两种表现形式顺序栈和链栈顺序栈用数组实现分配一块连续内存结构底层一维数组data[ ]top栈顶指针下标指向栈顶元素top-1代表栈空。#include stdlib.h#define MAX 5typedef struct {int data[MAX]; int top;} Stack;顺序栈的基本操作入栈出栈访问栈顶元素判断栈是否为空以及是否栈满。#include stdio.h #include stdlib.h #define MAX 5 typedef struct { int data[MAX]; int top; } Stack; void initStack(Stack *stack) { stack-top -1; } int isEmpty(Stack *stack) { return stack-top -1; } int isFull(Stack *stack) { return stack-top MAX - 1; } void push(Stack *stack, int value) { if (isFull(stack)) { printf(Stack is full\n); return; } stack-data[stack-top] value; } int pop(Stack *stack) { if (isEmpty(stack)) { printf(Stack is empty\n); return -1; } return stack-data[stack-top--]; } int peek(Stack *stack) { if (isEmpty(stack)) { printf(Stack is empty\n); return -1; } return stack-data[stack-top]; } int main() { Stack stack; initStack(stack); push(stack, 10); push(stack, 20); push(stack, 30); printf(Top element is: %d\n, peek(stack)); printf(Popped element is: %d\n, pop(stack)); printf(Top element after pop is: %d\n, peek(stack)); return 0; }链栈用单链表实现的栈不带头结点/带头结点均可链表头部作为栈顶.把栈顶放在链表头入栈出栈都在表头不需要遍历时间复杂度也就为O1).链栈结点结构typedef struct SNode{ int data; struct SNode *next; }SNode,*LinkStack;top栈顶指针指向链表第一个结点topNULL为空栈。链栈基本操作初始化topNULL判空top NULL入栈新建结点新结点nexttoptop新结点头插法出栈判空保存旧toptoptop-next;释放旧结点访问栈顶元素先判断定义整型指针指向栈顶数据域*valtop-data#include stdio.h #include stdlib.h // 链栈结点结构体 typedef struct SNode { int data; // 数据域 struct SNode *next; // 指针域 } SNode, *LinkStack; // 1.初始化链栈 void InitStack(LinkStack *top) { *top NULL; // 栈顶置空空栈 } // 2.判栈空 int StackEmpty(LinkStack top) { if(top NULL) return 1; // 空返回1 else return 0; } // 3.入栈头插法 int Push(LinkStack *top, int val) { // 新建结点 SNode *p (SNode *)malloc(sizeof(SNode)); if(p NULL) { // 内存分配失败 printf(内存分配失败\n); return 0; } p-data val; p-next *top; // 新结点指向原来栈顶 *top p; // top更新为新结点新结点成为栈顶 return 1; } // 4.出栈用val接收弹出元素 int Pop(LinkStack *top, int *val) { if(StackEmpty(*top)) { printf(栈为空无法出栈\n); return 0; } SNode *p *top; // p保存栈顶结点 *val p-data; // 取出栈顶数据 *top (*top)-next;// top下移 free(p); // 释放原栈顶结点 return 1; } // 5.取栈顶元素不删除 int GetTop(LinkStack top, int *val) { if(StackEmpty(top)) { printf(栈为空无栈顶元素\n); return 0; } *val top-data; return 1; } // 6.遍历链栈从栈顶到栈底输出 void TraverseStack(LinkStack top) { SNode *p top; printf(链栈元素(栈顶→栈底)); while(p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 7.销毁链栈释放全部结点 void DestroyStack(LinkStack *top) { SNode *p, *q; p *top; while(p ! NULL) { q p-next; free(p); p q; } *top NULL; } // 测试主函数 int main(void) { LinkStack st; int ret, topVal; InitStack(st); Push(st, 10); Push(st, 20); Push(st, 30); TraverseStack(st); GetTop(st, topVal); printf(栈顶元素%d\n, topVal); Pop(st, ret); printf(弹出元素%d\n, ret); TraverseStack(st); DestroyStack(st); return 0; }顺序栈与链栈的区别对比项顺序栈链栈存储结构连续数组链表离散结点栈满有会溢出无受总内存限制空间分配静态预先分配可动态扩容动态 malloc随用随开入出栈时间O(1)O(1)空间开销仅存数据数据 指针额外开销判空条件top‑1topNULL适用场景规模已知规模波动大队列先进先出的线性表只允许在表的一端进行插入而在另一端删除元素。允许插入的一端叫做队尾允许删除的一端叫做队头。队列的基本操作创建队列typedef struct{int data[MAXSIZE];int front; int rear;}SqQueue;初始化队首下标和队尾下标都为0判空队列没有元素入队先确认是否队满队满无法入队未满则插入队尾队尾下标加1出队先确认是否队空队空无法出队队首有元素就删除该元素队头后移顺序非循环队列极易出现假溢出现象front后面还有大量空间rear到数组末尾就认为队列满而无法继续入队可采用循环顺序队列来解决假溢出访问队首元素若队列不为空返回队首元素#include stdio.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SqQueue; // 初始化队列 void InitQueue(SqQueue *q) { q-front 0; q-rear 0; } // 判断队列是否为空 int IsEmpty(SqQueue *q) { return q-front q-rear; } // 入队操作 int Enqueue(SqQueue *q, int x) { if (q-rear MAXSIZE) { printf(队列已满无法入队); return 0; } q-data[q-rear] x; q-rear; return 1; } // 出队操作 int Dequeue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法执行出队操作); return 0; } *x q-data[q-front]; q-front; return 1; } //访问队首元素 int Getqueue(SqQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法进行访问); return 0; } *x q-data[q-front]; return 1; }链队列用单链表实现队列由数据结点和存放头尾指针的队列结构两部分组成采用带表头结点的单链表设置队头指针front指向头结点队尾指针rear指向队尾数据结点。判空front rear入队在队尾 rear 处插入新结点更新 rear出队删除头结点后继结点删除最后一个结点时必须将 rear 赋值为 front避免 rear 悬空。链队列没有假溢出动态分配结点长度不受预先定义常量限制。顺序队列数组链队列链表存储数组静态空间动态 malloc 结点容量预先 MAXSIZE 固定理论无上限受内存假溢出普通顺序队列有循环队列解决无假溢出时间复杂度入队出队 O (1)入队出队 O (1)空间开销数组每个结点额外 next 指针开销#include stdio.h #includestdlib.h // 数据结点 typedef struct QNode { int data; struct QNode *next; } QNode; // 链队列封装头尾指针 typedef struct { QNode *front; QNode *rear; } LinkQueue; void InitQueue(LinkQueue *q) { q-front q-rear (QNode *)malloc(sizeof(QNode)); q-front-next NULL; } int IsEmpty(LinkQueue *q) { return q-front q-rear; } int Enqueue(LinkQueue *q, int x) { QNode *s (QNode *)malloc(sizeof(QNode)); if (s NULL) { printf(内存分配失败); return 0; } s-data x; s-next NULL; q-rear-next s; //尾结点指向新结点 q-rear s; //rear后移到新的队尾 return 1; } int Dequeue(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf(链队列为空无法出队); return 0; } QNode *p q-front-next; //p指向真正队头数据结点初始化时frontrear代表此时front、rear都指向头结点头结点不存有效数据 *x p-data; q-front-next p-next; // 如果删的是最后一个结点rear要回指向头结点防止rear变成野指针 if (q-rear p) { q-rear q-front; } free(p); return 1; } int Getfront(LinkQueue *q, int *x) { if (IsEmpty(q)) { printf(队列为空无法访问); return 0; } *x q-front-next-data; return 1; }循环队列顺序数组实现利用取模运算%把数组看成环形解决普通顺序队列的假溢出问题牺牲一个储存单元区分队空、队满。结构体定义例MAXSIZE5数组下标01234牺牲一格最多存四个元素#define MAXSIZE 5 // 队列最大容量实际最多存 MAXSIZE‑1 个元素 typedef struct{ int data[MAXSIZE]; int front; // 队头指向队头元素下标 int rear; // 队尾指向**下一个要插入的空位** } SqQueue;初始化与判空条件与普通顺序队列一致判满条件牺牲一个单元不能存满全部数组留一个空位用来区分空和满int IsFull(SqQueue *q){ return (q-rear 1) % MAXSIZE q-front; }虽然循环队列本质成环但不能采用frontrear队列空、队列满都会出现frontrear条件冲突入队操作先判满将数据放入data[rear];rear(rear1)%MAXSIZE;int EnQueue(SqQueue *q, int x){ if(IsFull(q)){ printf(队列满\n); return 0; } q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; return 1; }出队操作判空取出data[front];front指向下一个位置front(front1)%MAXSIZE实现环形回转解决假溢出。int DeQueue(SqQueue *q, int *x){ if(IsEmpty(q)){ printf(队列空\n); return 0; } *x q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }示例说明模运算全过程执行示例 MAXSIZE5最多 4 个元素初始front0,rear0 →空En(q,10): data[0]10; rear(01)%51En(q,20): data[1]20; rear2En(q,30): data[2]30; rear3En (q,40): data [3]40; rear4 →此时队列满(41)%50 front0data[4]就是牺牲的空闲位置不存数据。