队列

队列的实现

/*
 * 队列
 * 说明:该例程为线性表实现,创建一个长度为MaxElements的队列;
 * 当头部元素或尾部元素到在线性表的尾部时,下一个元素会返回线性表的头部
 */
# include <stdio.h>
#include <stdlib.h>
#define Error(Str)    FatalError(Str);
#define FatalError(Str)    fprintf(stderr, "%s\n", Str), exit(1)
typedef int ElementType;
struct QueueRecord;
typedef struct QueueRecord *Queue;
struct QueueRecord
{
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};
int IsEmpty(Queue Q);
int IsFull(Queue Q);
void MakeEmpty(Queue Q);
Queue CreateQueue(int MaxElements);
static int Succ(int Value, Queue Q);
void Enqueue(ElementType X, Queue Q);
void Outqueue(Queue Q);
void traverse(Queue Q);
/*
 * 检测队列是否为空
 */
int IsEmpty(Queue Q)
{
    return Q->Size == 0;
}
/*
 * 检测队列是否已满
 */
int IsFull(Queue Q)
{
    return Q->Size == Q->Capacity;
}
/*
 * 构造空队列
 */
void MakeEmpty(Queue Q)
{
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}
/*
 * 创建一个队列
 */
Queue CreateQueue(int MaxElements)
{
    Queue Q;
    
    Q = malloc(sizeof(struct QueueRecord));
    if(Q == NULL)
        FatalError("空间分配失败!!!");
    Q->Array = malloc(sizeof(ElementType) * MaxElements);
    if(Q->Array == NULL)
        FatalError("空间分配失败!!!");
    Q->Capacity = MaxElements;
    MakeEmpty(Q);
    return Q;
}
static int Succ(int Value, Queue Q)
{
    if(++Value == Q->Capacity)
        Value = 0;
    return Value;
}
/*
 * 入队
 */
void Enqueue(ElementType X, Queue Q)
{
    if(IsFull(Q))
    {
        Error("队列已满,无法入队,皮卡!!!");
    }
    else
    {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}
/*
 * 出队
 */
void Outqueue(Queue Q)
{
    if(IsEmpty(Q))
    {
        Error("队列为空,无法执行出队操作,皮卡!!!");
    }
    else
    {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
    }
}
/*
 * 队列遍历
 */
void traverse(Queue Q)
{
    int i,key = 1,j;
    if(0 == Q->Size)
        printf("(＋﹏＋),我的神啊,这个队列竟然是空的\n");
    else
    {
        for(j=0; j<Q->Size; j++)
        {
            i = Q->Front + j;
            if(i >= Q->Capacity)
                i -= Q->Capacity;
            printf("节点%d:%d\n", key,Q->Array[i]);
            key++;
        }
    }
}
void main()
{
    //创建一个长度为10个元素的队列
    Queue queue;
    int MaxElements = 10;//队列的长度
    queue = CreateQueue(MaxElements);
    printf("初始化成功,皮卡！\n操作说明:\n");
    printf("入队:in 12,将12插入到队列,皮卡！\n");
    printf("出队:out,将最早入队的元素出队,皮卡！\n");
    printf("其它:traverse,遍历整个队列,退出:exit,皮卡！\n");
    
    char oper[10];
    ElementType element;
    
    //主循环
    while(1)
    {
        //参数接收
        int par_key=1;
        while(1)
        {
            if(1 == par_key)
                scanf("%s", &oper);
            else if(2 == par_key)
                scanf("%d", &element);
            else
                break;
            char c=getchar();
            if(c=='\n')
                break;
            par_key++;
        }
        if(strcmp(oper , "in") == 0)
        {
            //入队
            Enqueue(element, queue);
            printf("%d入队成功,目前的队列为:\n", element);
            traverse(queue);
        }
        else if(strcmp(oper , "out") == 0)
        {
            //出队
            printf("%d出队成功,目前的队列为:\n", queue->Array[queue->Front]);
            Outqueue(queue);
            traverse(queue);
        }
        else if(strcmp(oper , "traverse") == 0)
        {
            //遍历
            traverse(queue);
        }
        else if(strcmp(oper , "exit") == 0)
        {
            //退出
            break;
        }
    }
}

运行结果

[root@iZ28mhfkaunZ queue]# ./queue                 
初始化成功,皮卡！
操作说明:
入队:in 12,将12插入到队列,皮卡！
出队:out,将最早入队的元素出队,皮卡！
其它:traverse,遍历整个队列,退出:exit,皮卡！
in 12
12入队成功,目前的队列为:
节点1:12
in 187332
187332入队成功,目前的队列为:
节点1:12
节点2:187332
out
12出队成功,目前的队列为:
节点1:187332
out
187332出队成功,目前的队列为:
(＋﹏＋),我的神啊,这个队列竟然是空的
exit

1