C数据结构--队列 链表实现

队列(queue）是具有两个特殊属性的链表。第一，新项只能添加到链表的末尾；第二，只能从链表的开头移除项。可以把队列想象成排队买票的人，你从队尾加入队列，买完票后从队首离开。队列是一种"先进先出"(first in first out,FIFO）的数据形式。

/*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);
void EmptyTheQueue(Queue* pq);
bool GetHeadNode(Item* pitem, const Queue* pq);
#endif // _QUEUE_H_

/*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)
    {
        fprintf(stderr, "Unable to allocate memory!\n");
        exit(1);
    }
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
    {
        pq->front = pnew;//项位于队列的首端
    }
    else
    {
        pq->rear->next = pnew;//链接到队列的尾端
    }
    pq->rear = pnew;//记录队列尾端的位置
    pq->items++;//队列项数加1

    return true;
}

bool DeQueue(Item* pitem, Queue* pq)
{
    Node* pt;
    if(QueueIsEmpty(pq))
    {
        return false;
    }
    CopyToItem(pq->front, pitem);
    pt = pq->front;
    pq->front = pq->front->next;
    free(pt);
    pq->items--;
    if(pq->items == 0)
    {
        pq->rear = NULL;
    }
    return true;
}

void EmptyTheQueue(Queue* pq)
{
    Item dummy;
    while(!QueueIsEmpty(pq))
    {
        DeQueue(&dummy, pq);
    }
}

bool GetHeadNode(Item* pitem, const Queue* pq)
{
    if(QueueIsEmpty(pq))
    {
        return false;
    }
    CopyToItem(pq->front, pitem);
    return true;
}

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

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

/*main.c*/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
//测试程序：利用队列添加和删除整数
int main()
{
    Queue line;
    Item temp;
    char ch;

    InitializeQueue(&line);
    puts("Testing the Queue interface. Type a to add a value,");
    puts("type d to delete a value, type q to quit.");
    while((ch = getchar()) != 'q')
    {
        if(ch != 'a' && ch != 'd')
        {
            continue;
        }

        if(ch == 'a')
        {
            printf("Integer to add: ");
            scanf("%d", &temp);

            if(!QueueIsFull(&line))
            {
                printf("Putting %d into queue\n", temp);
                EnQueue(temp, &line);
            }
            else
            {
                puts("Queue is full!");
            }
        }
        else
        {
            if(QueueIsEmpty(&line))
            {
                puts("Nothing to delete");
            }
            else
            {
                DeQueue(&temp, &line);
                printf("Removing %d from queue\n", temp);
            }
        }
        printf("%d items in queue\n", QueueItemCount(&line));
        puts("Type a to add, d to delete, q to quit:");
    }
    EmptyTheQueue(&line);
    puts("Bye!");
    return 0;
}

运行结果:

Testing the Queue interface. Type a to add a value,
type d to delete a value, type q to quit.
a
Integer to add: 10
Putting 10 into queue
1 items in queue
Type a to add, d to delete, q to quit:
a
Integer to add: 20
Putting 20 into queue
2 items in queue
Type a to add, d to delete, q to quit:
a
Integer to add: 30
Putting 30 into queue
3 items in queue
Type a to add, d to delete, q to quit:
d
Removing 10 from queue
2 items in queue
Type a to add, d to delete, q to quit:
d
Removing 20 from queue
1 items in queue
Type a to add, d to delete, q to quit:
d
Removing 30 from queue
0 items in queue
Type a to add, d to delete, q to quit:
d
Nothing to delete
0 items in queue
Type a to add, d to delete, q to quit:
q
Bye!