链式队列的实现

队列(C++)

/*---------------------- 简单队列的链式实现------------------------- */
/*
功能：
1、以一定数目的元素初始化一个队列
2、判断队列是否为空
3、按队列顺序展示队列元素值
4、删除一个队列结点
5、获得队列的第一个元素值
6、向队列中加入一个元素结点
*/

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef int Elemtype;
typedef struct Node {
    Elemtype data;
    Node *next;
} *queueNode;
typedef struct indexNode {
    queueNode head;
    queueNode rear;
} *indexQueue;

//函数声明
void initQueue(indexQueue);
queueNode initNode();
void initQueue(indexQueue , int);
void displayQueue(indexQueue);
bool isEmptyQueue(indexQueue);
Elemtype pop(indexQueue);
Elemtype getHead(indexQueue);
void push(indexQueue , Elemtype);

int main()
{
    indexQueue iQueue = (indexQueue)malloc(sizeof(indexQueue));
    //initQueue(iQueue);
    int length;
    cout << "输入要初始化队列长度：" << endl;
    cin >> length;
    cout << "输入 " << length << " 个元素值，用于初始化队列：" << endl;
    initQueue(iQueue , length);

    //测试：按顺序展示元素
    cout << "队列中的元素为：" << endl;
    displayQueue(iQueue);

    //测试：从队列中出一个元素
    Elemtype popReturn = pop(iQueue);
    cout << "出队列的第一个元素为：" << popReturn << endl;
    cout << "出队列一个元素后，队列里面的元素为：" << endl;
    displayQueue(iQueue);

    //测试：获得队列中的第一个元素值
    Elemtype headValue = getHead(iQueue);
    cout << "队列中第一个元素为：" << headValue <<  endl;
    cout << "获取元素后，队列中的元素值：" << endl;
    displayQueue(iQueue);

    //测试：向队列尾添加一个元素结点
    Elemtype eInsert;
    cout << "输入要添加到队列的结点的元素值：" << endl;
    cin >> eInsert;
    push(iQueue , eInsert);
    cout << "添加一个元素后，队列中的元素结点的值分别为：" << endl;
    displayQueue(iQueue);

    return 0;
}

//初始化一个空的队列
void initQueue(indexQueue iQueue) {
    iQueue->head = NULL;
    iQueue->rear = NULL;
}

//初始化一个结点
queueNode initNode() {
    queueNode qReturn = (queueNode)malloc(sizeof(Node));
    qReturn->next = NULL;
    return qReturn;
}


//初始化一个带元素值的队列
void initQueue(indexQueue iQueue , int length) {
    initQueue(iQueue);
    queueNode newQueue;
    for(int i = 0; i < length; i++) {
        newQueue = initNode();
        cin >> newQueue->data;
        if(i == 0) {
            iQueue->rear = newQueue;
            iQueue->head = newQueue;
        } else {
            iQueue->rear->next = newQueue;
            iQueue->rear = newQueue;
        }
    }
}

//展示队列里面所有元素
void displayQueue(indexQueue iQueue) {
    queueNode qCurr = iQueue->head;
    while(qCurr != NULL) {
        cout << qCurr->data << "  ";
        qCurr = qCurr->next;
    }
    cout << endl;
}

//判断队列元素是否为空
bool isEmptyQueue(indexQueue iQueue) {
    if(iQueue->head == iQueue->rear) {
        return true;
    }
    return false;
}

//取出一个队列元素
Elemtype pop(indexQueue iQueue) {
    if(isEmptyQueue(iQueue)) {
        return -1;
    }
    queueNode qCurr = iQueue->head;
    iQueue->head = qCurr->next;
    Elemtype eReturn = qCurr->data;
    free(qCurr);
    return eReturn;
}

//获得队列第一个元素
Elemtype getHead(indexQueue iQueue) {
    if(isEmptyQueue(iQueue)) {
        return -1;
    }
    return iQueue->head->data;
}

//向队列尾添加元素
void push(indexQueue iQueue , Elemtype insertValue) {
    queueNode qInsert = initNode();
    qInsert->data = insertValue;
    if(isEmptyQueue(iQueue)) {
        iQueue->head = qInsert;
        iQueue->rear = qInsert;
        return;
    }
    iQueue->rear->next = qInsert;
    iQueue->rear = qInsert;
}