C Queue Demo

Published on with 0 views and 0 comments

  

queue.h

 1#ifndef _QUEUE_H_
 2#define _QUEUE_H_
 3#include <stdbool.h>
 4typedef int Item;
 5#define MAXQUEUE 10
 6typedef struct node
 7{
 8    Item item;
 9    struct node *next;
10} Node;
11
12typedef struct queue
13{
14    // 队列首项
15    Node *front;
16    // 队列尾项
17    Node *rear;
18    // 队列长度
19    int items;
20} Queue;
21// 初始化队列
22void InitializeQueue(Queue *pq);
23// 队列是否满了
24bool QueueIsFull(const Queue *pq);
25// 队列是否空了
26bool QueueIsEmpty(const Queue *pq);
27// 队列项数
28int QueueItemCount(const Queue *pq);
29// 入队
30bool EnQueue(Item item, Queue *pq);
31// 出队
32bool DeQueue(Item *pitem, Queue *pq);
33// free memory
34void EmptyQueue(Queue *pq);
35void showAll(Queue *pq);
36#endif

queue.c

  1#include <stdio.h>
  2#include <stdlib.h>
  3#include "queue.h"
  4// 拷贝节点
  5static void CopyToNode(Item item, Node *pn);
  6// 拷贝项
  7static void CopyToItem(Node *pn, Item *pi);
  8// 初始化队列
  9void InitializeQueue(Queue *pq)
 10{
 11    pq->front = pq->rear = NULL;
 12    pq->items = 0;
 13};
 14// 队列是否满了
 15bool QueueIsFull(const Queue *pq)
 16{
 17    return pq->items == MAXQUEUE;
 18};
 19// 队列是否空了
 20bool QueueIsEmpty(const Queue *pq)
 21{
 22    return pq->items == 0;
 23}
 24// 队列项数
 25int QueueItemCount(const Queue *pq)
 26{
 27    return pq->items;
 28}
 29// 入队
 30bool EnQueue(Item item, Queue *pq)
 31{
 32    // 新建一个要插入队的节点
 33    Node *pnew;
 34    // 队列是否满了
 35    if (QueueIsFull(pq))
 36    {
 37        return false;
 38    }
 39    // 为元素分配内存
 40    pnew = (Node *)malloc(sizeof(Node));
 41    // 是否分配好了内存
 42    if (pnew == NULL)
 43    {
 44        return false;
 45    }
 46    // 节点赋值
 47    CopyToNode(item, pnew);
 48    // 下一个节点为null
 49    pnew->next = NULL;
 50    // 查看队列是否为空
 51    if (QueueIsEmpty(pq))
 52    {
 53        // 如果为空的话,pq队列的首项为 pnew
 54        pq->front = pnew;
 55    }
 56    else
 57    {
 58        // 否则插入尾项的下一个位置
 59        pq->rear->next = pnew;
 60    }
 61    // 更新pq队列的尾项
 62    pq->rear = pnew;
 63    // 项 +1
 64    pq->items++;
 65    return true;
 66}
 67// 出队
 68bool DeQueue(Item *pitem, Queue *pq)
 69{
 70    Node *pt;
 71    // 是否为空队列
 72    if (QueueIsEmpty(pq))
 73    {
 74        return false;
 75    }
 76    // pitem指向 队首的item
 77    CopyToItem(pq->front, pitem);
 78    // pt 指向 队首
 79    pt = pq->front;
 80    // 队首为下一个元素
 81    pq->front = pq->front->next;
 82    // 释放内存
 83    free(pt);
 84    // 项数-1
 85    pq->items--;
 86    if (pq->items == 0)
 87    {
 88        pq->rear = NULL;
 89    }
 90    return true;
 91}
 92// free memory
 93void EmptyQueue(Queue *pq)
 94{
 95    Item dummy;
 96    while (!QueueIsEmpty(pq))
 97    {
 98        DeQueue(&dummy, pq);
 99    }
100}
101
102static void CopyToNode(Item item, Node *pn)
103{
104    pn->item = item;
105}
106static void CopyToItem(Node *pn, Item *pi)
107{
108    *pi = pn->item;
109}
110

test

 1#include <stdio.h>
 2#include "queue.h"
 3
 4int main(void)
 5{
 6    Queue line;
 7    Item item;
 8    char ch;
 9    InitializeQueue(&line);
10    puts("Testing the queue interface ,Type a to add a value\n");
11    puts("type d to delete a value and type q to quit\n");
12    while ((ch = getchar()) != 'q')
13    {
14        switch (ch)
15        {
16        case 'a':
17            printf("Integer to add\n");
18            scanf("%d", &item);
19            if (!QueueIsFull(&line))
20            {
21                printf("Putting %d into queue\n", item);
22                EnQueue(item, &line);
23            }
24            else
25            {
26                puts("The queue is full\n");
27            }
28            break;
29        case 'd':
30            if (QueueIsEmpty(&line))
31            {
32                puts("Nothing to delete\n");
33            }
34            else
35            {
36                DeQueue(&item, &line);
37                printf("Removing %d from queue\n", item);
38            }
39            break;
40        default:
41            printf("Please enter %c %c %c\n", 'a', 'd', 'q');
42            break;
43        }
44    }
45    EmptyQueue(&line);
46    puts("Bye !\n");
47}

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