DataStructure_LinkQueue

链队的基本操作

声明链队

#include "iostream"
using namespace std;
//声明
typedef int ElemType;
typedef struct LinkNode{        //链式队列节点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {                //链式队列
    LinkNode *front,*rear;      //队列的队头front和队尾rear
}LinkQueue;

初始化

//初始化队列 带头节点
void InitQueue(LinkQueue &Q){
    //初始front和rear都指向头节点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

注释:
	注意带头节点和不带头节点
	带头节点:Q.front->next=NULL
	不带头节点: Q.front==NULL && Q.rear==NULL

判断是否为空

//判断是否为空(带头节点)
bool IsEmpty(LinkQueue Q){
    if (Q.front=Q.rear){
        return true;
    }
    else
        return false;
}

新元素入队

//新元素入队(带头节点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode*) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;       //新节点加入到s之后
    Q.rear=s;               //修改尾指针 当然front一直都在前面指向头
                            //因为插入时尾巴插入
}

队列出队

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

查找第一个元素

//查找第一个队头元素
bool GetHead(LinkQueue Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;
    x = Q.front->next->data;

}

打印队列

//打印队列
void PrintQueue(LinkQueue Q){
    LinkNode *tmp = Q.front->next;
    while (tmp!=NULL){
        cout<<tmp->data<<" ";
        tmp=tmp->next;
    }
    cout<<endl;
}

全部代码

#include <stdio.h>
#include "iostream"
using namespace std;
//声明
typedef int ElemType;
typedef struct LinkNode{        //链式队列节点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {                //链式队列
    LinkNode *front,*rear;      //队列的队头front和队尾rear
}LinkQueue;

//初始化队列 带头节点
void InitQueue(LinkQueue &Q){
    //初始front和rear都指向头节点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//判断是否为空
bool IsEmpty(LinkQueue Q){
    if (Q.front=Q.rear){
        return true;
    }
    else
        return false;
}
//新元素入队(带头节点)
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode*) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;       //新节点加入到s之后
    Q.rear=s;               //修改尾指针 当然front一直都在前面指向头
                            // 因为插入时尾巴插入
}
//队列出队(带头节点)
bool DeQueue(LinkQueue &Q,ElemType &x){
    if (Q.front==Q.rear)
        return false;       //空队列
    LinkNode *p = Q.front->next;
    x=p->data;                  //用变量x返回队头元素 队头front 只能出队
    Q.front->next = p->next;    //修改头节点的指向next指针
    if (Q.rear==p){             //此次是最后一个节点出队
        Q.rear=Q.front;         //修改rear指针
    }
    free(p);                    //释放节点空间
    return true;
}
//查找第一个队头元素
bool GetHead(LinkQueue Q,ElemType &x){
    if (Q.front == Q.rear)
        return false;
    x = Q.front->next->data;

}
//打印队列
void PrintQueue(LinkQueue Q){
    LinkNode *tmp = Q.front->next;
    while (tmp!=NULL){
        cout<<tmp->data<<" ";
        tmp=tmp->next;
    }
    cout<<endl;
}
int main(){
    LinkQueue Q;
    InitQueue(Q);
    for (int i = 5; i >=1 ; i--) {
        EnQueue(Q,i);
        cout<<"此时加入元素:"<<i<<endl;
    }
    PrintQueue(Q);
    int head;
    GetHead(Q,head);
    cout<<"目前的队头元素是:"<<head<<endl;
    int tail;
    DeQueue(Q,tail);
    cout<<"删除队头元素:"<<tail<<endl;
    PrintQueue(Q);

}

执行结果

此时加入元素:5
此时加入元素:4
此时加入元素:3
此时加入元素:2
此时加入元素:1
5 4 3 2 1
目前的队头元素是:5
删除队头元素:5
4 3 2 1