链队列

空队列

元素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;
}

  

 

  
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
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
 

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

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

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