C Queue Demo

Updated on with 12 views and 0 comments

queue.h

#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>
typedef int Item;
#define MAXQUEUE 10
typedef struct node
{
    Item item;
    struct node *next;
} Node;

typedef struct queue
{
    // 队列首项
    Node *front;
    // 队列尾项
    Node *rear;
    // 队列长度
    int items;
} Queue;
// 初始化队列
void InitializeQueue(Queue *pq);
// 队列是否满了
bool QueueIsFull(const Queue *pq);
// 队列是否空了
bool QueueIsEmpty(const Queue *pq);
// 队列项数
int QueueItemCount(const Queue *pq);
// 入队
bool EnQueue(Item item, Queue *pq);
// 出队
bool DeQueue(Item *pitem, Queue *pq);
// free memory
void EmptyQueue(Queue *pq);
void showAll(Queue *pq);
#endif

queue.c

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
// 拷贝节点
static void CopyToNode(Item item, Node *pn);
// 拷贝项
static void CopyToItem(Node *pn, Item *pi);
// 初始化队列
void InitializeQueue(Queue *pq)
{
    pq->front = pq->rear = NULL;
    pq->items = 0;
};
// 队列是否满了
bool QueueIsFull(const Queue *pq)
{
    return pq->items == MAXQUEUE;
};
// 队列是否空了
bool QueueIsEmpty(const Queue *pq)
{
    return pq->items == 0;
}
// 队列项数
int QueueItemCount(const Queue *pq)
{
    return pq->items;
}
// 入队
bool EnQueue(Item item, Queue *pq)
{
    // 新建一个要插入队的节点
    Node *pnew;
    // 队列是否满了
    if (QueueIsFull(pq))
    {
        return false;
    }
    // 为元素分配内存
    pnew = (Node *)malloc(sizeof(Node));
    // 是否分配好了内存
    if (pnew == NULL)
    {
        return false;
    }
    // 节点赋值
    CopyToNode(item, pnew);
    // 下一个节点为null
    pnew->next = NULL;
    // 查看队列是否为空
    if (QueueIsEmpty(pq))
    {
        // 如果为空的话,pq队列的首项为 pnew
        pq->front = pnew;
    }
    else
    {
        // 否则插入尾项的下一个位置
        pq->rear->next = pnew;
    }
    // 更新pq队列的尾项
    pq->rear = pnew;
    // 项 +1
    pq->items++;
    return true;
}
// 出队
bool DeQueue(Item *pitem, Queue *pq)
{
    Node *pt;
    // 是否为空队列
    if (QueueIsEmpty(pq))
    {
        return false;
    }
    // pitem指向 队首的item
    CopyToItem(pq->front, pitem);
    // pt 指向 队首
    pt = pq->front;
    // 队首为下一个元素
    pq->front = pq->front->next;
    // 释放内存
    free(pt);
    // 项数-1
    pq->items--;
    if (pq->items == 0)
    {
        pq->rear = NULL;
    }
    return true;
}
// free memory
void EmptyQueue(Queue *pq)
{
    Item dummy;
    while (!QueueIsEmpty(pq))
    {
        DeQueue(&dummy, pq);
    }
}

static void CopyToNode(Item item, Node *pn)
{
    pn->item = item;
}
static void CopyToItem(Node *pn, Item *pi)
{
    *pi = pn->item;
}

test

#include <stdio.h>
#include "queue.h"

int main(void)
{
    Queue line;
    Item item;
    char ch;
    InitializeQueue(&line);
    puts("Testing the queue interface ,Type a to add a value\n");
    puts("type d to delete a value and type q to quit\n");
    while ((ch = getchar()) != 'q')
    {
        switch (ch)
        {
        case 'a':
            printf("Integer to add\n");
            scanf("%d", &item);
            if (!QueueIsFull(&line))
            {
                printf("Putting %d into queue\n", item);
                EnQueue(item, &line);
            }
            else
            {
                puts("The queue is full\n");
            }
            break;
        case 'd':
            if (QueueIsEmpty(&line))
            {
                puts("Nothing to delete\n");
            }
            else
            {
                DeQueue(&item, &line);
                printf("Removing %d from queue\n", item);
            }
            break;
        default:
            printf("Please enter %c %c %c\n", 'a', 'd', 'q');
            break;
        }
    }
    EmptyQueue(&line);
    puts("Bye !\n");
}

标题:C Queue Demo
作者:ferried
地址:https://blog.eiyouhe.com/articles/2019/12/22/1577006323470.html