【数据结构】队列

【1】定义

队列是限制在两端进行插入操作和删除操作的线性表，允许进行存
入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。
当线性表中没有元素时，称为“空队”。

【2】特点 ##

先进先出（FIFO）。

【3】队列的顺序存储（循环队列）

/* 顺序队 */
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef int datatype_t;

struct sqqueue
{
    datatype_t data[MAX];
    int front,tail;
};

struct sqqueue * sqqueue_create()
{
    struct sqqueue *tmp = (struct sqqueue *)malloc(sizeof(struct sqqueue));
    tmp->front=0;
    tmp->tail=0;
}


int sqqueue_full(struct sqqueue *sq)
{
    return ((sq->tail+1)%MAX==sq->front)?1:0;
}

int sqqueue_empty(struct sqqueue *sq)
{
    return (sq->front==sq->tail)?1:0;
}


void sqqueue_push(struct sqqueue *sq,datatype_t value)
{
    if(sqqueue_full(sq)==1)
    {
        printf("full\n");
        return;
    }
    sq->data[sq->tail]=value;
    sq->tail=(sq->tail+1)%MAX;
}

datatype_t sqqueue_pop(struct sqqueue *sq)
{
    if(sqqueue_empty(sq)==1)
    {
        printf("empty\n");
        return -1;
    }
    datatype_t tmp=sq->data[sq->front];
    sq->front=(sq->front+1)%MAX;
    return tmp;
}


int main()
{
    int i;
    struct sqqueue * sq;
    sq=sqqueue_create();


    for(i=0;i<10;i++)
        sqqueue_push(sq,i);

    while(sqqueue_empty(sq)==0)
    {
        printf("%d ",sqqueue_pop(sq));
    }
    putchar(10);

    return 0;
}

【4】队列的链式存储

/* 链队 */
#include <stdio.h>
#include <stdlib.h>
typedef int datatype_t;

struct node
{
    datatype_t data;
    struct node *next;
};

struct linkqueue
{
    struct node *front;
    struct node *rear;
};

struct linkqueue *linkqueue_create()
{
    struct linkqueue *tmp=(struct linkqueue *)malloc(sizeof(struct linkqueue));
    tmp->front=(struct node *)malloc(sizeof(struct node));
    tmp->front->next=NULL;
    tmp->rear=tmp->front;
    return tmp;
}


int linkqueue_empty(struct linkqueue *lq)
{
    return (lq->front->next==NULL)?1:0;
}

void linkqueue_push(struct linkqueue *lq,datatype_t value)
{
    struct node *tmp=(struct node *)malloc(sizeof(struct node));
    tmp->data=value;
    tmp->next=NULL;
    lq->rear->next=tmp;
    lq->rear=tmp;
}

datatype_t linkqueue_pop(struct linkqueue *lq)
{
    if(linkqueue_empty(lq)==1)
    {
        printf("empty\n");
        return -1;
    }
    struct node *p;
    datatype_t tmp;
    p=lq->front->next;
    tmp=p->data;
    lq->front->next=p->next;
    free(p);
    if(linkqueue_empty(lq)==1)
    {
        lq->rear=lq->front;
    }

    return tmp;
}


int main()
{

    struct linkqueue *lq;
    int i;
    lq=linkqueue_create();
    for(i=0;i<10;i++)
    {
        linkqueue_push(lq,i);
    }

    while(linkqueue_empty(lq)==0)
    {
        printf("%d ",linkqueue_pop(lq));
    }
    putchar(10);
    for(i=0;i<10;i++)
    {
        linkqueue_push(lq,i);
    }
    while(linkqueue_empty(lq)==0)
    {
        printf("%d ",linkqueue_pop(lq));
    }
    putchar(10);

    return 0;
}