数据结构——顺序队列

队列的顺序

• 用一维数组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