DS\队列操作集合

～风介～

1.链队列

#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

typedef struct QNode
{
        ElemType data;
        struct QNode *next;
}QNode,*QueuePtr;

typedef struct LinkQueue
{
        QueuePtr front,rear;
}LinkQueue;

void InitQueue(LinkQueue *q)
{
        q->front = q->rear=(QueuePtr)malloc(sizeof(QNode));
        if(!q->front)
        {
                printf("Initialization failed!");
                exit(0);
        }
        q->front->next = NULL;
}

void InsertQueue(LinkQueue *q,ElemType e)
{
        QueuePtr p;
        p = (QueuePtr)malloc(sizeof(QNode));
        if(p==NULL)
        {
                printf("InsetQueue:initialize p failed!");
                exit(0);
        }
        p->data = e;
        p->next = NULL;
        q->rear->next = p;
        q->rear = p;
}

void DeleteQueue(LinkQueue *q,ElemType *e)
{
        QueuePtr p;
        if(q->front == q->rear)
                return;
        p = q->front->next;
        *e = p->data;
        q->front->next = p->next;
        if(q->rear == p)
                q->rear = q->front;
        
        free(p);        
}

void DestroyQueue(LinkQueue *q)
{
        while(q->front)
        {
                q->rear = q->front->next;
                free(q->front);
                q->front = q->rear;
        }
}

int main()
{
        LinkQueue s;
        ElemType c,d,e;
        
        InitQueue(&s);
        
        printf("请输入整数<#结束>:");
        scanf("%c",&c);
        while(c != '#')
        {
                InsertQueue(&s,c);
                scanf("%c",&c);
        }
        
        getchar();
        
        printf("打印队列中的元素：");
        while(s.front != s.rear)
        {
                DeleteQueue(&s,&e);
                printf("%c",e);
        }
        printf("\n");
        
        return 0;
    
    
}

2.循环队列

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 5

typedef char ElemType;
typedef struct CycleQueue
{
        ElemType *base;
        
        int front;
        int rear;
}CycleQueue;

void InitQueue(CycleQueue *q)
{
        q->base = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
        if(!q->base)
        {
                printf("InitQueue:initialize falied!");
                exit(0);
        }
        q->front = q->rear = 0;
}

void InsertQueue(CycleQueue *q,ElemType e)
{
        if((q->rear+1)%MAXSIZE ==  q->front)
                return;
        q->base[q->rear] = e;
        q->rear = (q->rear+1)%MAXSIZE;
}

void DeleteQueue(CycleQueue *q,ElemType *e)
{
        if(q->front == q->rear)
                return;
        *e = q->base[q->front];
        q->front = (q->front+1)%MAXSIZE;
}

int main()
{
        char e;
        CycleQueue s;
        
        InitQueue(&s);
        
    printf("请输入<#结束>:");
        e = getchar();
        while(e != '#')
        {
                InsertQueue(&s,e);
                e = getchar();
        }
        
        printf("打印队列中的元素：");
        while(s.front != s.rear)
        {
                DeleteQueue(&s,&e);
                printf("%c",e);
        }
        printf("\n");
        
        return 0;
}