队列的基本操作(数据结构)

队列的顺序实现

#include 
#include 
#include 

#define MaxSize 10//定义队列的长度

typedef struct{
	int front,rear;
	int data[MaxSize];
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
} 

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
	if(Q.front==Q.rear) return true;//空队列
	else return false; 
}

//入队
bool EnQueue(SqQueue &Q,int x){
	if((Q.rear+1)%MaxSize==Q.front){//判断队满
		return false; 
	}
	Q.data[Q.rear]=x;//新元素入队 
	Q.rear = (Q.rear+1)%MaxSize;//队尾指针加一取模 让队列循环使用 
	return true;
} 

//出队
int DeQueue(SqQueue &Q){
	if(Q.front==Q.rear) return false;//队列为空 
	int x;
	x = Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;//对头指针后移 
	return x;
} 
 
//获取对头元素 
int GetHead(SqQueue &Q){
	if(Q.front==Q.rear) return false;
	int x;
	x = Q.data[Q.front];
	return x;
} 

//计算队列元素个数
int CountQueue(SqQueue &Q){
	if(Q.front==Q.rear) return false;
	int count;
	count = (Q.rear+MaxSize-Q.front)%MaxSize;
	return count;
}
 
//输出栈 
bool PrintSqQueue(SqQueue &Q){
	if(Q.front==Q.rear) return false;
	for(int i=Q.front;i<Q.rear;i++)
		printf("%d ",Q.data[i]);
	printf("\n");
	return true;
}

int main(){
	SqQueue Q;
	InitQueue(Q);
	printf("-----入队-----\n");
	EnQueue(Q,1);
	EnQueue(Q,2);
	EnQueue(Q,3);
	EnQueue(Q,4);
	EnQueue(Q,5);
	int count;
	count=CountQueue(Q);
	printf("队内元素个数为:%d\n",count);
	PrintSqQueue(Q);
	printf("-----出队-----\n");
	int x;
	x=DeQueue(Q);
	printf("%d出队\n",x);
	x=DeQueue(Q);
	printf("%d出队\n",x);
	x=DeQueue(Q);
	printf("%d出队\n",x);
	count=CountQueue(Q);
	printf("队内元素个数为:%d\n",count);
	PrintSqQueue(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

队列的链式实现

#include 
#include 
#include 

//链式队列结点 
typedef struct LinkNode{
	int data;
	struct LinkNode *next;
}LinkNode; 

//链式队列 
typedef struct{
	LinkNode *front,*rear;
}LinkQueue;

//队列初始化(带头结点) 
void InitQueue1(LinkQueue &Q){
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next=NULL;
}

//队列初始化(不带头结点)
void InitQueue2(LinkQueue &Q){
	Q.front=NULL;
	Q.rear=NULL;
} 

//判断队列是否为空(带头结点)
bool IsEmpty1(LinkQueue Q){
	if(Q.front==Q.rear) return true;
	else return false; 
} 

//判断队列是否为空(不带头结点)
bool IsEmpty2(LinkQueue Q){
	if(Q.front==NULL) return true;
	else false;
} 

//入队(带头结点)
void EnQueue1(LinkQueue &Q,int x){
	LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=x;
	s->next=NULL;
	Q.rear->next=s;//新节点插入到rear之后 
	Q.rear=s;//修改表尾指针 
} 
 
//入队(不带头结点)
void EnQueue2(LinkQueue &Q,int x){
	LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=x;
	s->next=NULL;
	if(Q.front==NULL){//空队列中插入第一个元素 
		Q.front=s;//修改队头队尾指针 
		Q.rear=s;
	}
	else{//新节点插入到rear结点之后 
		Q.rear->next=s;
		Q.rear=s;
	}
}

//出队(带头结点) 
int DeQueue1(LinkQueue &Q){
	if(Q.front==Q.rear){//空 
		return false;
	}
	LinkNode *p=Q.front->next;
	int x;
	x=p->data;
	Q.front->next = p->next;
	if(Q.rear==p) Q.rear=Q.front;//最后一个结点出队，修改rear指针
	free(p);
	return x ;
} 

//出队(不带头结点)
int DeQueue2(LinkQueue &Q){
	if(Q.front==NULL) return false;//空 
	LinkNode *p=Q.front;
	int x;
	x=p->data; 
	Q.front=p->next;//修改front指针 
	if(Q.rear==p){//最后一个结点出队 
		Q.front=NULL;
		Q.rear=NULL;
	}
	free(p);
	return x; 
} 

//打印队列 (带头结点)
void PrintQueue1(LinkQueue &Q)
{
	LinkNode *temp=Q.front->next;
	printf("打印队列:");
	while(temp)
	{
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

//打印队列 (不带头结点)
void PrintQueue2(LinkQueue &Q)
{
	LinkNode *temp=Q.front;
	printf("打印队列:");
	while(temp)
	{
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

int main(){
	printf("--------带头结点-------\n");
	LinkQueue Q;
	InitQueue1(Q);
	printf("开始进队列\n");
	EnQueue1(Q,1);
	EnQueue1(Q,2);
	EnQueue1(Q,3);
	EnQueue1(Q,4);
	EnQueue1(Q,5);
	PrintQueue1(Q);//打印队列 
	if (!IsEmpty1(Q)) printf("非空队列\n");
	else printf("空队列\n");
	int x;
	x=DeQueue1(Q);
	printf("%d出队列\n",x);
	x=DeQueue1(Q);
	printf("%d出队列\n",x);
	x=DeQueue1(Q);
	printf("%d出队列\n",x);
	PrintQueue1(Q);//打印队列 
	
	printf("--------不带头结点-------\n");
	LinkQueue P;
	InitQueue2(P);
	printf("开始进队列\n");
	EnQueue2(P,1);
	EnQueue2(P,2);
	EnQueue2(P,3);
	EnQueue2(P,4);
	EnQueue2(P,5);
	PrintQueue2(P);//打印队列 
	if (!IsEmpty2(P)) printf("非空队列\n");
	else printf("空队列\n");
	int y;
	y=DeQueue2(P);
	printf("%d出队列\n",y);
	y=DeQueue2(P);
	printf("%d出队列\n",y);
	y=DeQueue2(P);
	printf("%d出队列\n",y);
	PrintQueue2(P);//打印队列 
	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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162