顺序队列与链式队列区别与实现

/*
队列的基本概念：模拟现实生活中的队列，队列中允许插入的一端叫做队尾，
                        允许删除的一端叫做队头
顺序队列：所有操作的时间复杂度是O(1),因为它没有任何循环语句
顺序队列存在的问题：
    假溢出：假溢出是队尾指针超出了顺序队列定义的最大存储空间，但
                实际上队列中还有剩余存储空间
假溢出解决办法：采用顺序循环队列解决
    设队尾指针为rear，队头指针为front，最大存储空间为maxsize,
     采用rear=(rear+1)%maxsize=0实现
另一个问题：
队列队满和队空状态均为rear=front=0
可采用的解决方法：
1.少用一个存储单元：判断条件：front==(rear+1)%maxsize
2.设置一个标志位tag,初始时tag=0；每当入队列成功时，tag=1，出队列时tag=0
队列空的条件：rear=front && tag=0
队列满的条件：rear=front && tag=1
3.设置一个计数器count，初始时count=0，每当入队列时count加1，出队列count减1
这样这个计数器不但具有了tag的功能，还有了计数的功能
队空的判断条件：count=0
队满的判断条件：count==maxsize或者count>0 && rear==front
下面的例子将采用第三中解决方法，简单而且不浪费存储空间
链式队列：时间复杂度除了撤销空间是O(n)以外，其他都是O(1)
*/
顺序队列的实现

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

//构造队列
typedef struct queue{
    int que[MAXSIZE];
    int rear;
    int front;
    int count;
}queue;

//初始化队列
void init(queue *q)
{
    q->rear=0;
    q->front=0;
    q->count=0;
}

//判断非空否
int isEmpty(queue *q)
{
    if (q->count==0) return 0;
    else return 1;
}

//插入数据元素
int insert(queue *q,int x)
{
    if(q->count==MAXSIZE){
        printf("队列已满！\n" );
        return 0;
    }
    q->que[q->rear]=x;//数据元素入队尾
    q->rear=(q->rear+1)%MAXSIZE;//后移队尾指针
    q->count++;//元素个数加一
    return 1;
}

//删除数据元素
int delete(queue *q)
{
    if(q->count==0){
        printf("队列为空!\n");
        return 0;
    }
    q->front=(q->front+1)%MAXSIZE;//队头指示器加一
    q->count--;//计数器减一
    return 1;
}

//取队头元素
int get(queue *q)
{
    if(q->count==0){
        printf("队列为空！\n");
        exit(-1);
    }
    return q->que[q->front];
}


int main()
{
    queue q;
    init(&q);
    int i;
    for (i= 0; i < MAXSIZE; ++i)
    {
        insert(&q,i);
    }

    for (i = 0; q.count>0; ++i)
    {
        printf("%d\n", get(&q));
        delete(&q);
    }

    return 0;
}

链式队列的实现
优点：没有最大容量限制，取数据元素相对方便

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

//链表节点
typedef struct qnode
{
    int data;
    struct qnode *next;
}qnode;

//通常为了方便参数调用，把链式队列的头尾节点指针定义为一个单独的结构体
typedef struct  queue
{
    qnode *front;
    qnode *rear;
}queue;
//初始化
int init(queue *q)
{
    q->front=NULL;
    q->rear=NULL;
}
//判断非空否
int isEmpty(queue *q)
{
    if(q->front==NULL) return 0;
    else
        return 1;
}

//插入数据元素
void insert(queue *q,int x)
{
    qnode *p=(qnode*)malloc(sizeof(qnode));//为新元素分配存储空间
    //给新元素赋值
    p->data=x;
    p->next=NULL;
    //加入队列
    //1.队列非空
    if(q->rear!=NULL) q->rear->next=p;//队尾加入新节点
    q->rear=p;//新节点成为新的队尾元素
    //2.队列为空时新节点成为新的头元素
    if(q->front==NULL) q->front=p;
}
//删除数据元素
int delete(queue *q)
{
    qnode *p;
    if(q->front==NULL){
        printf("队列为空！\n");
        return ;
    }
    //让p指向头元素
    p=q->front;
    //出队列脱链,改变队头指针
    q->front=q->front->next;
    //若删除的节点为最后一个，置队尾指针为空
    if(q->front==NULL) q->rear=NULL;

    free(p);
    return 1;

}

//取队头元素
int get(queue *q)
{
    if(q->front==NULL){
        printf("队列为空！\n");
        return 0;
    }
    return q->front->data;
}

//撤销空间
void destroy(queue *q)
{
    qnode *p,*p1;
    p=q->front;
    while(p!=NULL){
        p1=p;
        p=p->next;
        free(p1);
    }
}
int main()
{
    queue q;
    init(&q);
    int i;
    for (i= 0; i < MAXSIZE; ++i)
    {
        insert(&q,i);
    }

     while(q.front!=NULL)
    {
        printf("%d\n", get(&q));
        delete(&q);
    }

    return 0;
}