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

栈和队列

目录

栈

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

顺序栈

顺序栈定义

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

#defineMaxSize10typedefstruct{int data[MaxSize];int top;}SqStack;

顺序栈初始化

//初始化voidInitStack(SqStack& S){
    S.top =-1;//data[0]还没有放数据元素}

入栈

//入栈boolPush(SqStack& S,int x){if(S.top == MaxSize -1)returnfalse;
    S.top = S.top +1;//初始指向data[-1]
    S.data[S.top]= x;//等价于//S.data[++S.top] = x;returntrue;}

出栈

//出栈boolPop(SqStack& S,int& x){if(S.top ==-1)returnfalse;
    x = S.data[S.top];
    S.top = S.top -1;//等价于//x = S.data[S.top--];returntrue;}

读栈顶元素

//读栈顶元素boolGetTop(SqStack S,int& x){if(S.top ==-1)returnfalse;
    x = S.data[S.top];returntrue;}

判断栈是否为空

//判断栈是否为空boolStackEmpty(SqStack S){if(S.top ==-1)//栈空returntrue;elsereturnfalse;}

共享栈

定义

• 利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

#defineMaxSize10typedefstruct{int data[MaxSize];int top0;int top1;}ShStack;

ShStack s;//全局变量

初始化

//初始化栈voidInitStack(ShStack& s){
    s.top1 = MaxSize;//上
    s.top0 =-1;//下}

入栈

//入栈intpush(int i,int x){if(i <0|| i>1){
        cout <<"栈号输入不对"<< endl;exit(0);}if(s.top1 - s.top0 ==1){
        cout <<"栈满了"<< endl;return0;}switch(i){case0:s.data[++s.top0]= x;break;case1:s.data[--s.top1]= x;break;}}

出栈

//出栈intpop(int i){if(i <0|| i>1){
        cout <<"栈号输入错误"<< endl;exit(0);}switch(i){case0:if(s.top0 ==-1){
            cout <<"栈空"<< endl;}else{//return s.data[s.top0--];
            cout << s.data[s.top0--]<< endl;}break;case1:if(s.top1 == MaxSize){
            cout <<"栈空"<< endl;}else{//return s.data[s.top1++];
            cout << s.data[s.top1++]<< endl;}break;}}

链栈

• 采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。

类似单链表的头插法

队列

顺序队列

定义

• 队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置

#defineMaxSize10typedefstruct{int data[MaxSize];int front, rear;//队头和队尾指针}SqQueue;

初始化

//初始化voidInitQueue(SqQueue& Q){
    Q.rear = Q.front =0;}

入队

//入队boolEnQueue(SqQueue& Q,int x){if((Q.rear +1)% MaxSize == Q.front)//牺牲一个节点空间returnfalse;
    Q.data[Q.rear]= x;
    Q.rear =(Q.rear +1)% MaxSize;returntrue;}

出队

//出队boolDeQueue(SqQueue& Q,int& x){if(Q.rear == Q.front)//判断队空returnfalse;
    x = Q.data[Q.front];
    Q.front =(Q.front +1)% MaxSize;returntrue;}

获取队头元素

//获取队头元素boolGetHead(SqQueue Q,int& x){if(Q.rear == Q.front)returnfalse;
    x = Q.data[Q.front];returntrue;}

判断队列是否为空

//判断队列是否为空boolQueueEmpty(SqQueue Q){if(Q.rear == Q.front)//对空条件returntrue;elsereturnfalse;}

队列链式存储

定义

• 队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已

typedefstructLinkNode{int data;structLinkNode* next;}LinkNode;typedefstruct{
    LinkNode* front,* rear;//队头和队尾指针}LinkQueue;

初始化

//初始化voidInitQueue(LinkQueue& Q){
    Q.front = Q.rear =(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next =NULL;}

入队

//入队voidEnQueue(LinkQueue& Q,int x){
    LinkNode* s =(LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next =NULL;
    Q.rear->next = s;
    Q.rear = s;}

出队

//出队boolDeQueue(LinkQueue& Q,int& x){if(Q.front == Q.rear)returnfalse;//空队
    LinkNode* p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;if(Q.rear == p)
        Q.rear = Q.front;free(p);returntrue;}

判断队列是否为空

//判断队列是否为空boolIsEmpty(LinkQueue Q){if(Q.front == Q.rear)returntrue;elsereturnfalse;}

队列链式存储（不带头结点）

定义

typedefstructLinkNode{int data;structLinkNode* next;}LinkNode;typedefstruct{
    LinkNode* front,* rear;//队头和队尾指针}LinkQueue;

初始化

//初始化voidInitQueue(LinkQueue& Q){
    Q.front =NULL;
    Q.rear =NULL;}

入队

//入队(不带头结点)voidEnQueue(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;}}

出队

//出队(不带头结点)boolDeQueue(LinkQueue& Q,int& x){if(Q.front ==NULL)returnfalse;
    LinkNode* p = Q.front;
    x = p->data;
    Q.front = p->next;if(Q.rear == p){//此次是最后一个节点出队
        Q.front =NULL;
        Q.rear =NULL;}free(p);returntrue;}

判断队列是否为空

//判断队列是否为空boolIsEmpty(LinkQueue Q){if(Q.rear ==NULL)returntrue;elsereturnfalse;}

此博文的分享就到此啦，点个

关注

再走吧
✨你好啊，我是“ 满级小白”，是一名在校大学生。
🌍主页链接：满级小白的博客
☀️博文主更方向为：

计算机408

，

数据库

，

javaEE

随着专业的深入会越来越广哦…一起期待。
❤️人生的每一次成长，都是从“觉得自己是个傻逼”开始的，人生每一次的陷入困境，都是从“觉得别人是个傻逼”开始的。
💪很高兴与你相遇，一起加油！！！！