带头结点
#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode {
int data;
struct LinkNode *next;
}LinkNode;
typedef struct {
LinkNode *front, *rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
bool DeQueue(LinkQueue &Q, int &x);
bool IsEmpty(LinkQueue Q);
int main(void) {
LinkQueue Q;
int x;
InitQueue(Q);
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
EnQueue(Q, 4);
EnQueue(Q, 5);
EnQueue(Q, 6);
EnQueue(Q, 7);
DeQueue(Q, x);
DeQueue(Q, x);
DeQueue(Q, x);
DeQueue(Q, x);
if (!IsEmpty(Q)) {
printf("x=%d\n", x);
}
return 0;
}
//初始化队列
void InitQueue(LinkQueue &Q) {
//初始时,队头和队尾指针指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
//判断队列是否为空
bool QueueEmpty(LinkQueue Q) {
if (Q.rear == Q.front) { //队空条件
return true;
} else {
return false;
}
}
//入队(带头结点)
void EnQueue(LinkQueue &Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s; //新节点插入到rear之后
Q.rear = s; //修改表尾指针
}
//队头元素出队
bool DeQueue(LinkQueue &Q, int &x) {
if (Q.front == Q.rear) { //空队
return false;
}
LinkNode *p = Q.front->next;
x = p->data; //用变量x返回队头元素
Q.front->next = p->next; //修改头结点的next指针
if (Q.rear == p) { //此次是最后一个节点出队
Q.rear = Q.front; //修改rear指针
}
free(p); //释放节点空间
return true;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q) {
if (Q.front == Q.rear) {
return true;
} else {
return false;
}
}
不头结点
#include<stdio.h>
#include<stdlib.h>
typedef struct LinkNode {
int data;
struct LinkNode *next;
}LinkNode;
typedef struct {
LinkNode *front, *rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q, int x);
bool DeQueue(LinkQueue &Q, int &x);
bool IsEmpty(LinkQueue Q);
int main(void) {
LinkQueue Q;
int x;
InitQueue(Q);
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
EnQueue(Q, 4);
EnQueue(Q, 5);
EnQueue(Q, 6);
EnQueue(Q, 7);
DeQueue(Q, x);
DeQueue(Q, x);
DeQueue(Q, x);
DeQueue(Q, x);
if (!IsEmpty(Q)) {
printf("x=%d\n", x);
}
return 0;
}
//初始化队列
void InitQueue(LinkQueue &Q) {
//初始时,队头和队尾指针指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
//判断队列是否为空
bool QueueEmpty(LinkQueue Q) {
if (Q.rear == Q.front) { //队空条件
return true;
} else {
return false;
}
}
//入队(带头结点)
void EnQueue(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 {
Q.rear->next = s; //新节点插入到rear之后
Q.rear = s; //修改表尾指针
}
}
//队头元素出队
bool DeQueue(LinkQueue &Q, int &x) {
if (Q.front == Q.rear) { //空队
return false;
}
LinkNode *p = Q.front; //p指向此次出队的节点
x = p->data; //用变量x返回队头元素
Q.front = p->next; //修改front指针
if (Q.rear == p) { //此次是最后一个节点出队
Q.rear = NULL; //rear指向NULL
Q.front = NULL; //front指向NULL
}
free(p); //释放节点空间
return true;
}
bool IsEmpty(LinkQueue Q) {
if (Q.front == NULL) {
return true;
} else {
return false;
}
}