数据结构队列的链式表示

队列链式表示的抽象类型表示及相关运算(C语言实现) 文章目录

一.队列链式表示抽象类型定义
二.链式队列的基本运算

1.链式队列的抽象类型定义

#define ERROR 0
#define OK 1
#define NULLQUE 1
#define NULLDATA 0

#include 

typedef int ElemType;
typedef struct LinkQue {
    ElemType data;//数据域
    struct LinkQue *next;//指针域
} LinkQueNode;
typedef struct {
    LinkQueNode *front, *rear; //头指针与尾指针
} LiQue;

2.链式队列的初始化

int InitQue(LiQue *L) {

    LinkQueNode *temp; //创建工作指针
    temp = (LinkQueNode *) malloc(sizeof(LinkQueNode));
    temp->next = NULL;  //头结点置空
    L->front = temp;    //队头指向头结点
    L->rear = temp;     //队尾指向头结点
    return OK;
    
}

3.链式队列判空

int EmptyQue(LiQue *L){
    
    if(L->front == L->rear)
        return NULLQUE;
    
    return 0;

}

4.入队

int EnterQue(LiQue *L,ElemType edata){

    LinkQueNode *temp;
    temp = (LinkQueNode *)malloc(sizeof(LinkQueNode));

    if(!temp)
        return ERROR;

    temp->data = edata;
    temp->next = NULL;
    L->rear->next = temp;//新结点入队
    L->rear = temp;//修改尾指针
    return OK;

}

5.出队

int OutQue(LiQue *L){
    
    LinkQueNode *temp;
    
    if(EmptyQue(L))
        return ERROR;//队空
    else{
        temp = L->front->next; //定位L队列原队头
        L->front->next = temp->next;//置换队头成为新队头
        free(temp);
        
        if(L->front->next == NULL)//如果原队列只有一个元素且唯一元素出队后要重置队列
            L->rear == L->front;
        return OK;
    }    
    
}

6.取队头元素

ElemType GetHead(LiQue *L) {

    LinkQueNode *temp;
    if (EmptyQue(L)) {//判对空
        return NULLDATA;
    } else {
        temp = L->front->next;//定位L队列原队头
        return temp->data;//返回队首元素
    }

}