栈与队列原理解析

发布于：2025-02-10 ⋅ 阅读:(71) ⋅ 点赞:(0)

13.3 栈的原理解析

13.3.1 栈的特性

​ 只允许在一端进行插入或删除操作的线性表。

image-20230402101236727

13.3.2 栈的基本操作

image-20230402101257203

13.3.3 顺序存储实现栈

！！！

  1. 一开始top=-1,即链表为空的时候。
  2. top从0开始记元素，和数组一样。
  3. 当top等于MaxSize-1时，栈满。
  1. 定义
typedef struct{
    ElemType data[50];
    int top;
}SqStack;
SqStack S;
  1. 元素入栈
S.data[++S.top] = 4;

image-20230402101554608

  1. 元素出栈
x = S.data[S.top--];

image-20230402101636503

我自己的理解：top就相当于门，data相当于人。

  1. 当入栈的时候，就需要先打开门，人再进去；
  2. 当出栈的时候，就需要人先出来，门再锁上；

13.4 初始化栈-入栈-出栈实战

13.4.1 流程图

image-20230402103851757

13.4.2 代码

#include <stdlib.h>
#include <stdio.h>
#define MaxSize 50
//定义结构体
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

//初始化队列
void InitStack(SqStack &s){
    s.top = -1;
}

//判断队列是否为空
bool isempty(SqStack s){
    if(s.top == -1){
        return true;
    }else{
        return false;
    }
}

//压栈
void Push(SqStack &s, int pop_x){
    //判断是否栈已经满了
    if(s.top == MaxSize-1){
        return;
    }
    //开始压栈
    s.data[++s.top] = pop_x;
}

//读取栈顶元素
void GetTop(SqStack s, int &top_x){
    //判断栈是否为空
    if(s.top == -1){
        return;
    }
    top_x = s.data[s.top];
}

//出栈
void Pop(SqStack &s, int &pop_x){
    //判断栈是否为空
    if(s.top == -1){
        return;
    }
    pop_x = s.data[s.top--];
}

int main() {
    SqStack s;
    InitStack(s);
    if(isempty(s)){
        printf("empty now");
    }else{
        printf("no empty now");
    }
    printf("------------------\n");
    Push(s,1);
    Push(s,2);
    Push(s,3);
    Push(s,4);
    if(isempty(s)){
        printf("empty now\n");
    }else{
        printf("no empty now\n");
    }
    printf("------------------\n");
    int top_x, pop_x;
    GetTop(s, top_x);
    printf("top val is %d\n", top_x);
    Pop(s, pop_x);
    GetTop(s, top_x);
    printf("pop val is %d\n", pop_x);
    printf("top val is %d\n", top_x);
    return 0;
}

13.5 队列-循环队列原理解析

13.5.1 队列的特性

​ 队列(Queue)简称队，也是一种操作受限制的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

image-20230402110242934

13.5.2 循环队列

13.5.2.1 结构体

#define MaxSize 6
//定义结构体
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

13.5.2.2 示意图

image-20230402111241584

  1. 初始队列，要求Q.front = Q.rear(也是队列为空的条件);

  2. 若队列能够存储满，则当存储满时，依然会存在Q.front = Q.rear的情况，与队列为空时条件冲突，因此我们规定队列所能存储的元素个数为存储最大容量-1；

  3. Q.rear始终指向将要被入队的位置(此处为空)；

  4. Q.front始终指向队列中即将出队的元素(此处不为空)。

  5. ==！！！==判断队列满的标志：(Q.rear+1)%MaxSize==Q.front。因为Q.rear如果刚好在5，下一个位置在0，而不是在6!!!

  6. 改变队尾，队首标记：

    1. Q.rear = (Q.rear+1)%MaxSize
    2. Q.front = (Q.front+1)%MaxSize

13.5.2.3 循环队列元素入队

13.5.2.3.1 流程图

image-20230402125029395

13.5.2.3.2 代码
//入队
void EnQueue(SqQueue &q, int en_val){
    //判断是否已经满队列了
    if((q.rear+1)%MaxSize == q.front){
        return;
    }
    q.data[q.rear] = en_val;
    q.rear = (q.rear+1)%MaxSize;
}

13.5.2.4 循环队列元素出队

13.5.2.4.1 流程图

image-20230402125200745

13.5.2.4.2 代码
//出队
void DeQueue(SqQueue &q, int &de_val){
    //判断是否为空队列
    if(isempty(q)){
        return;
    }
    de_val = q.data[q.front];
    q.front = (q.front+1)%MaxSize;
}

13.5.3 队列的链式存储

13.5.3.1 定义

​ 队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。

13.5.3.2 结构体

//结构体
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;
typedef struct LinkQueue{
    LinkList front, rear;
}LinkQueue;

13.6 循环队列实战

13.6.1 流程图

image-20230402130215429

13.6.2 代码

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 6
//定义结构体
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

//初始化循环队列
void InitSqQue(SqQueue &q){
    q.front = q.rear = 0;
}

//判断队列是否为空
bool isempty(SqQueue q){
    if(q.rear == q.front){
        return true;
    }else{
        return false;
    }
}

//入队
void EnQueue(SqQueue &q, int en_val){
    //判断是否已经满队列了
    if((q.rear+1)%MaxSize == q.front){
        return;
    }
    q.data[q.rear] = en_val;
    q.rear = (q.rear+1)%MaxSize;
}

//出队
void DeQueue(SqQueue &q, int &de_val){
    //判断是否为空队列
    if(isempty(q)){
        return;
    }
    de_val = q.data[q.front];
    q.front = (q.front+1)%MaxSize;
}

int main() {
    SqQueue q;
    InitSqQue(q);
    if(isempty(q)){
        printf("empty queue\n");
    }else{
        printf("no empty queue\n");
    }
    printf("-----------------------------\n");
    EnQueue(q,1);
    EnQueue(q,2);
    EnQueue(q,3);
    if(isempty(q)){
        printf("empty queue\n");
    }else{
        printf("no empty queue\n");
    }
    printf("-----------------------------\n");
    int front_val;
    while(q.front != q.rear){
        DeQueue(q, front_val);
        printf("de_queue val is %d\n", front_val);
        if(isempty(q)){
            printf("empty queue\n");
        }else{
            printf("no empty queue\n");
        }
    }
    return 0;
}

13.7 链表实现的队列的实战

13.7.1 流程图

image-20230402142925081

13.7.2 代码

#include <stdlib.h>
#include <stdio.h>

//结构体
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;
typedef struct LinkQueue{
    LinkList front, rear;
}LinkQueue;

//队列的初始化
void InitLinkQueue(LinkQueue &q){
    q.rear = q.front = (LinkList) malloc(sizeof (LNode));
    q.front->next = NULL;//万一没有元素呢，所以头结点的指针域为NULL（可参照头插法新建链表）
}

//判断队列是否为空
bool isempty(LinkQueue q){
    if(q.front == q.rear){
        return true;
    }else{
        return false;
    }
}

//入队,从尾部入队
void EnQueue(LinkQueue &q, int en_val){
    LinkList s;
    s = (LinkList) malloc(sizeof (LNode));
    s->data = en_val;
    s->next = NULL;
    q.rear->next = s;
    q.rear = s;
}

//出队，从头部出队
void DeQueue(LinkQueue &q, int &de_val){
    //如果队列为空
    if(q.rear == q.front){
        return;
    }
    LinkList s = q.front->next;
    de_val = s->data;
    q.front->next = s->next;//断链
    //如果恰好删除的是最后一个结点
    if(q.rear == s){
        q.rear = q.front;
    }
    free(s);
}

int main() {
    LinkQueue q;
    InitLinkQueue(q);
    if(isempty(q)){
        printf("empty queue\n");
    }else{
        printf("no empty queue\n");
    }
    printf("-----------------------------\n");
    EnQueue(q,1);
    EnQueue(q,2);
    EnQueue(q,3);
    EnQueue(q,4);
    if(isempty(q)){
        printf("empty queue\n");
    }else{
        printf("no empty queue\n");
    }
    printf("-----------------------------\n");
    int de_val;
    while(q.front != q.rear) {
        DeQueue(q, de_val);
        printf("de_queue val is %d\n", de_val);
        if(isempty(q)){
            printf("empty queue\n");
        }else{
            printf("no empty queue\n");
        }
    }
    return 0;
}

13.8 2019年42题真题

13.8.1 题目简介：

image-20230402220336039

13.8.2 题目解析

image-20230402220403995

image-20230402220414395

13.8.3 链式循环队列

13.8.3.1 流程图

image-20230402220423066

13.8.3.2 代码

#include <stdio.h>
#include <stdlib.h>

//定义结构体
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode, *LinkList;
typedef struct{
    LinkList front, rear;
}LinkQueue;

//初始化
void Init_LinkQueue(LinkQueue &q){
    //一开始有一个结点呀，只不过不是头结点，就是第一个结点
    LinkList h;
    h = (LinkList)malloc(sizeof(LNode));
    q.rear = q.front = h;
    q.rear->next = q.front;
}

//压入元素
void Push_LinkQueue(LinkQueue &q, int pop_val){
    if(q.rear->next == q.front){
        LinkList h;
        h = (LinkList)malloc(sizeof(LNode));
        h->next = q.front;
        q.rear->next = h;
        q.rear->data = pop_val;
        q.rear = h;
    }else{
        q.rear->data = pop_val;
        q.rear = q.rear->next;
    }
}

//弹出元素
void Pop_LinkQueue(LinkQueue &q){
    if(q.rear == q.front){
        return;
    }
    q.front = q.front->next;
}

int main() {
    LinkQueue q;
    Init_LinkQueue(q);
    Push_LinkQueue(q, 1);
    Push_LinkQueue(q, 2);
    Push_LinkQueue(q, 3);
    Push_LinkQueue(q, 4);
    Pop_LinkQueue(q);
    Pop_LinkQueue(q);
    Pop_LinkQueue(q);
    Pop_LinkQueue(q);
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布