数据结构3.0 栈、队列和数组

一、栈的基本概念

①栈的定义

②栈的基本操作

③常考题型

④小结

二、栈的顺序存储实现

①顺序栈的定义

②初始化操作

③进栈操作

④出栈操作

⑤读栈顶元素操作

⑥共享栈

⑦小结

三、栈的链式存储实现

①链栈的定义

②小结

#include <stdio.h> #include <stdlib.h> // 链栈的结点结构 typedef struct LinkNode { int data; // 数据域 struct LinkNode *next; // 指针域 } LinkNode; // 链栈结构（不带头结点，栈顶指针直接指向栈顶元素） typedef struct { LinkNode *top; // 栈顶指针 } LinkStack; // 1. 初始化链栈 void InitStack(LinkStack &S) { S.top = NULL; // 空栈时栈顶指针为NULL } // 2. 判断栈是否为空 bool StackEmpty(LinkStack S) { return S.top == NULL; } // 3. 进栈操作（增） bool Push(LinkStack &S, int x) { // 生成新结点 LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode)); if (p == NULL) return false; // 内存分配失败 p->data = x; p->next = S.top; // 新结点的next指向原栈顶 S.top = p; // 更新栈顶指针 return true; } // 4. 出栈操作（删） bool Pop(LinkStack &S, int &x) { if (StackEmpty(S)) return false; // 栈空，出栈失败 LinkNode *p = S.top; // 指向栈顶结点 x = p->data; // 获取栈顶元素 S.top = S.top->next; // 栈顶指针下移 free(p); // 释放原栈顶结点 return true; } // 5. 获取栈顶元素（查） bool GetTop(LinkStack S, int &x) { if (StackEmpty(S)) return false; // 栈空，获取失败 x = S.top->data; return true; } // 测试函数 int main() { LinkStack S; InitStack(S); // 进栈 Push(S, 1); Push(S, 2); Push(S, 3); // 获取栈顶 int topVal; if (GetTop(S, topVal)) { printf("栈顶元素：%d\n", topVal); } // 出栈 int popVal; while (Pop(S, popVal)) { printf("出栈元素：%d\n", popVal); } // 判空 if (StackEmpty(S)) { printf("栈已为空\n"); } return 0; }

四、队列的基本概念

①队列的定义

②队列的基本操作

③小结

五、队列的顺序实现

①初始化操作

②入队操作

③循环队列

④循环队列——入队操作

⑤循环队列——出队操作

⑥判断队列已满/已空

⑦小结

六、队列的链式实现

①初始化（带头结点）

②初始化（不带头结点）

③入队（带头结点）

④入队（不带头结点）

⑤出队（带头结点）

⑥出队（不带头结点）

⑦队列满的条件

⑧小结

七、双端队列