[C++知识库]数据结构_队列_基本操作的c++实现

#include <iostream>

using namespace std;

//队列Queue
/*---------------------顺序队列------------------*/
//定义
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int front,rear;   //队头指针（规定指向队头元素），队尾指针（规定指向队尾元素的后一个位置，即下一个应该插入的位置）
}SqQueue;

//初始化
void InitSqQueue(SqQueue &Q){
    Q.front=Q.rear=0;
}

//队列判空
bool EmptySqQueue(SqQueue Q){
    return (Q.front==Q.rear);
}

//队列判满
bool FullSqQueue(SqQueue Q){
    return ((Q.rear+1)%MaxSize==Q.front);
}
//队列的判满/判空也可以采用以下两种方式：
//1.增加size变量记录队列长度；
//2.增加tag=0/1用于标记最近的一次操作是出队/入队。

//入队
bool EnQueue(SqQueue &Q, int x){
    if((Q.rear+1)%MaxSize==Q.front)     //！队列已满（为了区别于队空条件，必须牺牲掉一个位置）
        return false;
    Q.data[Q.rear]=x;            //新元素插入队尾
    Q.rear=(Q.rear+1)%MaxSize;//！队尾指针加1取余（即取模），在数论中，常表示为a MOD b
    return true;
}

//出队
bool DeQueue(SqQueue &Q, int &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,int &x){
    if(Q.front==Q.rear)
        return false;//队列为空
    x=Q.data[Q.front];
    return true;
}

//!!!!!队列元素个数：(rear+MaxSize-front)%MaxSize

/*----------------------------链式队列---------（带头结点&不带头结点）------------------------*/
//定义
typedef struct LinkNode{   //链式队列结点
    int data;
    struct LinkNode *next;
}LinkNode;
typedef struct{           //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//初始化队列（带头结点）
void InitLQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//判空（带头结点）
bool EmptyLQueue(LinkQueue Q){
    return (Q.front==Q.rear);
    //或者return (Q.front->next==NULL);
}

//初始化队列（不带头结点）
void InitQueue_NoHeadNode(LinkQueue &Q){
    Q.front=Q.rear=NULL;
}

//判空（不带头结点）
bool EmptyQueue_NoHeadNode(LinkQueue Q){
    return (Q.front==NULL);
    //或者return (Q.rear==NULL);
    //或者return (Q.rear==Q.front);
}

//入队：队尾入队（带头结点）,带头结点时插入第一个元素的操作和插入后续元素的操作相同
bool EnQueue(LinkQueue &Q, int x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;//存储空间分配失败
    p->data=x;
    p->next=NULL;
    Q.rear->next=p;         //带头结点时front指向的是头结点而不是第一个元素
    Q.rear=p;
    return true;
}

//不带头结点：在空队列中插入第一个元素的操作需要特别处理
//入队：队尾入队（不带头结点）
bool EnQueue_NoHeadNode(LinkQueue &Q, int x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL)
        return false;//存储空间分配失败
    p->data=x;
    p->next=NULL;
    if(Q.front==NULL){          //！！！！！单独考虑：第一个元素入队的情况
        Q.front=p;
        Q.rear=p;
    }else{
        Q.rear->next=p;
        Q.rear=p;
    }
    return true;
}

//出队：队头出队（带头结点）
bool DeQueue(LinkQueue &Q,int &x){
    if(Q.front==Q.rear)
        return false;//队列为空
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(p==Q.rear)               //！！！！！单独考虑：最后一个元结点出队的情况
        Q.rear=Q.front;
    free(p);
    return true;
}

//出队：队头出队（不带头结点）
bool DeQueue_NoHeadNode(LinkQueue &Q, int &x){
    if(Q.front==NULL)
        return false;  //队列为空
    LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){            //！！！！最后一个结点出队
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;

}



int main()
{

    return 0;
}