PTA之双端队列_双端队列(deque,即double-ended queue的缩写)是一种具有队列和栈性质的数据结构

题目描述

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，请编写例程实现下列操作：

Push(X,D)：将元素X插入到双端队列D的头；
Pop(D)：删除双端队列D的头元素，并返回；
Inject(X,D)：将元素X插入到双端队列D的尾部；
Eject(D)：删除双端队列D的尾部元素，并返回。

//函数接口定义：
bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );
//其中Deque结构定义如下：

typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存储元素的数组   */
    Position Front, Rear;   /* 队列的头、尾指针 */
    int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：Push和Inject应该在正常执行完操作后返回true，或者在出现非正常情况时返回false。当Front和Rear相等时队列为空，Pop和Eject必须返回由裁判程序定义的ERROR。

裁判测试程序样例：

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

#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {
    ElementType *Data;      /* 存储元素的数组   */
    Position Front, Rear;   /* 队列的头、尾指针 */
    int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; 

Deque CreateDeque( int MaxSize )
{   /* 注意：为区分空队列和满队列，需要多开辟一个空间 */
    Deque D = (Deque)malloc(sizeof(struct QNode));
    MaxSize++;
    D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    D->Front = D->Rear = 0;
    D->MaxSize = MaxSize;
    return D;
}

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

Operation GetOp();          /* 裁判实现，细节不表 */
void PrintDeque( Deque D ); /* 裁判实现，细节不表 */

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

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

/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

输入样例：

3
Pop
Inject 1
Pop
Eject
Push 2
Push 3
Eject
Inject 4
Inject 5
Inject 6
Push 7
Pop
End

输出样例：

Deque is Empty!
1 is out
Deque is Empty!
2 is out
Deque is Full!
Deque is Full!
3 is out
Inside Deque: 4 5

双端队列

定义

双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

存取实现

插入

插入操作大致分为以下三种

• 首指针指向队首时：
  ①向队尾插入：将元素插入rear的位置，再将rear向后移一位
  ②向队首插入：采用顺序存储的双端队列是一个循环队列，我们要往队首插入元素的话，就是向front的前一个位置插入元素，如图，此时front的前一个位置是数组的最后一个位置
  
• 首尾指针均指向中间位置时：
  
• 尾指针指向队尾时：
  

删除

删除操作也分为三种：

• 当首指针指向队尾时：
  
• 首尾指针指向中间位置时：
  
• 尾指针指向队首时：
  

分析：当我们了解了双端队列的工作流程之后，还有一步最重要的操作就是判断队列是空是满。
由题目可知，rear指向的位置不存储元素，由上述可知当rear和front指向同一位置时，队列为空；当（rear+1）%maxsize=front时队列满。
又因为该队列是循环的，所以rear指向的下一个位置应该是（rear+1）%maxsize；而front的下一个位置是（front-1+maxsize）%maxsize，同样地，反过来，front的上一个位置是（front+1）%maxsize，而rear上一个位置是（rear-1+maxsize）%maxsize,大家可以动手验证一下。

核心代码

//将元素X插入到双端队列D的头

bool Push( ElementType X, Deque D ){
    if((D->Rear+1)%D->MaxSize==D->Front){
        return false;
    }
    D->Front=(D->Front-1+D->MaxSize)%D->MaxSize;
    D->Data[D->Front]=X;
    return true;
    
}
//删除双端队列D的头元素，并返回

ElementType Pop( Deque D ){
    int temp;
    if(D->Rear==D->Front){
        return ERROR;
    }
    temp=D->Front;
    D->Front=(D->Front+1)%D->MaxSize;
    return D->Data[temp];
}
//将元素X插入到双端队列D的尾部

bool Inject( ElementType X, Deque D ){
    if((D->Rear+1)%D->MaxSize==D->Front){
        return false;
    }
    D->Data[D->Rear]=X;
    D->Rear=(D->Rear+1)%D->MaxSize;
    return true;
}
//删除双端队列D的尾部元素，并返回

ElementType Eject( Deque D ){
    if(D->Rear==D->Front){
        return ERROR;
    }
    D->Rear=(D->Rear-1+D->MaxSize)%D->MaxSize;
    return D->Data[D->Rear];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42