目录
- 栈
- 顺序栈
- 顺序栈定义
- 顺序栈初始化
- 入栈
- 出栈
- 读栈顶元素
- 判断栈是否为空
- 共享栈
- 定义
- 初始化
- 入栈
- 出栈
- 链栈
- 队列
- 顺序队列
- 定义
- 初始化
- 入队
- 出队
- 获取队头元素
- 判断队列是否为空
- 队列链式存储
- 定义
- 初始化
- 入队
- 出队
- 判断队列是否为空
- 队列链式存储（不带头结点）
- 定义
- 初始化
- 入队
- 出队
- 判断队列是否为空
栈
- 定义：是只允许在一端进行插入或删除的线性表。首先栈是一种
线性表，但限定这种线性表只能在某一端进行插入和删除操作
顺序栈
顺序栈定义
- 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置
#define MaxSize 10typedef struct { int data[MaxSize]; int top;}SqStack;顺序栈初始化
//初始化void InitStack(SqStack& S) { S.top = -1; //data[0]还没有放数据元素}入栈
//入栈bool Push(SqStack& S, int x) { if (S.top == MaxSize - 1) return false; S.top = S.top + 1;//初始指向data[-1] S.data[S.top] = x; //等价于 //S.data[++S.top] = x; return true;}出栈
//出栈bool Pop(SqStack& S, int& x) { if (S.top == -1) return false; x = S.data[S.top]; S.top = S.top - 1; //等价于 //x = S.data[S.top--]; return true;}读栈顶元素
//读栈顶元素bool GetTop(SqStack S, int& x) { if (S.top == -1) return false; x = S.data[S.top]; return true;}判断栈是否为空
//判断栈是否为空bool StackEmpty(SqStack S) { if (S.top == -1) //栈空 return true; else return false;}共享栈
定义
- 利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
#define MaxSize 10typedef struct { int data[MaxSize]; int top0; int top1;}ShStack;ShStack s; //全局变量初始化
//初始化栈void InitStack(ShStack& s) { s.top1 = MaxSize; //上 s.top0 = -1;//下}入栈
//入栈int push(int i, int x) { if (i < 0 || i>1) { cout << "栈号输入不对" << endl; exit(0); } if (s.top1 - s.top0 == 1) { cout << "栈满了" << endl; return 0; } switch (i) { case 0:s.data[++s.top0] = x; break; case 1:s.data[--s.top1] = x; break; }}出栈
//出栈int pop(int i) { if (i < 0 || i>1) { cout << "栈号输入错误" << endl; exit(0); } switch (i) { case 0: if (s.top0 == -1) { cout << "栈空" << endl; } else { //return s.data[s.top0--]; cout << s.data[s.top0--] << endl; } break; case 1: if (s.top1 == MaxSize) { cout << "栈空" << endl; } else { //return s.data[s.top1++]; cout << s.data[s.top1++] << endl; } break; }}链栈
- 采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
类似单链表的头插法
队列
顺序队列
定义
- 队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置
#define MaxSize 10typedef struct { int data[MaxSize]; int front, rear; //队头和队尾指针}SqQueue;初始化
//初始化void InitQueue(SqQueue& Q) { Q.rear = Q.front = 0;}入队
//入队bool EnQueue(SqQueue& Q, int x) { if ((Q.rear + 1) % MaxSize == Q.front) //牺牲一个节点空间 return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; return true;}出队
//出队bool DeQueue(SqQueue& Q, int& x) { if (Q.rear == Q.front) //判断队空 return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; return true;}获取队头元素
//获取队头元素bool GetHead(SqQueue Q, int& x) { if (Q.rear == Q.front) return false; x = Q.data[Q.front]; return true;}判断队列是否为空
//判断队列是否为空bool QueueEmpty(SqQueue Q) { if (Q.rear == Q.front) //对空条件 return true; else return false;}队列链式存储
定义
- 队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已
typedef struct linkNode { int data; struct linkNode* next;}linkNode;typedef struct { linkNode* front, * rear; //队头和队尾指针}linkQueue;初始化
//初始化void InitQueue(linkQueue& Q) { Q.front = Q.rear = (linkNode*)malloc(sizeof(linkNode)); Q.front->next = NULL;}入队
//入队void EnQueue(linkQueue& Q, int x) { linkNode* s = (linkNode*)malloc(sizeof(linkNode)); s->data = x; s->next = NULL; Q.rear->next = s; Q.rear = s;}出队
//出队bool DeQueue(linkQueue& Q, int& x) { if (Q.front == Q.rear) return false; //空队 linkNode* p = Q.front->next; x = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return true;}判断队列是否为空
//判断队列是否为空bool IsEmpty(linkQueue Q) { if (Q.front == Q.rear) return true; else return false;}队列链式存储（不带头结点）
定义
typedef struct linkNode { int data; struct linkNode* next;}linkNode;typedef struct { linkNode* front, * rear; //队头和队尾指针}linkQueue;初始化
//初始化void InitQueue(linkQueue& Q) { Q.front = NULL; Q.rear = NULL;}入队
//入队(不带头结点)void EnQueue(linkQueue& Q, int x) { linkNode* s = (linkNode*)malloc(sizeof(linkNode)); s->data = x; s->next = NULL; if (Q.front == NULL) { Q.front = s; Q.rear = s; } else { Q.rear->next = s; Q.rear = s; }}出队
//出队(不带头结点)bool DeQueue(linkQueue& Q, int& x) { if (Q.front == NULL) return false; linkNode* p = Q.front; x = p->data; Q.front = p->next; if (Q.rear == p) { //此次是最后一个节点出队 Q.front = NULL; Q.rear = NULL; } free(p); return true;}判断队列是否为空
//判断队列是否为空bool IsEmpty(linkQueue Q) { if (Q.rear == NULL) return true; else return false;}此博文的分享就到此啦，点个关注再走吧
✨你好啊，我是“ 满级小白”，是一名在校大学生。
🌍主页链接：满级小白的博客
☀️博文主更方向为：计算机408，数据库，javaEE随着专业的深入会越来越广哦…一起期待。
❤️人生的每一次成长，都是从“觉得自己是个傻逼”开始的，人生每一次的陷入困境，都是从“觉得别人是个傻逼”开始的。
💪很高兴与你相遇，一起加油！！！！
