气死人的双端队列（Deque）

标题2 Deque (25 分)

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

九九有话说

其实这道题目和我写的另一篇博客差不多：
双端队列的数组实现习题
思路都一样，区别是：这道题目多了一个Create函数需要自己写，一共写五个函数，而且这道题目是链表实现，而另一个是数组实现。其次就是，这道题目是英语。
我的错误主要在：没看到题干里的“With Header”，于是我写出来的代码是没有头结点的，判空条件是Front = = Rear = = NULL。而题干里面有头结点的话，判空条件是Front==Rear。所以我今晚上机实验的时候找了n遍错误测试了n组样例还是没通过才发现没看到“With Header”的时候……
卧槽卧槽卧槽卧槽这他妈卧槽我自杀吧我从我疯了这既罢什么玩意我几把什么玩意眼瞎了还是脑子进水抽筋了还是卧槽卧槽卧槽卧槽他妈的让我疯了吗疯了吧我撞墙死了算了既罢既罢既罢既罢。
于是又改了半小时加了个头结点才AC的。
为什么我会去重新找题干从而发现漏看“With Header”了呢？其实还是和上面说的那个数组的博客有关。数组那个是因为print函数没有给出，所以我把空值给了Front，而裁判员打印的时候需要空值给Rear。
于是我看了一下这道题目的print，发现也没给出，于是我觉得是不是又犯了类似的错误。一看，诶？我没空值，不可能有两种写法啊？会不会需要带个头结点，于是重新看了眼题目，发现了with header……然后……我疯了。
这道题目的头结点一直被Front指向。

关于队列满了： if (!Push(X, D)) printf(“Memory is Full!\n”);

明白人都知道，这个和数组最不同的地方就是这一点——上限问题。
数组实现的话，因为空间是一次性开辟的，总会有一个容量，所以会有满栈现象，需要判满。
而这道题目是链表实现，插入一个元素，开辟一个空间，一般的编程根本不用考虑判满，因为以现在的计算机内存量，可以认为它永远不会满。但是它要求了，当队列满了的时候，需要输出Memory is Full。
这个地方整的我很懵逼——开辟空间失败了，程序可以说就算是崩了，所以需要类似try catch的机制来处理一下这个错误。但是……据我所知，C语言里面没有这种异常处理机制啊！！？
那怎么敲？
于是我……忽视了这个问题（因为实在不知道怎么敲，也感觉他不会有满的情况），于是就一直返回1，return 0 这句话都没写出来，但是，AC了。喵喵喵？
后来理解着，是这个意思：计算机这破玩意，指不定在什么地方什么时候出点啥幺蛾子，所以人类这种愚蠢的生物认为不可能的事情，也需要保证一下，所以有了一个判断。
就是假设给node开一个空间，需要判断一下这个空间是否真的被开辟了：

PtrToNode node;
    node=(PtrToNode)malloc(sizeof(struct Node));
    if(node==NULL)return 0;

就这样，其实对于这个编程题来说没什么意义，但是这是程序员的一种严谨的体现。毕竟，计算机这破玩意随时都可能出一些稀奇古怪莫名其妙脑洞大开的错误。
而他所说的栈满，我觉得是不可能的。就PTA这玩意，能把电脑的内存要完？我还小，不是很了解，只能这么体会。
下面粘两个代码，一个是我之前走的歪路——没带头结点的WA代码；另一个是我改完之后的正路——带了头结点AC的代码。

没带头结点的WA代码

Deque CreateDeque(){
    Deque result=(Deque)malloc(sizeof(struct DequeRecord));
    result->Front=NULL;
    result->Rear=NULL;
    return result;
}
int Push( ElementType X, Deque D ){
    PtrToNode node;
    node=(PtrToNode)malloc(sizeof(struct Node));
        node->Element=X;
        if(D->Front==NULL){
            node->Next=NULL;node->Last=NULL;
            D->Front=node;D->Rear=node;
        }
        else{
            node->Next=D->Front;
            D->Front->Last=node;
            D->Front=node;
            D->Front->Last=NULL;
        }
return 1;
}
ElementType Pop( Deque D ){
    if(D->Front==NULL)return ERROR;
    else{
        if(D->Front==D->Rear){
           ElementType x=D->Front->Element;
           PtrToNode a=D->Rear;
            D->Front=NULL;
            D->Rear=NULL;
            free(a);
            return x;
        }
        else{
            ElementType x=D->Front->Element;
           PtrToNode a=D->Front;
            D->Front=D->Front->Next;
            D->Front->Last=NULL;
            free(a);
return x;
        }
    }
}
int Inject( ElementType X, Deque D ){
PtrToNode node;
    node=(PtrToNode)malloc(sizeof(struct Node));
  node->Element=X;
   if(D->Rear==NULL){
            node->Next=NULL;node->Last=NULL;
            D->Front=node;D->Rear=node;
        }
    else{
        D->Rear->Next=node;
        node->Last=D->Rear;
        D->Rear=node;
        D->Rear->Next=NULL;
    }
return 1;
}
ElementType Eject( Deque D ){
    if(D->Rear==NULL)return ERROR;
    else{
        if(D->Front==D->Rear){
            ElementType x=D->Front->Element;
            PtrToNode a=D->Front;
            D->Front=NULL;
            D->Rear=NULL;
            free(a);
            return x;
        }
        else{
            ElementType x=D->Rear->Element;
           PtrToNode a=D->Rear;
            D->Rear=D->Rear->Last;
            D->Rear->Next=NULL;
            free(a);
            return x;
        }
    }
}

带头结点的AC代码

Deque CreateDeque(){
    PtrToNode Head = malloc(sizeof(struct Node));
    Head->Last =NULL;
    Head->Next = NULL;
    Deque result=malloc(sizeof(struct DequeRecord));
    result->Front =result->Rear = Head;
    return result;
}
int Push(ElementType X, Deque D){
    PtrToNode node= malloc(sizeof(struct Node));
    node->Element = X;
    if (D->Front->Next != NULL) {
        node->Last = D->Front;
        node->Next = D->Front->Next;
        D->Front->Next = node;
        node->Next->Last = node;
    }
    else {
        D->Front->Next = node;
        node->Last = D->Front;
        node->Next = NULL;
        D->Rear = node;
    }
    return 1;
}
ElementType Pop(Deque D) {
    if (D->Front==D->Rear)
    return ERROR;
else {
    PtrToNode XXX = D->Front->Next;
    ElementType xxx=XXX->Element;
    if (D->Front->Next->Next == NULL) {
        D->Front->Next = NULL;
        D->Rear = D->Front;
    }
    else {
        D->Front->Next = XXX->Next;
        XXX->Next->Last = D->Front;
    }
    free(XXX);
    return xxx;
    }
}
int Inject(ElementType X, Deque D) {
    PtrToNode node = malloc(sizeof(struct Node));
    node->Element = X;
    node->Next = NULL;
    node->Last = D->Rear;
    D->Rear->Next = node;
    D->Rear = node;
    return 1;
}
ElementType Eject(Deque D) {
    if (D->Front == D->Rear)
    return ERROR;
    else {
        PtrToNode XXX = D->Rear;
        ElementType xxx=XXX->Element;
        D->Rear = D->Rear->Last;
        D->Rear->Next = NULL;
        XXX->Last = NULL;
        free(XXX);
        return xxx;
    }
}