資料結構——順序隊列

隊列的順序

• 用一維數組base[M]

• 空隊标志： front = rear
• 入隊：base[rear++] = x
• 出隊：x = base[front++]

存在的問題

front ≠ 0

rear = M時，

假溢出

解決方法——循環隊列

• 實作：利用模運算

  • 入隊：

    base[rear] = x;

    rear = (rear+1) % M;

  • 出隊：

    x = base[front];

    front = (front + 1) % M;

C++代碼實作

#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 {
//    QElemType elem[MAXSIZE];
//    QElemType* rear;  // 隊尾指針
//    QElemType* front;  // 隊頭指針
//    int length;  // 長度
//}SqQueue;

/*------------動态配置設定------------*/
typedef struct {
    QElemType* elem;  // 動态配置設定存儲空間初始化
    int rear;  // 尾指針
    int front;  // 頭指針
}SqQueue;

// 構造空隊列
Status InitSqQueue(SqQueue& Q) {
    Q.elem = new QElemType[MAXSIZE];
    if (!Q.elem) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;

}

// 隊列長度
int QueueLength(SqQueue Q) {
    return(Q.rear - Q.front) % MAXSIZE;
}

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

// 判斷隊列是否滿
bool IsSqQueueFull(SqQueue Q) {
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

// 入隊
Status PushSqQueue(SqQueue& Q, QElemType e) {
    if (IsSqQueueFull(Q)) return ERROR;
    Q.elem[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

// 出隊
Status PopSqQueue(SqQueue& Q, QElemType &e) {
    if (IsSqQueueEmpty(Q)) return ERROR;
    e = Q.elem[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

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

// 輸出隊列
void OutPut(SqQueue Q) {
    int i;
    i = Q.front;
    while (i != Q.rear) {
        cout << Q.elem[i] << " ";
        i = (i + 1) % MAXSIZE;
    }
    cout << endl;
}

int main()
{
    // 測試代碼
    SqQueue Q;
    QElemType e;
    int m;
    InitSqQueue(Q);
    cout << "請輸入隊列的長度: ";
    cin >> m;
    CreatSqQueue(Q, m);
    OutPut(Q);

    cout << "隊列的長度為: " << QueueLength(Q) << endl;

    cout << "請輸入入隊元素: ";
    cin >> e;
    PushSqQueue(Q, e);
    cout << "隊列元素為: ";
    OutPut(Q);
    cout << "隊列的長度為: " << QueueLength(Q) << endl;

    PopSqQueue(Q, e);
    cout << "出隊元素為: " << e << endl;
    cout << "隊列元素為: ";
    OutPut(Q);
    cout << "隊列的長度為: " << QueueLength(Q) << endl;

    return 0;
}           

請輸入隊列的長度: 3
請輸入第1個元素的值: 1
請輸入第2個元素的值: 2
請輸入第3個元素的值: 3
1 2 3
隊列的長度為: 3
請輸入入隊元素: 4
隊列元素為: 1 2 3 4
隊列的長度為: 4
出隊元素為: 1
隊列元素為: 2 3 4
隊列的長度為: 3