AI 助理
备案控制台
开发者社区 云计算 文章 正文

顺序循环队列与链队列

2023-02-01 150
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 今天学习了队列，一种是顺序循环队列，一种是链队列，我个人认为链队列相对好用一点，毕竟链队列不用考虑“假溢出”的问题，下面是我整理的关于队列的一些基本操作

我们先来看个问题：
【问题描述】
实现循环队列的基本操作。（循环队列最大长度不超过20）
【输入形式】
输入若干个整数（以空格分隔），其中0表示做出队操作，不为0的整数为入队元素。
【输出形式】
依次输出队列的全部元素，若队列为空，则输出“empty”
【样例输入1】
1 2 3 4 5 6
【样例输出1】
1 2 3 4 5 6
【样例输入2】
1 2 3 0 0 4 0 5
【样例输出2】
4 5
【样例输入3】
1 0 2 0 3 0
【样例输出3】
empty
【样例输入4】
1 0 2 0 0 3 0 0 0
【样例输出4】
empty
下面我们将分别通过顺序循环队列和链队列来实现以上操作

一、顺序循环队列

顺序循环队列需要两个指针，一个用来入队，一个用来出队
顺序循环队列是个在数组中移动的队列
顺序循环队列主要要考虑“假溢出”的问题，为了防止“假溢出”，我们通过(front+1)%MAX来实现

1.1 初始化一个顺序循环队列

#include<stdio.h>
#include<malloc.h>
#define MAX 10
typedef struct Queue{
    int *base;       //可以理解为一个数组
    int front;       //指向队头的指针   可以理解为数组的下标
    int rear;        //指向队尾的指针   可以理解为数组的下标
    int len;         //队列的长度，方便打印队列
}Queue,*PQueue;
int Init_Queue(PQueue Q){
    Q->base=(int *)malloc(MAX*sizeof(int));   //初始化分配一个空间
    Q->front=Q->rear=0;                //初始化队头队尾在一起
    Q->len=0;                          //初始化队列长度为0
    return 1;
}

1.2 判断队列是否为空

int Empty_Queue(PQueue Q){
    if(Q->front==Q->rear)     //当队头和队尾指针在一起的时候，说明是个空队
    return 1;
    else
    return 0;
}

1.3 入队

入队前一定要先判断队列是否已经满了，满了就不能再入队了

int Push_Queue(PQueue Q,int e){
    if((Q->rear+1)%MAX==Q->front) return 0;    //首先要判断队列是否满了
    Q->base[Q->rear]=e;           //满了无法入队，没满可以入队
    Q->rear=(Q->rear+1)%MAX;      //这个方法可以让队列成为循环队列
    Q->len++;                     //每次入队队列长度增加1
    return 1;
}

1.4 出队

出队前一定要判断队列是否已经空了，如果队列空了，那么就没办法出队了

int Pop_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;   //出队前要先判断是否队空
    *e=Q->base[Q->front];             //队列不空可以出队
    Q->front=(Q->front+1)%MAX;        //这个方法可以循环出队
    Q->len--;                         //出队后队长减1
    return 1;
}

1.5 打印队列

int Print_Queue(PQueue Q){
    int i;
    for(i=0;i<Q->len;i++){
        printf("%d ",Q->base[Q->front+i]);    //将队列打印出来
    }
    printf("\n");
    return 1;
}

1.6 代码实现

1.6.1 完整代码

#include<stdio.h>
#include<malloc.h>
#define MAX 10
typedef struct Queue{
    int *base;
    int front;
    int rear;
    int len;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
    Q->base=(int *)malloc(MAX*sizeof(int));
    Q->front=Q->rear=0;
    Q->len=0;
    return 1;
}
int Empty_Queue(PQueue Q){
    if(Q->front==Q->rear)
    return 1;
    else
    return 0;
}
int Push_Queue(PQueue Q,int e){
    if((Q->rear+1)%MAX==Q->front) return 0;
    Q->base[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAX;
    Q->len++;
    return 1;
}
int Pop_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;
    *e=Q->base[Q->front];
    Q->front=(Q->front+1)%MAX;
    Q->len--;
    return 1;
}
int Get_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;
    *e=Q->base[Q->front];
    return 1;
}
int Print_Queue(PQueue Q){
    int i;
    for(i=0;i<Q->len;i++){
        printf("%d ",Q->base[Q->front+i]);
    }
    printf("\n");
    return 1;
}
int main(){
    Queue Q;
    int e;
    Init_Queue(&Q);
    while(scanf("%d",&e)==1){
        if(e==0){
            Pop_Queue(&Q,&e);
        }else{
            Push_Queue(&Q,e);
        }
    }
    if(Empty_Queue(&Q)==1){
        printf("empty\n");
    }else{
        Print_Queue(&Q);
    }
    return 0;
}

1.6.2 运行结果

1.png

二、链队列（带头结点单链表）

我们用的是带头结点的单链表，方便出队
链队列需要两个指针，分别用来入队和出队
链队列不用考虑“假溢出”问题，操作起来更加方便

2.1 初始化一个链队列

#include<stdio.h>
#include<malloc.h>
typedef struct Node{       //每个结点
    int data;
    struct Node *next;
}Node,*PNode; 
typedef struct Queue{      //保存两个指针
    PNode front,rear;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
    PNode P=(PNode)malloc(sizeof(Node));
    P->next=NULL;
    Q->front=Q->rear=P;    //初始队尾指针在队头指针位置
    return 1;
}

2.2 判断队列是否为空

int Empty_Queue(PQueue Q){
    if(Q->front==Q->rear)    //当队尾指针在队头指针处时，队列为空
    return 1;
    else
    return 0;
}

2.3 入队

链队列入队不用考虑“假溢出”问题，操作起来方便

int Push_Queue(PQueue Q,int e){
    PNode Pnew=(PNode)malloc(sizeof(Node)); //新建一个结点，用于入队
    Pnew->next=NULL;     
    Pnew->data=e;   
    Q->rear->next=Pnew;      //入队操作只用尾指针rear
    Q->rear=Pnew;
    return 1;
}

2.4 出队

int Pop_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;     //出队先判断是否队空
    *e=Q->front->next->data;
    if(Q->front->next==Q->rear){        //当只剩一个有效结点的时候，为了避免尾指针丢失
        Q->front->next=NULL;
        Q->rear=Q->front;               //我们删除结点后要让尾指针指向头结点
    }else{
        Q->front->next=Q->front->next->next;   
    }
    return 1;
}

2.5 打印队列

int Print_Queue(PQueue Q){
    PNode P=Q->front->next;
    while(P){
        printf("%d ",P->data);    //和打印单链表类似
        P=P->next;
    }
    printf("\n");
}

2.6 代码实现

2.6.1 完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct Node{
    int data;
    struct Node *next;
}Node,*PNode;
typedef struct Queue{
    PNode front,rear;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
    PNode P=(PNode)malloc(sizeof(Node));
    P->next=NULL;
    Q->front=Q->rear=P;
    return 1;
}
int Empty_Queue(PQueue Q){
    if(Q->front==Q->rear)
    return 1;
    else
    return 0;
}
int Push_Queue(PQueue Q,int e){
    PNode Pnew=(PNode)malloc(sizeof(Node));
    Pnew->next=NULL;
    Pnew->data=e;
    Q->rear->next=Pnew;
    Q->rear=Pnew;
    return 1;
}
int Pop_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;
    *e=Q->front->next->data;
    if(Q->front->next==Q->rear){
        Q->front->next=NULL;
        Q->rear=Q->front;
    }else{
        Q->front->next=Q->front->next->next;
    }
    return 1;
}
int Get_Queue(PQueue Q,int *e){
    if(Q->front==Q->rear) return 0;
    *e=Q->front->next->data;
    return 1;
}
int Print_Queue(PQueue Q){
    PNode P=Q->front->next;
    while(P){
        printf("%d ",P->data);
        P=P->next;
    }
    printf("\n");
}
int main(){
    Queue Q;
    Init_Queue(&Q);
    int e;
    while(scanf("%d",&e)==1){
        if(e==0){
            Pop_Queue(&Q,&e);
        }else{
            Push_Queue(&Q,e);
        }
    }
    if(Empty_Queue(&Q)==1){
        printf("empty\n");
    }else{
        Print_Queue(&Q);
    }
    return 0;
}

2.6.2 运行结果

2.png

三、总结

1.顺序循环队列入队和出队都要考虑“假溢出”的问题

2.链队列出队时要考虑是否是最后一个有效结点，避免尾结点的丢失

3.相比之下，链队列不用考虑“假溢出问题”，在实际应用中操作起来跟方便

Want595
目录
相关文章
阿里云Forward
|
6月前
循环队列详解
循环队列详解
阿里云Forward
130 0
DarkFire
|
12月前
|
存储
Leetcode循环队列（数组实现及链表实现）
Leetcode循环队列（数组实现及链表实现）
DarkFire
80 0
游客zmarifzwlqzqs
|
存储
【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列（下）
【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列（下）
游客zmarifzwlqzqs
96 0
游客zmarifzwlqzqs
【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列（上）
【栈和队列OJ题】有效的括号&&用队列实现栈&&用栈实现队列&&设计循环队列（上）
游客zmarifzwlqzqs
66 0
在下小吉.
|
存储 缓存 算法
【数据结构】队列（循环队列和链队列）详细讲解各种操作
【数据结构】队列（循环队列和链队列）详细讲解各种操作
在下小吉.
894 0
tinyvvampirepudge
|
Java
Java实现队列——顺序队列、链式队列
#### 概念 先进者先出，这就是典型的“队列”。(First In, First Out，FIFO)。 我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队和出队。入队 `enqueue()`，让一个数据到队列尾部；出队 `dequeue()`，从队列头部取一个元素。
tinyvvampirepudge
109 0
刘亚洲
|
消息中间件 存储 缓存
基于数组和链表实现队列
创建大数组实现对象：里面包含的信息公共初始化： 初始化页工厂：索引页工厂、数据页工厂、元数据页工厂,初始化数组索引、初始化数据页索引，通过队列前置索引页工厂获取索引页，获取队列front索引buffer,获取front,也即索引。这个实现和kafka是类似的，也即需要有相关页信息 入队列：进行入队操作是一个追加的操作，首先判断容量是否够，不够，则进行扩容操作。通过缓存拿到映射页实现，然后通过映射页。再通过锁，仅锁定创建页，索引用完后进行移除操作，映射页面实现，使用双向校验，如果为空，则创建页索引对象,通过索引拿到文件名称，然后通过读写通道进行读写操作。使用fileChannal调用映射方法获取
刘亚洲
140 0
基于数组和链表实现队列
Lucky小黄人^_^
|
存储
顺序循环队列和链式存储队列（带头结点和不带头结点）
顺序循环队列和链式存储队列（带头结点和不带头结点）
Lucky小黄人^_^
111 0
2h354fp6qznjc
Day9——用栈实现队列、用队实现拟栈
Day9——用栈实现队列、用队实现拟栈
2h354fp6qznjc
116 0
pandaconda
|
C++
C++实现线性表 - 05 队列（数组实现）
今天我们来学习一下队列结构，这也是我们讲线性表的最后一个部分了，这里会分成两节来讲，先讲数组的实现，再讲链表的实现。由于双端队列是包含了单端队列的操作，所以我们这里为了讲的更全一些，代码实现为双端队列。
pandaconda
137 0
C++实现线性表 - 05 队列（数组实现）