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");
}
争渡