数据结构与算法分析-队列

数据结构与算法分析-队列（单链表实现）
队列一定是遵循先进先出原则，很简单，队列的表示必须是一个具有标记了首位以及队列大小的结构体（front,rear,size），而队列中的节点和单链表中的节点是一样的都只含有当前节点元素和下一节点的地址。
但是入栈的方向其实是和单链表相反的，这是为了操作方便，假设已经初始化一个队列queue，当节点P入栈的时候只需判断队列是否为空，如果为空则新元素既是front也是rear；如果不是空队列，这仅仅将原来的rear->next指向新节点P，而队列queue的rear也要指向P，front则不变。
队列的出栈类似，如图5节点要出队列，直接将queue的新front设置为原始front->next，判断此时队列的size是否为0了，如果为0，则说明该队列中已经没有节点了，rear当然需要指向NULL；而如果此时队列的size不为0，则rear不会改变。
github代码详见这里点击

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

typedef int elementtype;

typedef struct headnode *queue;
typedef struct node     *position;
struct node {
    elementtype data;
    position    next;
};
struct headnode{
    int         size;
    position    front;
    position    rear;
};   // headnode is only use head mark, next point to follow node , rear point to the end node, size declaration the length of whole queue.

queue init_queue(void);
void delete_queue(queue Q);
int isempty(queue Q);
elementtype dequeue(queue Q);
void enqueue(elementtype data,queue Q);


queue init_queue(void)
{
    queue Q;
    Q = (queue)malloc(sizeof(struct headnode));
    Q->front = NULL;
    Q->rear  = NULL;
    Q->size  = 0;
    return Q;
}
void delete_queue(queue Q)
{
    while(!isempty(Q))
        dequeue(Q);
    free(Q);
}
int isempty(queue Q)
{
    return ((Q->front == NULL)&&(Q->rear == NULL)&&(Q->size == 0));
}
void enqueue(elementtype data,queue Q)
{
    position P;
    P = (position)malloc(sizeof(struct node));
    P->data = data;
    P->next = NULL;

    if(isempty(Q))  //when Q is empty ,the new node(P) is both front node and rear node.
        Q->front = P;
    else
        Q->rear->next = P;//when Q isn't empty ,the new node(P) is rear node, the front node isn't change, but original rear->next will point to P

    Q->rear = P;
    Q->size++;
}
elementtype dequeue(queue Q)
{
    elementtype data;
    position tem;
    if(!isempty(Q))
    {
        tem = Q->front;
        data = Q->front->data;
        Q->size--;
        Q->front = tem->next;
        if(Q->size == 0)
            Q->rear = NULL;
        free(tem);
        return data;
    }
    else
    {

        printf("enqueue : error ! Q is a empty queue !\n");
        return 0 ; 
    }
}



int main(int argc ,char** argv)
{
    queue Q;
    elementtype data;
    int i = 0;
    Q = init_queue();
    printf("queue size is : %d\n\n",Q->size);
    printf("enqueue 10 datas\n");
    for(i=0;i<10;i++)
    {   
        enqueue(i, Q);
    }
    printf("queue size is : %d\n\n",Q->size);
    printf("enqueue 5 datas\n");
    for(i=0;i<5;i++)
    {   
        data = dequeue(Q);
        printf("dequeue data is : %d\n",data);
    }
    printf("enqueue 10 datas\n\n");
    for(i=10;i<20;i++)
    {   
        enqueue(i, Q);
    }
    printf("queue size is : %d\n",Q->size);

    for(i=0;i<15;i++)
    {   
        data = dequeue(Q);
        printf("dequeue data is : %d\n",data);
    }
    printf("queue size is : %d\n",Q->size);
}