欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列(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;
}