資料結構——鍊隊列

鍊隊列

空隊列

元素x入隊列

元素y入隊列

元素x出隊列

C++代碼實作

/*------鍊隊列基本操作-------*/
/*
front指針指向頭結點（第一個結點的前一個）
rear指針指向最後一個結點
*/
#include<iostream>
#include<stdlib.h>
using namespace std;

#define OK 1
#define ERROR -1
#define OVERFLOW -2

typedef int Status;
typedef int QElemType;

#define MAXSIZE 100

typedef struct Qnode {
    QElemType data;
    struct Qnode* next;
}Qnode, * QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Status InitLQueue(LinkQueue& Q) {
    Q.front = new Qnode;
    if (!Q.front) exit(OVERFLOW);
    Q.rear = Q.front;
    Q.front->next = NULL;
    return OK;
}

// 判斷鍊隊列是否為空
bool LQueueEmpty(LinkQueue Q) {
    return (Q.front == Q.rear);
}

// 入隊
Status PushLQueue(LinkQueue& Q, QElemType e) {
    QueuePtr q;
    q = new Qnode;
    if (!q)  exit(OVERFLOW);
    q->data = e;
    q->next = NULL;
    Q.rear->next = q;
    Q.rear = q;
    return OK;
}

// 出隊
Status PopLQueue(LinkQueue& Q, QElemType& e) {
    QueuePtr q;
    if(LQueueEmpty(Q)) return ERROR;
    q = Q.front->next;
    e = q->data;
    Q.front->next = q->next;
    if (Q.rear == q) Q.rear = Q.front;
    delete q;
    return OK;
}

// 銷毀鍊隊列
Status DestroyQueue(LinkQueue& Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}

// 擷取隊頭元素
Status GetHead(LinkQueue Q, QElemType& e) {
    if (LQueueEmpty(Q)) return ERROR;
    e = Q.front->next->data;
    return OK;
}

// 建立鍊隊列
void CreateLQueue(LinkQueue& Q, int m) {
    QElemType e;
    for (int i = 1; i <= m; i++) {
        cout << "請輸入第" << i << "個元素: ";
        cin >> e;
        PushLQueue(Q, e);
    }
}

// 輸對外連結隊列
void OutPut(LinkQueue Q) {
    QueuePtr q;
    q = new Qnode;
    q = Q.front->next;
    while (q) {
        cout << q->data << " ";
        q = q->next;
    }
    cout << endl;
}

int main()
{
    // 測試代碼
    LinkQueue Q;
    int m;
    QElemType e;
    InitLQueue(Q);
    cout << "請輸傳入連結隊列的長度: ";
    cin >> m;
    CreateLQueue(Q, m);
    cout << "鍊隊列元素為: ";
    OutPut(Q);

    GetHead(Q, e);
    cout << "隊頭元素為: " << e << endl;

    cout << "請輸入入隊元素: ";
    cin >> e;
    PushLQueue(Q, e);
    cout << "鍊隊列元素為: ";
    OutPut(Q);

    PopLQueue(Q, e);
    cout << "出列元素為: " << e << endl;
    cout << "鍊隊列元素為: ";
    OutPut(Q);

    return 0;
}           

請輸傳入連結隊列的長度: 3
請輸入第1個元素: 1
請輸入第2個元素: 2
請輸入第3個元素: 3
鍊隊列元素為: 1 2 3
隊頭元素為: 1
請輸入入隊元素: 4
鍊隊列元素為: 1 2 3 4
出隊元素為: 1
鍊隊列元素為: 2 3 4