[数据结构与算法]数据结构之队列的相关实现（C语言）

参考：1.网课：数据结构与算法基础（青岛大学-王卓）
2.教材：数据结构（c语言版）第二版，严蔚敏，李冬梅等著

非科班自学，如有错误望不吝赐教。

链队

0.基本操作

一个链队包括一个头指针和尾指针，链队有头结点，链表方向从队头指向队尾，头指针始终指向头结点，尾指针指向尾结点
链栈只有栈顶指针,始终指向队尾结点

#include <stdio.h>
#include <malloc.h>
#define Max 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int QElemType;


//队列的链式储存结构
typedef struct  QNode{//链队结点包括数据域和指针域
    QElemType data;//数据域
    struct  QNode  *next;//指针域
}QNode,*QueuePtr;

typedef struct{//一个链队包括一个头指针和尾指针，
//链队有头结点，头指针始终指向头结点
    QueuePtr front;//队头指针
    QueuePtr rear;//队尾指针
}LinkQueue;

//链队的初始化
Status  InitQueue(LinkQueue* QQ){
    (*QQ).front=(QueuePtr)malloc(sizeof(QNode));
    (*QQ).front->next=NULL;
    (*QQ).rear=(*QQ).front;
    return  OK;
}

//链队的入队
Status EnQueue(LinkQueue* QQ,QElemType a){
    QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
    p->data=a;
    p->next=NULL;
    (*QQ).rear->next=p;
    (*QQ).rear=p;
    printf("En%d ",a);
    return  OK;
}


//链队的出队
Status  DeQueue(LinkQueue*  QQ,QElemType* e){
    if((*QQ).front==(*QQ).rear) return  ERROR;  //判断是否队空
    QueuePtr p=(*QQ).front->next;
    *e=p->data;
    (*QQ).front->next=p->next;
    if((*QQ).rear==p) (*QQ).rear=(*QQ).front;//如果出队的是尾结点
    free(p);
    printf("De%d ",*e);
    return  OK;
}

//销毁队列：从头结点开始依次释放所有结点
Status  DestroyQueue(LinkQueue* QQ){
    while((*QQ).front){
         QueuePtr p=(*QQ).front->next;
        free((*QQ).front);
        (*QQ).front=p;
    }
}

//取队头元素，不修改队头指针
QElemType GetHead(LinkQueue Q){
    if(Q.front==Q.rear) return  ERROR;
    return  Q.front->next->data;
}

//打印链队
Status PrintQueue(LinkQueue Q){
    QueuePtr p=Q.front->next;
    printf("print:");
    while(p) {
    printf("%d ",p->data);
    p=p->next;
    }
    return OK;
}

//简单调试
int main(){
    int m;
    int i=0;
    QElemType a;//入队的元素
    QElemType e;//出队的元素
    LinkQueue   Q;
    InitQueue(&Q);
    printf("请输入原始队列的元素个数：");
    scanf("%d",&m);
    for(i=0;i<m;i++){
        printf("请输入入队的元素：");
        scanf("%d",&a);
         EnQueue(&Q,a);
    }
    PrintQueue(Q);
    DeQueue(&Q,&e);
    printf("出队的元素为%d ",e);
    PrintQueue(Q);
}

注：结构体起别名

1.带头节点的循环链表表示队列，只设一个指针指向队尾元素节点（不设头指针）

设计置空队列，判断队列是否为空，入队和出队等算法

#include <stdio.h>
#include <malloc.h>
#define Max 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int QElemType;
//带头节点的循环链表表示队列，只设一个指针指向队尾元素节点（不设头指针）
//置空队列，判断队列是否为空，入队和出队等算法

//队列的链式储存结构
typedef struct  QNode{//链队结点包括数据域和指针域
    QElemType data;//数据域
    struct  QNode  *next;//指针域
}QNode,*QueuePtr;


typedef struct{
    QueuePtr rear;//队尾指针
}LinkQueue2;

//链队的初始化
Status  InitQueue2(LinkQueue2* QQ){
    (*QQ).rear=(QueuePtr)malloc(sizeof(QNode));
    (*QQ).rear->next=(*QQ).rear;
    return  OK;
}

//链队的入队
Status EnQueue2(LinkQueue2* QQ,QElemType a){
    QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
    p->data=a;
    p->next=(*QQ).rear->next;
    (*QQ).rear->next=p;
    (*QQ).rear=p;
    printf("En %d",a);
    return  OK;
}


//链队的出队
Status  DeQueue2(LinkQueue2*  QQ,QElemType* e){
    if((*QQ).rear==(*QQ).rear->next) {printf("the queue is empty"); return  ERROR;}  
    QueuePtr p=(*QQ).rear->next->next;
    *e=p->data;
    (*QQ).rear->next->next=p->next;
    if((*QQ).rear==p) (*QQ).rear=p->next;//如果出队的是尾结点
    free(p);
    printf("De %d",*e);
    return  OK;
}

//销毁队列：从头结点开始依次释放所有结点
Status  DestroyQueue2(LinkQueue2* QQ){
    while((*QQ).rear){
         QueuePtr p=(*QQ).rear->next;
        (*QQ).rear->next=p->next;
        free(p);
    }
}


//取队头元素，不修改队头指针
QElemType GetHead2(LinkQueue2 Q){
    if(Q.rear==Q.rear->next) return  ERROR;
    return  Q.rear->next->next->data;
}

//打印链队
Status PrintQueue2(LinkQueue2 Q){
    QueuePtr p=Q.rear->next->next;
    printf("print:");
    while(p!=Q.rear->next) {
    printf("%d ",p->data);
    p=p->next;
    }
    return OK;
}
//简单调试
int main(){ 
    int m;
    int i=0;
    QElemType a;//入队的元素
    QElemType e;//出队的元素
    LinkQueue2   Q;
    InitQueue2(&Q);
    printf("Please enter the number of elements in the original queue: ");
    scanf("%d",&m);
    for(i=0;i<m;i++){
        printf("Please enter the elements of the queue: ");
        scanf("%d",&a);
         EnQueue2(&Q,a);
    }
    PrintQueue2(Q);
    DeQueue2(&Q,&e);
    PrintQueue2(Q);
	printf("the head is %d ",GetHead2(Q));

}

顺序队

0.基本操作（牺牲一个空间）

循环顺序队包含数组（基地址），头指针（数组下标），尾指针（数组下标）
头指针指向队头元素，尾指针指向队尾元素的下一个
注意循环如何表示：一般要模max，且式子是减法时还要加max避免负数模max的情况
front=rear:Queue is empty
(rear+1)%Max=front：Queue is full

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define Max 8
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int QElemType;


//队列的顺序储存结构
typedef struct{
    QElemType *base;//存储空间的基地址
    int front;//头指针，指向队头元素
    int rear;//尾指针，指向队尾元素后面一个
}SqQueue;


//初始化
Status InitQueue(SqQueue* QQ){
    (*QQ).base=(QElemType*)malloc(sizeof(QElemType)*Max);
    if(!(*QQ).base) exit(OVERFLOW);
    (*QQ).front=(*QQ).rear=0;
    return OK;
} 

//求队列长度
int QueueLength(SqQueue Q){
    return (Q.rear-Q.front+Max) % Max;
}


//入队
Status EnQueue(SqQueue *QQ,QElemType a){
    if(((*QQ).rear+1)%Max==(*QQ).front){printf("Queue is full");return ERROR;}//判断队满
    (*QQ).base[(*QQ).rear]=a;
    (*QQ).rear=((*QQ).rear+1)% Max;
    printf("En %d",a);
    return OK;
}

//出队
Status DeQueue(SqQueue *QQ,QElemType* e){
    if((*QQ).front==(*QQ).rear){printf("Queue is empty");return ERROR;};//判断队空
    *e=(*QQ).base[(*QQ).front];
    (*QQ).front=((*QQ).front+1)%Max;
    printf("De %d",*e);
    return OK;
}

//打印顺序队
Status PrintQueue(SqQueue Q){
    if(Q.front==Q.rear) {printf("Queue is empty");return ERROR;};//判断队空
    int p=Q.front;
    printf("print:");
    while(p!=Q.rear){
        printf("%d ",Q.base[p]);
        p=(p+1)%Max;
    }
}

//简单调试
int main(){
    SqQueue Q;
    InitQueue(&Q);
    int m;
    int i;
    QElemType a;//存放入队元素
    QElemType e;//存放出队元素
    printf("Please enter the length of the original queue:");
    scanf("%d",&m);
    for(i=0;i<m;i++){
        printf("Please %dth data:",i+1);
        scanf("%d",&a);
        EnQueue(&Q,a);
    }
    
    for(i=0;i<3;i++){
        DeQueue(&Q,&e);
    }
    for(i=0;i<m;i++){
        printf("Please %dth data:",i+1);
        scanf("%d",&a);
        EnQueue(&Q,a);
    }
    PrintQueue(Q);

}

1.设置tag的不牺牲数组存储空间的循环顺序队

循环顺序队包含数组（基地址），头指针（数组下标），尾指针（数组下标）
头指针指向队头元素，尾指针指向队尾元素的下一个
注意循环如何表示：一般要模max，且式子是减法时还要加max避免负数模max的情况
用tag表示上一次操作是入队还是出队
rear=front&&tag=0 :Queue is empty 指针重叠，且上一次操作是出队
rear=front&&tag=1 :Queue is full 指针重叠，且上一次操作是入队

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define Max 8
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
typedef int Status;
typedef int QElemType;




//队列的顺序储存结构
typedef struct{
    QElemType *base;//存储空间的基地址
    int front;//头指针，指向队头元素
    int rear;//尾指针，指向队尾元素后面一个
}SqQueue;


//初始化
Status InitQueue(SqQueue* QQ){
    (*QQ).base=(QElemType*)malloc(sizeof(QElemType)*Max);
    if(!(*QQ).base) exit(OVERFLOW);
    (*QQ).front=(*QQ).rear=0;
    return OK;
} 

//求队列长度
int QueueLength(SqQueue Q){
    return (Q.rear-Q.front+Max) % Max;
}



//入队
Status EnQueue(SqQueue *QQ,QElemType a,int* tagptr){
    if((*QQ).rear==(*QQ).front&&*tagptr ) {
        printf("Queue is full");
        return ERROR;}//判断队满:两个指针重合，且上一次操作是入队
    (*QQ).base[(*QQ).rear]=a;
    (*QQ).rear=((*QQ).rear+1)% Max;
    printf("En %d",a);
    *tagptr=1;
    return OK;
}

//出队
Status DeQueue(SqQueue *QQ,QElemType* e,int* tagptr){
    if((*QQ).rear==(*QQ).front&&*tagptr==0 ) {printf("Queue is empty");return ERROR;}//判断队空:两个指针重合且上一次操作是出队
    *e=(*QQ).base[(*QQ).front];
    (*QQ).front=((*QQ).front+1)%Max;
    printf("De %d",*e);
    *tagptr=0;
    return OK;
}

//打印顺序队
Status PrintQueue(SqQueue Q,int tag){
    if(Q.rear==Q.front&&tag==0) {
        printf("Queue is empty");
        return ERROR;}//判断队空
    int p=Q.front;
    printf("print:");
    do//注意要先做一次循环，以免队满时（p==Q.rear）直接跳过循环
    {
        printf("%d ",Q.base[p]);
        p=(p+1)%Max;
    }while(p!=Q.rear);
    return OK;
}

//简单调试
int main(){
    SqQueue Q;
    InitQueue(&Q);
    int m;
    int i;
    QElemType a;//存放入队元素
    QElemType e;//存放出队元素
    int tag=0;
    printf("Please enter the length of the original queue:");
    scanf("%d",&m);
    for(i=0;i<m;i++){
        printf("Please %dth data:",i+1);
        scanf("%d",&a);
        EnQueue(&Q,a,&tag);
    }
    for(i=0;i<3;i++){
    DeQueue(&Q,&e,&tag);
    }
        for(i=0;i<5;i++){
        printf("Please %dth data:",i+1);
        scanf("%d",&a);
        EnQueue(&Q,a,&tag);
    }
    PrintQueue(Q,tag);
}

注：这篇博客写了队列的链式存储结构（牺牲一个存储空间/设置tag表示上次操作/设置变量记录每次操作后数组中元素个数）与顺序存储结构，很详细：队列的实现(c语言)

2.循环列队的两端操作

允许在循环队列的两端进行插入和删除操作，具体为如果允许在循环队列的两端都可以进行插入和删除操作。构造一个循环队列，实现从队头入队，从队尾出队并输出。约定从队头入队时向下标小的方向发展，从队尾入队时则向下标大的方向发展。
想法：
设置队头指针front和队尾指针rear,约定front指向队头元素的前位置， rear指向队尾元素。 定义满足 front- rear时为队空。从队尾删除元素，则rear向着下标减小的方向行走:从队头插入元素，front 同样向着下标减小的方向行走。因此，当满足rear==(front-1+maxSize)%maxSize时队满。