数据结构之双端队列

摘要：有时候一个队列可能需要能从两端进出，这时候称呼它为双端队列。具体思路很简单，从代码可以直接看出来。

#include "stdafx.h"
#include "malloc.h"
#include "stdlib.h"
typedef struct DequeueRecord *queue;
struct DequeueRecord
{
int Capcity;
int size;
int Front ;
int Rear;
int * Array;
};
queue Create(int MaxElements)
{
queue Q;
    Q = (queue)malloc(sizeof(DequeueRecord));
    Q->Capcity = MaxElements;
    Q->Array = (int *)malloc(sizeof(int )*MaxElements);
    Q->size = 0;
    Q->Front = -1;
    Q->Rear = Q->Capcity;
return Q;
}

void Inject(queue Q,int x)//后端入队
{
if (Q->size == Q->Capcity)
    {
puts("error: it is impossible to insert an element inot a full dequeue");
return;
    }
//插入到尾端
    Q->Array[--Q->Rear] = x;
    Q->size++;
}
void Push(queue Q,int x)//前端入队
{
if (Q->size == Q->Capcity)
    {
puts("error: it is impossible to insert an element inot a full dequeue");
return;
    }
//插入前端
Q->Array[++Q->Front] = x;
Q->size++;
} 
int Eject(queue Q)//后端出队
{
if (Q->size == 0 )
    {
puts("it is impossible to delete an element from a empty dequeue");
return (-1);
    }
//删除后端
    Q->Rear = (Q->Capcity + Q->Rear)%Q->Capcity;
    Q->size -- ;
return Q->Array[Q->Rear++];

}
int Pop(queue Q)//前端出队

{
if (Q->size == 0 )
    {
puts("it is impossible to delete an element from a empty dequeue");
return (-1);
    }
//删除前端
    Q->Front = (Q->Capcity + Q->Front)%Q->Capcity;
    Q->size -- ;
return Q->Array[Q->Front--];

}
int _tmain(int argc, _TCHAR* argv[])
{
int i = 0;
queue Q;
    Q = Create(20);
while(i++<5)
        Push(Q,i);
while(i-->1)
       Inject(Q,i);
while(i++ <9)
printf("%d ",Pop(Q));
puts("\n");
       i = 0;
while(i++<3)
printf("%d",Eject(Q));
return 0;
}