devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

双端队列(Double-ended Queue)_双端queue

作者：Gausst松鼠会 | 2024-04-23 01:24:32

赞

踩

双端queue

双端队列(Double-ended Queue)

注：队列是一种只允许在一端删除而在另一端插入的数据结构。双端队列(Deque)是队列的一种拓展，它可以在队列的两端进行插入和删除。

1. 双端队列(Deque)的概念

1.1 双端队列的定义
  • 双端队列是限定插入和删除操作在表的两端进行的线性表，是一种具有队列和栈的性质的数据结构。
1.2 双端队列的特点
  • 双端队列中的元素可以从两端进队和出队，其限定插入和删除操作在表的两端进行。
  • 双端队列提供了3个存取队头元素的函数：
    (1)读取队头元素的函数：bool getHead(T& x);
    (2)在队头插入新元素的函数：bool EnQueueHead(const T& x);
    (3)删除队头元素的函数：bool DeQueueHead(T& x);
  • 双端队列提供了3个存取队尾元素的函数：
    (1)读取队尾元素的函数：bool getTail(T& x);
    (2)在队尾插入新元素的函数：bool EnQueueTail(const T& x);
    (3)删除队尾元素的函数：bool DeQueueTail(T& x);
  • 注：双端队列是单端队列的延伸，很自然地，可以从单端队列的抽象基类Queue派生出双端队列的抽象基类Deque。

2. 双端队列的抽象类定义——应用了模板类来描述双端队列抽象数据类型

  • 文件：DeQue.h

    
#ifndef DEQUE_H_


#define DEQUE_H_



#include "Queue.h"


template <class T>
class Deque : public Queue<T>
{
public:
    Deque(){}                               //构造函数
    virtual ~Deque(){}                     //析构函数
public:
    virtual bool getHead(T& x)const = 0;        //读取队头元素，并将该元素的值保存至x
    virtual bool getTail(T& x)const = 0;        //读取队尾元素，并将该元素的值保存至x
    virtual bool EnQueue(const T& x) = 0;       //新元素x入队——从队尾入队
    virtual bool EnQueueHead(const T& x) = 0;   //新元素x入队——从队头入队
    virtual bool EnQueueTail(const T& x) = 0;   //新元素x入队——从队尾入队
    virtual bool DeQueue(T& x) = 0;             //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueHead(T& x) = 0;         //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueTail(T& x) = 0;         //队尾元素出队，并将该元素的值保存至x
    virtual bool IsEmpty() const = 0;           //判断队列是否为空
    virtual bool IsFull() const = 0;            //判断队列是否为满
    virtual void MakeEmpty() = 0;               //清空队列的内容
    virtual int getSize() const = 0;            //计算队列中元素个数
};


#endif

    • 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

3. 双端队列的实现——基于一维数组的存储表示

3.1 双端队列的类定义及其操作的实现

  • 文件：SeqDeque.h

    
#ifndef SEQ_DEQUE_H_


#define SEQ_DEQUE_H_



#include "Deque.h"


#include <iostream>


#include <string>


#include <strstream>


using namespace std;

const int defaultSize = 50;

template <class T>
class SeqDeque : public Deque<T>
{
public:
    SeqDeque(int sz = defaultSize);         //构造函数
    virtual ~SeqDeque();                    //析构函数
public:
    virtual bool getHead(T& x)const;        //读取队头元素，并将该元素的值保存至x
    virtual bool getTail(T& x)const;        //读取队尾元素，并将该元素的值保存至x
    virtual bool EnQueue(const T& x);       //新元素x入队——从队尾入队
    virtual bool EnQueueHead(const T& x);   //新元素x入队——从队头入队
    virtual bool EnQueueTail(const T& x);   //新元素x入队——从队尾入队
    virtual bool DeQueue(T& x);             //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueHead(T& x);         //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueTail(T& x);         //队尾元素出队，并将该元素的值保存至x
    virtual bool IsEmpty() const;           //判断队列是否为空
    virtual bool IsFull() const;            //判断队列是否为满
    virtual void MakeEmpty();               //清空队列的内容
    virtual int getSize() const;            //计算队列中元素个数
public:
    template <class T>
    friend ostream& operator<<(ostream& os, const SeqDeque<T>& q);  //输出队列元素的重载操作<<
private:
    T *elements;    //存放队列元素的队列数组
    int front;      //队头指针
    int rear;       //队尾指针
    int maxSize;    //队列最大可容纳元素个数
};

//构造函数
template <class T>
SeqDeque<T>::SeqDeque(int sz)
{
    cout << "$ 执行构造函数" << endl;
    if (sz >= 0)
    {
        maxSize = sz;
        front = rear = 0;
        elements = new T[maxSize];
    }
}

//析构函数
template <class T>
SeqDeque<T>::~SeqDeque()
{
    cout << "$ 执行析构函数" << endl;
    delete[] elements;
    elements = NULL;
}

//读取队头元素，并将该元素的值保存至x
template <class T>
bool SeqDeque<T>::getHead(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = elements[front];
    return true;
}

//读取队尾元素，并将该元素的值保存至x
template <class T>
bool SeqDeque<T>::getTail(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = elements[(rear - 1 + maxSize) % maxSize];
    return true;
}

//新元素x入队——从队尾入队
template <class T>
bool SeqDeque<T>::EnQueue(const T& x)
{
    return EnQueueTail(x);
}

//新元素x入队——从队头入队
template <class T>
bool SeqDeque<T>::EnQueueHead(const T& x)
{
    if (true == IsFull())
    {
        return false;
    }
    front = (front - 1 + maxSize) % maxSize;
    elements[front] = x;
    return true;
}

//新元素x入队——从队尾入队
template <class T>
bool SeqDeque<T>::EnQueueTail(const T& x)
{
    if (true == IsFull())
    {
        return false;
    }
    elements[rear] = x;
    rear = (rear + 1) % maxSize;
    return true;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
bool SeqDeque<T>::DeQueue(T& x)
{
    return DeQueueHead(x);
}

//队头元素出队，并将该元素的值保存至x
template <class T>
bool SeqDeque<T>::DeQueueHead(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = elements[front];
    front = (front + 1) % maxSize;
    return true;
}

//队尾元素出队，并将该元素的值保存至x
template <class T>
bool SeqDeque<T>::DeQueueTail(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }
    rear = (rear - 1 + maxSize) % maxSize;
    x = elements[rear];
    return true;
}

//判断队列是否为空
template <class T>
bool SeqDeque<T>::IsEmpty() const
{
    return (front == rear) ? true : false;
}

//判断队列是否为满
template <class T>
bool SeqDeque<T>::IsFull() const
{
    return ((rear + 1) % maxSize == front) ? true : false;
}

//清空队列的内容
template <class T>
void SeqDeque<T>::MakeEmpty()
{
    delete[] elements;
    front = rear = 0;
    elements = new T[maxSize];
}

//计算队列中元素个数
template <class T>
int SeqDeque<T>::getSize() const
{
    return (rear - front + maxSize) % maxSize;
}

//输出队列元素的重载操作<<
template <class T>
ostream& operator<<(ostream& os, const SeqDeque<T>& q)
{
    for (int i = q.front; i != q.rear; i = (i + 1) % q.maxSize)
    {
        os << "[" << i << "]" << " : " << q.elements[i] << endl;
    }
    return os;
}


#endif /* SEQ_DEQUE_H_ */

    • 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
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
3.2 主函数(main函数)的实现

  • 文件：main.cpp

    
#include "SeqDeque.h"



#define EXIT 0              //退出


#define GETHEAD 1           //读取队头元素，并将该元素的值保存至x


#define GETTAIL 2           //读取队尾元素，并将该元素的值保存至x


#define ENQUEUE 3           //新元素x入队——从队尾入队


#define ENQUEUEHEAD 4       //新元素x入队——从队头入队


#define ENQUEUETAIL 5       //新元素x入队——从队尾入队


#define DEQUEUE  6          //队头元素出队，并将该元素的值保存至x


#define DEQUEUEHEAD  7      //队头元素出队，并将该元素的值保存至x


#define DEQUEUETAIL  8      //队尾元素出队，并将该元素的值保存至x


#define ISEMPTY  9          //判断队列是否为空


#define ISFULL 10           //判断队列是否为满


#define MAKEEMPTY 11        //清空队列的内容


#define GETSIZE 12          //计算队列中元素个数


#define OPERATOR_OSTREAM 13 //输出队列元素的重载操作<<


void print_description()
{
    cout << "------------------------------>双端队列<------------------------------" << endl;
    cout << "功能选项说明：" << endl;
    cout << "#0：  退出" << endl;
    cout << "#1：  读取队头元素，并将该元素的值保存至x" << endl;
    cout << "#2：  读取队尾元素，并将该元素的值保存至x" << endl;
    cout << "#3：  新元素x入队——从队尾入队" << endl;
    cout << "#4：  新元素x入队——从队头入队" << endl;
    cout << "#5：  新元素x入队——从队尾入队" << endl;
    cout << "#6：  队头元素出队，并将该元素的值保存至x" << endl;
    cout << "#7：  队头元素出队，并将该元素的值保存至x" << endl;
    cout << "#8：  队尾元素出队，并将该元素的值保存至x" << endl;
    cout << "#9：  判断队列是否为空" << endl;
    cout << "#10： 判断队列是否为满" << endl;
    cout << "#11： 清空队列的内容" << endl;
    cout << "#12： 计算队列中元素个数" << endl;
    cout << "#13： 输出队列元素的重载操作<<" << endl;
    cout << "--------------------------------------------------------------------" << endl;
}

//判断输入的字符串每个字符是否都是数值0~9
bool IsNumber(const string& s_num)
{
    for (size_t i = 0; i < s_num.size(); i++)
    {
        if ((s_num[i] < '0') || (s_num[i] > '9'))
        {
            return false;
        }
    }
    return true;
}

//类型转换——将string型转为模板类型T
template <class T>
T StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}

//输入数据值
template <class T>
T get_data()
{
    cout << "> 请输入数据值，data = ";
    string s_data;
    cin >> s_data;
    return StrToTtype<T>(s_data);
}

//输入数组的最大长度
template <class T>
int get_maxsize()
{
    cout << "> 请输入数组的最大长度，maxsize = ";
    string s_maxsize;
    cin >> s_maxsize;
    while (false == IsNumber(s_maxsize))
    {
        cout << "* 输入有误，请重新输入：";
        cin >> s_maxsize;
    }
    return atoi(s_maxsize.c_str());
}

//构造双端队列
template <class T>
SeqDeque<T>* construct_seqdeque()
{
    cout << "\n==> 创建双端队列" << endl;
    int n_maxsize = get_maxsize<T>();
    SeqDeque<T> *seqDeque = new SeqDeque<T>(n_maxsize);
    return seqDeque;
}

//析构双端队列
template <class T>
void destory_seqdeque(SeqDeque<T>* seqDeque)
{
    cout << "\n==> 释放双端队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;
    delete seqDeque;
    seqDeque = NULL;
}

//读取队头元素，并将该元素的值保存至x
template <class T>
void gethead(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行读取队头元素并将该元素的值保存至x函数" << endl;
    T data;
    if (false == seqDeque->getHead(data))
    {
        cout << "* 读取队头元素失败" << endl;
        return;
    }
    cout << "* 读取队头元素成功，data = " << data << endl;
}

//读取队尾元素，并将该元素的值保存至x
template <class T>
void gettail(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行读取队尾元素并将该元素的值保存至x函数" << endl;
    T data;
    if (false == seqDeque->getTail(data))
    {
        cout << "* 读取队尾元素失败" << endl;
        return;
    }
    cout << "* 读取队尾元素成功，data = " << data << endl;
}

//新元素x入队——从队尾入队
template <class T>
void enqueue(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行新元素x入队——从队尾入队函数" << endl;
    T data = get_data<T>();
    if (false == seqDeque->EnQueue(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//新元素x入队——从队头入队
template <class T>
void enqueuehead(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行新元素x入队——从队头入队函数" << endl;
    T data = get_data<T>();
    if (false == seqDeque->EnQueueHead(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//新元素x入队——从队尾入队
template <class T>
void enqueuetail(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行新元素x入队——从队尾入队函数" << endl;
    T data = get_data<T>();
    if (false == seqDeque->EnQueueTail(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
void dequeue(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == seqDeque->DeQueue(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
void dequeuehead(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == seqDeque->DeQueueHead(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//队尾元素出队，并将该元素的值保存至x
template <class T>
void dequeuetail(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行队尾元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == seqDeque->DeQueueTail(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//判断队列是否为空
template <class T>
void isempty(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行判断队列是否为空函数，IsEmpty = " << seqDeque->IsEmpty() << endl;
}

//判断队列是否为满
template <class T>
void isfull(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行判断队列是否为满函数，IsFull = " << seqDeque->IsFull() << endl;
}

//清空队列的内容
template <class T>
void makeempty(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行清空队列的内容函数" << endl;
    seqDeque->MakeEmpty();
}

//计算队列中元素个数
template <class T>
void getsize(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行计算队列中元素个数函数，Size = " << seqDeque->getSize() << endl;
}

//输出队列元素的重载操作<<
template <class T>
void operator_ostream(SeqDeque<T>* seqDeque)
{
    cout << "$ 执行输出队列元素的重载操作<<函数" << endl;
    cout << *seqDeque;//或operator<<(cout, *seqDeque);
}

//双端队列操作选择
template <class T>
void select_operation(SeqDeque<T>* seqDeque)
{
    if (NULL == seqDeque)
    {
        cout << "* 没有构造双端队列，请先构造双端队列。" << endl;
        return;
    }

    string s_operation;
    while (s_operation != "0")
    {
        cout << "\n==> 请输入功能选项编号(按\"0\"退出程序)：";
        cin >> s_operation;
        while (false == IsNumber(s_operation))
        {
            cout << "* 输入有误，请重新输入：";
            cin >> s_operation;
        }
        int n_operation = atoi(s_operation.c_str());
        switch (n_operation)
        {
        case EXIT://退出
        {
            cout << "$ 退出程序" << endl;
            break;
        }
        case GETHEAD://读取队头元素，并将该元素的值保存至x
        {
            gethead(seqDeque);
            break;
        }
        case GETTAIL://读取队尾元素，并将该元素的值保存至x
        {
            gettail(seqDeque);
            break;
        }
        case ENQUEUE://新元素x入队——从队尾入队
        {
            enqueue(seqDeque);
            break;
        }
        case ENQUEUEHEAD://新元素x入队——从队头入队
        {
            enqueuehead(seqDeque);
            break;
        }
        case ENQUEUETAIL://新元素x入队——从队尾入队
        {
            enqueuetail(seqDeque);
            break;
        }
        case DEQUEUE://队头元素出队，并将该元素的值保存至x
        {
            dequeue(seqDeque);
            break;
        }
        case DEQUEUEHEAD://队头元素出队，并将该元素的值保存至x
        {
            dequeuehead(seqDeque);
            break;
        }
        case DEQUEUETAIL://队尾元素出队，并将该元素的值保存至x
        {
            dequeuetail(seqDeque);
            break;
        }
        case ISEMPTY://判断队列是否为空
        {
            isempty(seqDeque);
            break;
        }
        case ISFULL://判断队列是否为满
        {
            isfull(seqDeque);
            break;
        }
        case MAKEEMPTY://清空队列的内容
        {
            makeempty(seqDeque);
            break;
        }
        case GETSIZE://计算队列元素个数
        {
            getsize(seqDeque);
            break;
        }
        case OPERATOR_OSTREAM://输出队列元素的重载操作<<
        {
            operator_ostream(seqDeque);
            break;
        }
        default:
        {
            cout << "* 请输入正确的功能选项编号" << endl;
            break;
        }
        }
    }
}

int main(int argc, char* argv[])
{
    print_description();
    SeqDeque<int> *seqDeque = construct_seqdeque<int>();
    select_operation(seqDeque);
    destory_seqdeque(seqDeque);
    system("pause");
    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
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396

4. 双端队列的实现——基于单链表的存储表示

4.1 双端队列的类定义及其操作的实现

  • 文件：LinkedDeque.h

    
#ifndef LINKED_DEQUE_H_


#define LINKED_DEQUE_H_



#include "Deque.h"


#include "LinkNode.h"


#include <iostream>


#include <string>


#include <strstream>


using namespace std;

template <class T>
class LinkedDeque : public Deque<T>
{
public:
    LinkedDeque();              //构造函数
    virtual ~LinkedDeque();     //析构函数
public:
    virtual bool getHead(T& x)const;        //读取队头元素，并将该元素的值保存至x
    virtual bool getTail(T& x)const;        //读取队尾元素，并将该元素的值保存至x
    virtual bool EnQueue(const T& x);       //新元素x入队——从队尾入队
    virtual bool EnQueueHead(const T& x);   //新元素x入队——从队头入队
    virtual bool EnQueueTail(const T& x);   //新元素x入队——从队尾入队
    virtual bool DeQueue(T& x);             //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueHead(T& x);         //队头元素出队，并将该元素的值保存至x
    virtual bool DeQueueTail(T& x);         //队尾元素出队，并将该元素的值保存至x
    virtual bool IsEmpty() const;           //判断队列是否为空
    virtual bool IsFull() const;            //判断队列是否为满
    virtual void MakeEmpty();               //清空队列的内容
    virtual int getSize() const;            //计算队列中元素个数
public:
    template <class T>
    friend ostream& operator<<(ostream& os, const LinkedDeque<T>& q);   //输出队列元素的重载操作<<
private:
    LinkNode<T> *front; //队头指针，即链头指针
    LinkNode<T> *rear;  //队尾指针，即链尾指针
};

//构造函数
template <class T>
LinkedDeque<T>::LinkedDeque()
: front(NULL), rear(NULL)
{
    cout << "$ 执行构造函数" << endl;
}

//析构函数
template <class T>
LinkedDeque<T>::~LinkedDeque()
{
    cout << "$ 执行析构函数" << endl;
    MakeEmpty();
}

//读取队头元素，并将该元素的值保存至x
template <class T>
bool LinkedDeque<T>::getHead(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = front->data;
    return true;
}


//读取队尾元素，并将该元素的值保存至x
template <class T>
bool LinkedDeque<T>::getTail(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = rear->data;
    return true;
}

//新元素x入队——从队尾入队
template <class T>
bool LinkedDeque<T>::EnQueue(const T& x)
{
    return EnQueueTail(x);
}

//新元素x入队——从队头入队
template <class T>
bool LinkedDeque<T>::EnQueueHead(const T& x)
{
    LinkNode<T> *newNode = new LinkNode<T>(x);
    if (NULL == newNode)
    {
        return false;
    }

    if (NULL == front)
    {
        front = newNode;
        rear = newNode;
    }
    else
    {
        newNode->link = front;
        front = newNode;
    }
    return true;
}

//新元素x入队——从队尾入队
template <class T>
bool LinkedDeque<T>::EnQueueTail(const T& x)
{
    LinkNode<T> *newNode = new LinkNode<T>(x);
    if (NULL == newNode)
    {
        return false;
    }

    if (NULL == front)
    {
        front = newNode;
        rear = newNode;
    }
    else
    {
        rear->link = newNode;
        rear = rear->link;
    }
    return true;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
bool LinkedDeque<T>::DeQueue(T& x)
{
    return DeQueueHead(x);
}

//队头元素出队，并将该元素的值保存至x
template <class T>
bool LinkedDeque<T>::DeQueueHead(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }
    LinkNode<T> *curNode = front;
    front = front->link;
    x = curNode->data;
    delete curNode;
    return true;
}

//队尾元素出队，并将该元素的值保存至x
template <class T>
bool LinkedDeque<T>::DeQueueTail(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }

    x = rear->data;
    LinkNode<T> *curNode = front;
    if (curNode == rear)
    {
        delete rear;
        front = NULL;
        rear = NULL;
        return true;
    }
    while (curNode->link != rear)
    {
        curNode = curNode->link;
    }
    delete rear;
    curNode->link = NULL;
    rear = curNode;
    return true;
}

//判断队列是否为空
template <class T>
bool LinkedDeque<T>::IsEmpty() const
{
    return (NULL == front) ? true : false;
}

//判断队列是否为满
template <class T>
bool LinkedDeque<T>::IsFull() const
{
    return false;
}

//清空队列的内容
template <class T>
void LinkedDeque<T>::MakeEmpty()
{
    LinkNode<T> *curNode = NULL;
    while (NULL != front)           //当链表不为空时，删去链表中所有结点
    {
        curNode = front;            //保存被删结点
        front = curNode->link;      //被删结点的下一个结点成为头结点
        delete curNode;             //从链表上摘下被删结点
    }
}

//计算队列中元素个数
template <class T>
int LinkedDeque<T>::getSize() const
{
    int count = 0;
    LinkNode<T> *curNode = front;
    while (NULL != curNode)
    {
        curNode = curNode->link;
        count++;
    }
    return count;
}

//输出队列元素的重载操作<<
template <class T>
ostream& operator<<(ostream& os, const LinkedDeque<T>& q)
{
    int i = 0;
    LinkNode<T> *curNode = q.front;
    while (NULL != curNode)
    {
        os << "[" << i++ << "]" << " : " << curNode->data << endl;
        curNode = curNode->link;
    }
    return os;
}


#endif /* LINKED_DEQUE_H_ */

    • 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
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
4.2 主函数(main函数)的实现

  • 文件：main.cpp

    
#include "LinkedDeque.h"



#define EXIT 0              //退出


#define GETHEAD 1           //读取队头元素，并将该元素的值保存至x


#define GETTAIL 2           //读取队尾元素，并将该元素的值保存至x


#define ENQUEUE 3           //新元素x入队——从队尾入队


#define ENQUEUEHEAD 4       //新元素x入队——从队头入队


#define ENQUEUETAIL 5       //新元素x入队——从队尾入队


#define DEQUEUE  6          //队头元素出队，并将该元素的值保存至x


#define DEQUEUEHEAD  7      //队头元素出队，并将该元素的值保存至x


#define DEQUEUETAIL  8      //队尾元素出队，并将该元素的值保存至x


#define ISEMPTY  9          //判断队列是否为空


#define ISFULL 10           //判断队列是否为满


#define MAKEEMPTY 11        //清空队列的内容


#define GETSIZE 12          //计算队列中元素个数


#define OPERATOR_OSTREAM 13 //输出队列元素的重载操作<<


void print_description()
{
    cout << "------------------------------>双端队列<------------------------------" << endl;
    cout << "功能选项说明：" << endl;
    cout << "#0：  退出" << endl;
    cout << "#1：  读取队头元素，并将该元素的值保存至x" << endl;
    cout << "#2：  读取队尾元素，并将该元素的值保存至x" << endl;
    cout << "#3：  新元素x入队——从队尾入队" << endl;
    cout << "#4：  新元素x入队——从队头入队" << endl;
    cout << "#5：  新元素x入队——从队尾入队" << endl;
    cout << "#6：  队头元素出队，并将该元素的值保存至x" << endl;
    cout << "#7：  队头元素出队，并将该元素的值保存至x" << endl;
    cout << "#8：  队尾元素出队，并将该元素的值保存至x" << endl;
    cout << "#9：  判断队列是否为空" << endl;
    cout << "#10： 判断队列是否为满" << endl;
    cout << "#11： 清空队列的内容" << endl;
    cout << "#12： 计算队列中元素个数" << endl;
    cout << "#13： 输出队列元素的重载操作<<" << endl;
    cout << "--------------------------------------------------------------------" << endl;
}

//判断输入的字符串每个字符是否都是数值0~9
bool IsNumber(const string& s_num)
{
    for (size_t i = 0; i < s_num.size(); i++)
    {
        if ((s_num[i] < '0') || (s_num[i] > '9'))
        {
            return false;
        }
    }
    return true;
}

//类型转换——将string型转为模板类型T
template <class T>
T StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}

//输入数据值
template <class T>
T get_data()
{
    cout << "> 请输入数据值，data = ";
    string s_data;
    cin >> s_data;
    return StrToTtype<T>(s_data);
}

//构造双端队列
template <class T>
LinkedDeque<T>* construct_linkeddeque()
{
    cout << "\n==> 创建双端队列" << endl;
    LinkedDeque<T> *linkedDeque = new LinkedDeque<T>;
    return linkedDeque;
}

//析构双端队列
template <class T>
void destory_linkeddeque(LinkedDeque<T>* linkedDeque)
{
    cout << "\n==> 释放双端队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;
    delete linkedDeque;
    linkedDeque = NULL;
}

//读取队头元素，并将该元素的值保存至x
template <class T>
void gethead(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行读取队头元素并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedDeque->getHead(data))
    {
        cout << "* 读取队头元素失败" << endl;
        return;
    }
    cout << "* 读取队头元素成功，data = " << data << endl;
}

//读取队尾元素，并将该元素的值保存至x
template <class T>
void gettail(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行读取队尾元素并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedDeque->getTail(data))
    {
        cout << "* 读取队尾元素失败" << endl;
        return;
    }
    cout << "* 读取队尾元素成功，data = " << data << endl;
}

//新元素x入队——从队尾入队
template <class T>
void enqueue(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行新元素x入队——从队尾入队函数" << endl;
    T data = get_data<T>();
    if (false == linkedDeque->EnQueue(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//新元素x入队——从队头入队
template <class T>
void enqueuehead(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行新元素x入队——从队头入队函数" << endl;
    T data = get_data<T>();
    if (false == linkedDeque->EnQueueHead(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//新元素x入队——从队尾入队
template <class T>
void enqueuetail(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行新元素x入队——从队尾入队函数" << endl;
    T data = get_data<T>();
    if (false == linkedDeque->EnQueueTail(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
void dequeue(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedDeque->DeQueue(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
void dequeuehead(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedDeque->DeQueueHead(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//队尾元素出队，并将该元素的值保存至x
template <class T>
void dequeuetail(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行队尾元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedDeque->DeQueueTail(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//判断队列是否为空
template <class T>
void isempty(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行判断队列是否为空函数，IsEmpty = " << linkedDeque->IsEmpty() << endl;
}

//判断队列是否为满
template <class T>
void isfull(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行判断队列是否为满函数，IsFull = " << linkedDeque->IsFull() << endl;
}

//清空队列的内容
template <class T>
void makeempty(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行清空队列的内容函数" << endl;
    linkedDeque->MakeEmpty();
}

//计算队列中元素个数
template <class T>
void getsize(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行计算队列中元素个数函数，Size = " << linkedDeque->getSize() << endl;
}

//输出队列元素的重载操作<<
template <class T>
void operator_ostream(LinkedDeque<T>* linkedDeque)
{
    cout << "$ 执行输出队列元素的重载操作<<函数" << endl;
    cout << *linkedDeque;//或operator<<(cout, *linkedDeque);
}

//双端队列操作选择
template <class T>
void select_operation(LinkedDeque<T>* linkedDeque)
{
    if (NULL == linkedDeque)
    {
        cout << "* 没有构造双端队列，请先构造双端队列。" << endl;
        return;
    }

    string s_operation;
    while (s_operation != "0")
    {
        cout << "\n==> 请输入功能选项编号(按\"0\"退出程序)：";
        cin >> s_operation;
        while (false == IsNumber(s_operation))
        {
            cout << "* 输入有误，请重新输入：";
            cin >> s_operation;
        }
        int n_operation = atoi(s_operation.c_str());
        switch (n_operation)
        {
            case EXIT://退出
            {
                cout << "$ 退出程序" << endl;
                break;
            }
            case GETHEAD://读取队头元素，并将该元素的值保存至x
            {
                gethead(linkedDeque);
                break;
            }
            case GETTAIL://读取队尾元素，并将该元素的值保存至x
            {
                gettail(linkedDeque);
                break;
            }
            case ENQUEUE://新元素x入队——从队尾入队
            {
                enqueue(linkedDeque);
                break;
            }
            case ENQUEUEHEAD://新元素x入队——从队头入队
            {
                enqueuehead(linkedDeque);
                break;
            }
            case ENQUEUETAIL://新元素x入队——从队尾入队
            {
                enqueuetail(linkedDeque);
                break;
            }
            case DEQUEUE://队头元素出队，并将该元素的值保存至x
            {
                dequeue(linkedDeque);
                break;
            }
            case DEQUEUEHEAD://队头元素出队，并将该元素的值保存至x
            {
                dequeuehead(linkedDeque);
                break;
            }
            case DEQUEUETAIL://队尾元素出队，并将该元素的值保存至x
            {
                dequeuetail(linkedDeque);
                break;
            }
            case ISEMPTY://判断队列是否为空
            {
                isempty(linkedDeque);
                break;
            }
            case ISFULL://判断队列是否为满
            {
                isfull(linkedDeque);
                break;
            }
            case MAKEEMPTY://清空队列的内容
            {
                makeempty(linkedDeque);
                break;
            }
            case GETSIZE://计算队列元素个数
            {
                getsize(linkedDeque);
                break;
            }
            case OPERATOR_OSTREAM://输出队列元素的重载操作<<
            {
                operator_ostream(linkedDeque);
                break;
            }
            default:
            {
                cout << "* 请输入正确的功能选项编号" << endl;
                break;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    print_description();
    LinkedDeque<int> *linkedDeque = construct_linkeddeque<int>();
    select_operation(linkedDeque);
    destory_linkeddeque(linkedDeque);
    system("pause");
    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
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380

参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第三章
[2] 百度搜索关键字：双端队列

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/471467
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号