数据结构——顺序队列

队列的顺序

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