现在位置: 首页 / C语言 / 正文

队列-数据结构

  • Caijxlinux
  • C语言
  • 2024-04-12
  • 5626热度
  • 0评论

队列-数据结构

队列的基本概念

队列：是只允许在一端进行插入，在另一端删除的线性表。

队头：允许删除的一端

队尾：允许插入的一端

空队列：队列内不包含元素

队列的特点：先进先出

队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之称为新队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

QueueEmpty(Q)：判断队列是否为空，为空返回true，否则返回false。

队列顺序实现

顺序存储实现队列

基本操作：创(初始化)、增(入队)、删(出队)、查(获取队头元素)、判空、判满(进行)

#include <stdio.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear; //队头指针和队尾指针
}SqQueue;

int main(){
    SqQueue Q;
    return 0;
}
初始化操作
#include <stdio.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear; //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时队头、队尾指针指向0
    Q.rear=Q.front=0;
}

//判断队列是否为空
bool  QueueEmpty(SqQueue Q){
    if(Q.rear==Q.front) //队空条件
    {
        return true;
    } else
    {
        return false;
    }
}
int main(){
    //声明一个队列并进行初始化操作(顺序存储)
    SqQueue Q;
    InitQueue(Q);
    return 0;
}
入队操作

入队操作需要注意：判断队列满的条件应该是什么？由于在数据出队的过程中，队头指针会不断移动，怎么循环利用已经出队的空间呢？

此时可以采用模运算将无限的整数域映射到有限的整数集合上。用模运算将存储空间变成了逻辑上的环状结构，而判断队列是否已满的条件是队尾指针的下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front。这样做的代价是牺牲一个存储单元。

#include <stdio.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear; //队头指针和队尾指针
}SqQueue;

//元素入队操作
bool  EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize==Q.front); //队满条件
    {
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
}
int main(){
    return 0;
}

出队操作

出队操作需要注意，只能让队头元素出队，并且在出队时，需要判断队列是否为空，出队后，队头指针需要后移。

#include <stdio.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear; //队头指针和队尾指针
}SqQueue;

//元素出队操作
bool DnQueue(SqQueue &Q, ElemType &x){
    if(Q.rear==Q.front); //队空条件
    {
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize; //队头指针后移
    return true;
}

//获取队头元素的值，用x返回
bool GetHead(SqQueue Q, ElemType &x){
    if(Q.rear==Q.front)
    {
        return false; //队空则报错
    }
    x=Q.data[Q.front];
    return true;
}
int main(){
    return 0;
}
队列的链式存储

用链式存储实现队列，主要分为带头结点的情况和不带头结点的情况，基本操作有创、增、删、查、判空、判满。

队列的链式实现
#include <stdio.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

int main(){
    return 0;
}
初始化(带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//初始化队列(带头结点)
void  InitQueue(LinkQueue &Q){
    //初始时front、rear都指向头结点
    Q.front=Q.rear=(LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
int main(){
    LinkQueue Q; //声明一个队列
    InitQueue(Q); //初始化队列
    return 0;
}
初始化(不带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//初始化队列(带头结点)
void  InitQueue(LinkQueue &Q){
    //初始时front、rear都指向头结点
    Q.front=NULL;
    Q.rear=NULL;
}
int main(){
    LinkQueue Q; //声明一个队列
    InitQueue(Q); //初始化队列
    return 0;
}
入队(带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//新元素入队(带头结点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; //新结点插入到rear之后
    Q.rear=s; //修改表尾指针
}
int main(){
    return 0;
}

入队（带头结点）

入队(不带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//新元素入队(不带头结点)
void EnQueue(LinkQueue &Q,ElemType 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; //新结点插入到rear结点之后
        Q.rear=s; //修改rear指针
    }
}
int main(){
    return 0;
}
出队(带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//队头元素出队(带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)
    {
        return false;
    }
    LinkNode *p=Q.front->next; //指针p指向头结点的下一个元素
    x=p->data; //用变量x返回队头元素
    Q.front->next=p->next; //修改头结点的next指针
    if(Q.rear==p) //此次是最后一个结点出队
    {
        Q.rear=Q.front; //修改rear指针
    }
    free(p); //释放结点空间
    return true;
}
int main(){
    return 0;
}

出队（带头结点）

出队(不带头结点)
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct { //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//队头元素出队(带头结点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==NULL) //不带头结点的空队列判断条件
    {
        return false;
    }
    LinkNode *p=Q.front; //指针p指向此次出队的结点
    x=p->data; //用变量x返回队头元素
    Q.front=p->next; //front指针指向被删除结点的下一个结点
    if(Q.rear==p) //此次是最后一个节点出队
    {
        Q.front=NULL; //恢复成空队列
        Q.rear=NULL;
    }
    free(p);
    return true;
}
int main(){
    return 0;
}

关于链式存储队列如果判断队列满的问题，一般不会队满，除非内存不足，而顺序存储会在预分配的空间耗尽时队满。

双端队列

双端队列（Deque，全称Double Ended Queue）是一种数据结构，它允许在队列的两端进行插入和删除操作，因此可以从前端（头部）或者后端（尾部）插入或删除元素。这种灵活性使得双端队列在某些场景下比普通队列更加实用。

双端队列可以看作是栈和队列的结合体，支持栈和队列的所有操作。它可以在队列的两端执行以下操作：

  1. 在队列的前端（头部）插入元素。
  2. 在队列的后端（尾部）插入元素。
  3. 从队列的前端（头部）删除元素。
  4. 从队列的后端（尾部）删除元素。
  5. 获取队列的前端元素（但不删除）。
  6. 获取队列的后端元素（但不删除）。

这种双向操作的特性使得双端队列在需要从两端频繁操作元素的场景中非常有用，比如在实现某些算法或数据结构时，或者在某些应用中需要高效地处理输入和输出。

双端队列可以用多种方式实现，包括使用数组、链表或者其他数据结构。不同的实现方式会影响其性能和适用场景。