雙端隊列Deque基本操作的C語言實作

題目描述：

A "deque" is a data structure consisting of a list of items, on which the following operations are possible:

• Push(X,D): Insert item X on the front end of deque D.
• Pop(D): Remove the front item from deque D and return it.
• Inject(X,D): Insert item X on the rear end of deque D.
• Eject(D): Remove the rear item from deque D and return it. Write routines to support the deque that take O(1) time per operation.

Format of functions:

Deque CreateDeque();

int Push( ElementType X, Deque D );

ElementType Pop( Deque D );

int Inject( ElementType X, Deque D );

ElementType Eject( Deque D );
           

where 

Deque

 is defined as the following:

typedef struct Node *PtrToNode;

struct Node {

    ElementType Element;

    PtrToNode Next, Last;

};

typedef struct DequeRecord *Deque;

struct DequeRecord {

    PtrToNode Front, Rear;

};
           

Here the deque is implemented by a doubly linked list with a header. Front and Rear point to the two ends of the deque respectively. Front always points to the header. The deque is empty when Front and Rear both point to the same dummy header. Note: Push and Inject are supposed to return 1 if the operations can be done successfully, or 0 if fail. If the deque is empty, Pop and Eject must return ERROR which is defined by the judge program.

Sample program of judge:

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

#define ElementType int
#define ERROR 1e5
typedef enum { push, pop, inject, eject, end } Operation;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Element;
    PtrToNode Next, Last;
};
typedef struct DequeRecord *Deque;
struct DequeRecord {
    PtrToNode Front, Rear;
};
Deque CreateDeque();
int Push( ElementType X, Deque D );
ElementType Pop( Deque D );
int Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* details omitted */
void PrintDeque( Deque D ); /* details omitted */

int main()
{
    ElementType X;
    Deque D;
    int done = 0;

    D = CreateDeque();
    while (!done) {
        switch(GetOp()) {
        case push: 
            scanf("%d", &X);
            if (!Push(X, D)) printf("Memory is Full!\n");
            break;
        case pop:
            X = Pop(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            break;
        case inject: 
            scanf("%d", &X);
            if (!Inject(X, D)) printf("Memory is Full!\n");
            break;
        case eject:
            X = Eject(D);
            if ( X==ERROR ) printf("Deque is Empty!\n");
            break;
        case end:
            PrintDeque(D);
            done = 1;
            break;
        }
    }
    return 0;
}

/* Your function will be put here */
           

Sample Input:

Pop
Inject 1
Pop
Eject
Push 1
Push 2
Eject
Inject 3
End
           

Sample Output:

Deque is Empty!
Deque is Empty!
Inside Deque: 2 3
           

PS：

雙端隊列帶有頭結點（不儲存有效資料），尾結點儲存最後一個元素

Push：在頭部添加一個元素

Pop：删除首元結點（第一個有效結點）并傳回其資料

Inject：在尾部插入一個元素

Eject：删除尾部結點并傳回其資料

Answer：

Deque CreateDeque()
{
    Deque D;
    D=(Deque)malloc(sizeof(struct DequeRecord));
    PtrToNode t;
    t = (PtrToNode)malloc(sizeof(struct Node));
    t->Next = NULL;
    t->Last = NULL;
    D->Front = t;
    D->Rear = t;
    return D;
}

int Push( ElementType X, Deque D )
{
    PtrToNode t;
    t = (PtrToNode)malloc(sizeof(struct Node));
    if(!t)  //存儲空間已滿
        return 0;
    t->Element = X;
    if(D->Front == D->Rear) //隊列為空
    {
        D->Front->Next = t;
        t->Last = D->Front;
        t->Next = NULL;
        D->Rear = t;
        return 1;
    }           
    t->Next = D->Front->Next;
    t->Last = D->Front;
    D->Front->Next->Last = t;
    D->Front->Next = t;
    return 1;
}

ElementType Pop( Deque D )
{
    if(D->Front == D->Rear)  //隊列為空
        return ERROR;
    ElementType x = D->Front->Element;
    if(D->Front->Next == D->Rear) //隻有一個元素
    {
        D->Rear = D->Front;
        D->Rear->Next = NULL;
    }
    else //有兩個及兩個以上元素
    {
        PtrToNode t = D->Front->Next;
        t->Next->Last = D->Front;
        D->Front->Next = t->Next;
        free(t);
    }
    return x;
}

int Inject( ElementType X, Deque D )
{
    PtrToNode t = (PtrToNode)malloc(sizeof(struct Node));
    if(!t)  //存儲空間已滿
        return 0;
    t->Element = X;
    if(D->Front == D->Rear)  //隊列為空
    {
        D->Front->Next = t;
        t->Last = D->Front;
        D->Rear = t;
        return 1;
    }
    
    D->Rear->Next = t;
    t->Next = NULL;
    t->Last = D->Rear;
    D->Rear = t;
    return 1;
}

ElementType Eject( Deque D )
{
    if(D->Front == D->Rear)  //隊列為空
        return ERROR;
    PtrToNode r = D->Rear;
    int x = r->Element;
    D->Rear = r->Last;
    D->Rear->Next = NULL;
    free(r);
    return x;  
}