我爷爷都看的懂的《栈和队列》，学不会来打我数据结构

栈和队列

目录

- - 栈
  - - 顺序栈
    - - 顺序栈定义
      - 顺序栈初始化
      - 入栈
      - 出栈
      - 读栈顶元素
      - 判断栈是否为空
    - 共享栈
    - - 定义
      - 初始化
      - 入栈
      - 出栈
    - 链栈
  - 队列
  - - 顺序队列
    - - 定义
      - 初始化
      - 入队
      - 出队
      - 获取队头元素
      - 判断队列是否为空
    - 队列链式存储
    - - 定义
      - 初始化
      - 入队
      - 出队
      - 判断队列是否为空
    - 队列链式存储（不带头结点）
    - - 定义
      - 初始化
      - 入队
      - 出队
      - 判断队列是否为空

【我爷爷都看的懂的《栈和队列》，学不会来打我】
栈

定义：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作

顺序栈顺序栈定义

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置

#define MaxSize 10 typedef 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 10 typedef 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 = https://www.it610.com/article/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 = https://www.it610.com/article/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随着专业的深入会越来越广哦…一起期待。
??人生的每一次成长，都是从“觉得自己是个傻逼”开始的，人生每一次的陷入困境，都是从“觉得别人是个傻逼”开始的。
很高兴与你相遇，一起加油！！！！