队列---数据结构

定义

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。

队头（Front）：允许删除的一端，又称队首。

队尾（Rear）：允许插入的一端。

循环队列元素入队

循环队列元素出队

队列的链式存储

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

动画网站：https://www.cs.usfca.edu/~galles/visualization/QueueLL.html 

代码

流程：判断循环队列是否为空，入队，出队

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//数组,存储MaxSize - 1个元素
    int front,rear;//队列头,队列尾
}SqQueue;

void InitQueue(SqQueue &Q){
    Q.front = Q.rear = 0;//初始化循环队列,就是让头和尾都指向零号
}

//普安段循环队列是否为空
bool isEmpty(SqQueue &Q){
    return Q.rear == Q.front;
}

//入队
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;//rear 要+1,如果大于数组最大下标,回到开头
    return true;

}

//出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front){//队列为空,无法出队
        return false;
    }
    x = Q.data[Q.front];//出队
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

int main(){
    SqQueue Q;
    InitQueue(Q);
    bool ret;
    ret = isEmpty(Q);
    if(ret){
        printf("SqQueue is Empty\n");
    }else{
        printf("SqQueue is not Empty\n");
    }
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    ret = EnQueue(Q,6);
    ret = EnQueue(Q,7);
    if(ret){
        printf("EnQueue success\n");
    }else{
        printf("EnQueue failed\n");
    }
    ElemType element;
    ret = DeQueue(Q,element);
    if(ret){
        printf("DeQueue success\n");
    }else{
        printf("DeQueue failed\n");
    }
    return 0;
}

效果

队列的链表实现

代码

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

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front, *rear;//链表头,链表尾,也可以称为队头,队尾
}LinkQueue;

//初始化队列
void InitQueue(LinkQueue &Q){
        Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//头和尾指向同一个结点
        Q.front -> next = NULL;//头结点的next指针为NULL
}

//入队
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *pnew = (LinkNode*) malloc(sizeof(LinkNode));
    pnew -> data = x;
    pnew -> next =NULL;//要让next为NULL;
    Q.rear -> next = pnew;//尾指针的next指向pnew,因为从尾部入队
    Q.rear = pnew;//rear要指向新的尾部
}


bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.rear == Q.front){//队列为空
        return false;
    }
    LinkNode* q = Q.front -> next;//拿到第一个结点,存入q
    x = q -> data;//获取要出对的元素值
    Q.front -> next = q->next;//让第一个结点断链
    if(Q.rear == q){//链表只剩余一个结点时,被删除后,要改变rear
        Q.rear = Q.front;
    }
    free(q);
    return true;
}
int main(){
    LinkQueue Q;
    bool ret;
    ElemType element;//存储出对元素
    InitQueue(Q);//初始化队列
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    ret = DeQueue(Q,element);
    if(ret){
        printf("DeQueue success element=%d\n",element);
    }else{
        printf("DeQueue failed\n",element);
    }
    return 0;
}

效果