数据结构——顺序队列

队列的顺序

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
 

请输入队列的长度: 3
请输入第1个元素的值: 1
请输入第2个元素的值: 2
请输入第3个元素的值: 3
1 2 3
队列的长度为: 3
请输入入队元素: 4
队列元素为: 1 2 3 4
队列的长度为: 4
出队元素为: 1
队列元素为: 2 3 4
队列的长度为: 3

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/102902146