队列(Queue) C 语言实现
程序员文章站
2024-03-18 12:34:22
...
https://blog.csdn.net/song_hui_xiang/article/details/47146503
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素成为出队。队列中没有元素时,称为空队列。因为队列只允许在一段插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。
一、队列的数组实现
队列的顺序存储结构通常由一个一维数组、一个记录队列头元素位置的变量front、一个记录队列尾元素位置的变量rear以及记录队列元素个数的变量size组成。
#include <stdio.h>
#include <stdlib.h>
#define ElementType int //存储数据元素的类型
#define MAXSIZE 6 //存储数据元素的最大个数
#define ERROR -99 //ElementType的特殊值,标志错误
typedef struct {
ElementType data[MAXSIZE];
int front; //记录队列头元素位置
int rear; //记录队列尾元素位置
int size; //存储数据元素的个数
}Queue;
Queue* CreateQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
if (!q) {
printf("空间不足\n");
return NULL;
}
q->front = -1;
q->rear = -1;
q->size = 0;
return q;
}
int IsFullQ(Queue* q) {
return (q->size == MAXSIZE);
}
void AddQ(Queue* q, ElementType item) {
if (IsFullQ(q)) {
printf("队列已满\n");
return;
}
q->rear++;
q->rear %= MAXSIZE;
q->size++;
q->data[q->rear] = item;
}
int IsEmptyQ(Queue* q) {
return (q->size == 0);
}
ElementType DeleteQ(Queue* q) {
if (IsEmptyQ(q)) {
printf("空队列\n");
return ERROR;
}
q->front++;
q->front %= MAXSIZE; //0 1 2 3 4 5
q->size--;
return q->data[q->front];
}
void PrintQueue(Queue* q) {
if (IsEmptyQ(q)) {
printf("空队列\n");
return;
}
printf("打印队列数据元素:\n");
int index = q->front;
int i;
for (i = 0; i < q->size; i++) {
index++;
index %= MAXSIZE;
printf("%d ", q->data[index]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
Queue* q = CreateQueue();
AddQ(q, 0);
AddQ(q, 1);
AddQ(q, 2);
AddQ(q, 3);
AddQ(q, 4);
AddQ(q, 5);
PrintQueue(q);
DeleteQ(q);
DeleteQ(q);
DeleteQ(q);
PrintQueue(q);
AddQ(q, 6);
AddQ(q, 7);
AddQ(q, 8);
PrintQueue(q);
return 0;
}
二、队列的链表实现
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。队列指针front指向链表头部方便删除操作,队列指针rear指向链表尾部方便插入操作。
#include <stdio.h>
#include <stdlib.h>
#define ElementType int
#define ERROR -99 //ElementType的特殊值,标志错误
typedef struct Node {
ElementType data;
struct Node* next;
}QNode;
typedef struct {
QNode* front; //指向对头节点
QNode* rear; //指向队尾节点
}Queue;
Queue* CreateQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
if (!q) {
printf("空间不足!\n");
return NULL;
}
q->front = NULL;
q->rear = NULL;
return q;
}
void AddQ(Queue* q, ElementType item) {
QNode* qNode = (QNode*)malloc(sizeof(QNode));
if (!qNode) {
printf("空间不足!\n");
return;
}
qNode->data = item;
qNode->next = NULL;
if (q->front == NULL) {
q->front = qNode;
}
if (q->rear == NULL) {
q->rear = qNode;
}
else {
q->rear->next = qNode;
q->rear = qNode;
}
}
int IsEmptyQ(Queue* q){
return (q->front == NULL);
}
ElementType DeleteQ(Queue* q) {
if (IsEmptyQ(q)) {
printf("空队列\n");
return ERROR;
}
QNode* temp = q->front;
ElementType item;
if (q->front == q->rear) { //若队列只有一个元素
q->front = NULL;
q->rear = NULL;
}
else {
q->front = q->front->next;
}
item = temp->data;
free(temp);
return item;
}
void PrintQueue(Queue* q) {
if (IsEmptyQ(q)) {
printf("空队列\n");
return;
}
printf("打印队列数据元素:\n");
QNode* qNode = q->front;
while (qNode != NULL) {
printf("%d " , qNode->data);
qNode = qNode->next;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
Queue* q = CreateQueue();
AddQ(q, 1);
PrintQueue(q);
DeleteQ(q);
PrintQueue(q);
AddQ(q, 2);
AddQ(q, 3);
AddQ(q, 4);
PrintQueue(q);
DeleteQ(q);
DeleteQ(q);
PrintQueue(q);
AddQ(q, 5);
AddQ(q, 6);
PrintQueue(q);
return 0;
}
上一篇: vb.net编写的吃蘑菇小游戏(贪吃蛇)
下一篇: 数据结构-线性结构之队列