05 Jun 2014
数据结构-队列

##队列概念队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

##顺序队列队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

① “下溢”现象 当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

② “真上溢”现象 当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。

③ “假上溢”现象 从顺序存储的队列可以看出，有可能出现这样情况，尾指针指向一维数组最后，但前面有很多元素已经出队，即空出很多位置，这时要插入元素，仍然会发生溢出。例如，在下图中，若队列的最大容量maxsize=4，此时，tail=3，再进队时将发生溢出。我们将这种溢出称为“假溢出”。要克服“假溢出”，可以将整个队列中元素向前移动，直到头指针head为零，或者每次出队时，都将队列中元素前移一个位置。因此，顺序队列的队满判定条件为tail=maxsize-1。但是，在顺序队列中，这些克服假溢出的方法都会引起大量元素的移动，花费大量的时间，所以在实际应用中很少采用，一般采用下面的循环队列形式。

###循环队列 循环队列定义

为了克服顺序队列中假溢出，通常将一维数组queue[0]到q[maxsize-1]看成是一个首尾相接的圆环，即queue[0]与queue[maxsize-1]相接在一起。将这种形式的顺序队列称为循环队列。若tail+1=maxsize,则令tail=0. 这样运算很不方便，可利用数学中的求模运算来实现。入队：tail=(tail+1) mod maxsize;squeue[tail]=x. 出队：head=(head+1) mod maxsize.

循环队列实现

/******** 数组实现的queue *********/
#include <stdlib.h>
#ifndef _Queuearray_h
#define _Queuearray_h
struct QueueRecord ;
typedef void* ElementType ;
typedef struct QueueRecord *Queue ;

int IsEmpty(Queue Q) ;
int IsFull(Queue Q) ;
Queue CreateQueue(int MaxElements) ;
void DisposeQueue(Queue Q) ;
void MakeEmpty(Queue Q) ;
void Enqueue(ElementType X,Queue Q) ;
ElementType Front(Queue Q) ;
void Dequeue(Queue Q) ;
ElementType FrontAndDequeue(Queue Q) ;

#endif


#define MinQueueSize (5)

struct QueueRecord
{
    int Capacity ;
    int Front ;
    int Rear ;
    int size ;
    ElementType *Array ;
} ;

int IsEmpty(Queue Q)
{
    return Q->size==0 ;
}

int IsFull(Queue Q)
{
    return Q->size==Q->Capacity ;   
}

Queue CreateQueue(int MaxElements)
{
    Queue Q ;
    if(MaxElements<MinQueueSize)
    {
        printf("queue size is too small!") ;
        exit(-1) ;
    }
    Q = (Queue)malloc(sizeof(Queue)) ;
    if(Q==NULL)
    {
        printf("out of stack!") ;
        exit(-1) ;
    }
    Q->Array = (ElementType*)malloc(sizeof(ElementType)*MaxElements) ;
    if(Q->Array==NULL)
    {
        printf("out of stack!") ;
        exit(-1) ;
    }
    Q->Capacity = MaxElements ;
    Q->Front = Q->Rear = 0 ;
    Q->size = 0 ;

    return Q ;
}

void MakeEmpty(Queue Q)
{
    Q->size = 0 ;
    Q->Front = Q->Rear = 0 ;
}

void Enqueue(ElementType X,Queue Q)
{
    if(IsFull(Q)){
        printf("queue is full!\n") ;
        exit(-1) ;
    }else{
        Q->size++ ;
		Q->Rear = (Q->Rear+1)%Q->Capacity ;
        Q->Array[Q->Rear] = X ;
    }
}

ElementType Front(Queue Q)
{
    if(IsEmpty(Q)||Q==NULL){
        printf("queue is empty or not init!") ;
        exit(-1) ;
    }
    return Q->Array[Q->Front+1] ;
}

void Dequeue(Queue Q)
{
    if(IsEmpty(Q))
    {
        printf("queue is empty!") ;
        exit(-1) ;
    }else{
        Q->size-- ;
        Q->Front = (Q->Front+1)%Q->Capacity ;   //此处取余是防止Front的值超过容量
    }
}

ElementType FrontAndDequeue(Queue Q)
{
    ElementType result ;
    if(IsEmpty(Q))
    {
        printf("queue is empty!") ;
        exit(-1) ;
    }else{
        Q->size-- ;
        result = Q->Array[Q->Front+1] ;
        Q->Front = (Q->Front+1)%Q->Capacity ;   //此处取余是防止Front的值超过容量
    }
    return result ;
}

测试程序

/*************************************************************************
	> File Name: queue.c
	> Author: huanglei
	> Mail: huanglei2109@gmail.com 
	> Created Time: 2014年06月03日 星期二 21时17分52秒
	> 数组实现的queue
 ************************************************************************/
#include<stdio.h>
#include"queuearray.h"
main()
{
    Queue Q ;
    Q = CreateQueue(10) ;
    if(IsEmpty(Q))
        printf("queue is empty!\n") ;
    if(IsFull(Q))
        printf("queue is full!\n") ;

    int i = 1 ;
    int j = 2 ;
    int k = 3 ;
    Enqueue(&i,Q) ;
    Enqueue(&j,Q) ;
    Enqueue(&k,Q) ;
    if(IsEmpty(Q))
        printf("queue is empty!\n") ;

    printf("the front is %d\n",*(int*)Front(Q)) ;

    //Dequeue(Q) ;

    printf("%d\n",*(int*)FrontAndDequeue(Q)) ;
}

##链式队列链式队列就没什么地方要注意的了，就直接上代码。

/***********用链表实现的队列*************/
#include <stdlib.h>
#ifndef _Queuelist_h
#define _Queuelist_h

struct QueueRecord ;
typedef void *ElementType ;
typedef struct QueueRecord *Queue ;

int IsEmpty(Queue Q) ;
Queue CreateQueue() ;
void MakeEmpty(Queue Q) ;
void Enqueue(ElementType X,Queue Q) ;
ElementType Front(Queue Q) ;
void Dequeue(Queue Q) ;
ElementType FrontAndDequeue(Queue Q) ;

#endif

struct QueueRecord
{
    ElementType elem ;
    QueueRecord *front ;
    QueueRecord *rear ;
    QueueRecord *next ;
};

int IsEmpty(Queue Q)
{
    return Q->front->next == NULL ;
}

/**此处首先初始化头结点，首指针和尾指针都指向头结点,而头结点的下一个元素为空**/
Queue CreateQueue()
{
	Queue Q ;
    Q = (Queue)malloc(sizeof(QueueRecord)) ;
	Q->front = Q->rear = Q ;
    if(Q->front==NULL)
    {
        printf("out of stack!") ;
        exit(-1) ;
    }
    Q->front->next = NULL ;
	return Q ;	
}

void MakeEmpty(Queue Q) 
{
    Queue QTemp,PTemp ;
    Q->rear = Q->front ;
    PTemp = Q->front->next ;
    Q->front->next = NULL ;
    while(PTemp){
        QTemp = PTemp ;
        PTemp = PTemp->next ;
        free(QTemp) ;
    }
}

void Enqueue(ElementType X,Queue Q)
{
    Queue QCurrent = (Queue)malloc(sizeof(struct QueueRecord)) ;
    if(QCurrent==NULL){
        printf("out of stack!") ;
        exit(-1) ;
    }
    QCurrent->elem = X ;
    Q->rear->next = QCurrent ;
    Q->rear = QCurrent ;
    QCurrent->next = NULL ;
}

void Dequeue(Queue Q) 
{
    Queue QTemp = Q->front->next ;
    Q->front->next = QTemp->next ;
    free(QTemp) ;
}

ElementType FrontAndDequeue(Queue Q)
{
    Queue QTemp = Q->front->next ;
    ElementType result = QTemp->elem ;
    Q->front->next = QTemp->next ;
    free(QTemp) ;
    return result ;
}

测试代码

/*************************************************************************
	> File Name: queuelist.c
	> Author: huanglei
	> Mail: huanglei2109@gmail.com 
	> Created Time: 2014年06月05日 星期四 17时29分18秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include"queuelist.h"
main()
{
    Queue Q ;
    Q = CreateQueue() ;
    printf("%d\n",IsEmpty(Q)) ;
    
    int i = 1 ;
    int j = 2 ;
    int k = 3 ;
    Enqueue(&i,Q) ;
    Enqueue(&j,Q) ;
    Enqueue(&k,Q) ;

    printf("%d\n",IsEmpty(Q)) ; 

   // MakeEmpty(Q) ;
    //printf("%d\n",IsEmpty(Q)) ; 
    
    Dequeue(Q) ;

    printf("%d\n",*(int*)FrontAndDequeue(Q)) ;

}

##循环队列和链式队列的区别对于循环队列与链队列的比较，可以从两方面来考虑：

从时间上，其实它们的基本操作都是常数时间，即都为0(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。
对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据，可以有效的利用资源。但是用循环队列有个小麻烦，不好判断数列是为空还是为满；

链队列就不存在上面的问题。“循环队列”最大优点就是节省空间和少分配空间，而链队列多了一点点地址存储开销。

2014-06-05 22:15:55

乐此不疲～

reference: http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/zhanhuoduilie/zhanhuoduilie3.2.2.2.htm

xule

scribble

05 Jun 2014 数据结构-队列

05 Jun 2014
数据结构-队列