c++双向链表构成的队列

c++双向链表构成的队列：也可以看成循环队列的。需要仔细，重点是插入与弹出，结合前篇的绘图，总结逻辑是：1先外部元素建立连接，2后内部元素改变连接。

3改变内部元素连接时，留意前驱或后驱是否为空时的特例。
以下是自定义实现：

//circularqueue.h

#ifdef _MSC_VER
#pragma once
#endif // _MSC_VER

#ifndef CIRCULAR_QUEUE_h_H_
#define CIRCULAR_QUEUE_h_H_

#include
#include

/** 此容器保存的数据类型 */
typedef int DataType;

/** 结点类型 */
struct Node
{
    DataType data_;
    Node* next_;
    Node* prev_;
};

class CircularQueue
{
    Node* pFront;       ///< 指向头结点
    Node* pBack;        ///< 指向尾结点
    int maxSize_;       ///< 最大可用容量
    int size_;          ///< 已使用的容量
public:
    /** 构造函数，传入最大容量参数 */
    explicit CircularQueue(int maxSize);
    ~CircularQueue();

    /** 从尾部插入 */
    int push_back(DataType data);

    /** 从头部弹出 */
    int pop_front();

    /** 返回头结点的数据 */
    DataType front();

    /** 已使用的容量 */
    int size();

    /** 空队判断 */
    bool empty();

    /** 满队判断 */
    bool full();
};

#endif // !CIRCULAR_QUEUE_h_H_

//circularqueue.cpp

#include "circularqueue.h"

CircularQueue::CircularQueue(int maxSize)
{
    assert(maxSize > 0);
    pFront=NULL;
    pBack=NULL;
    maxSize_ = maxSize;
    size_ = 0;
}

CircularQueue::~CircularQueue()
{
    Node* tempNode;
    while (pFront !=NULL)
    {
        tempNode = pFront->next_;
        delete pFront;
        pFront = tempNode;
    }
}

int CircularQueue::push_back(DataType data)
{
    assert(!full());

    Node* newNode = new Node;
    newNode->data_ = data;
    if (empty())
    {
        // 构造队列
        newNode->next_ = NULL;
        newNode->prev_ = NULL;
        pBack=pFront = newNode;

    }
    else
    {
        // 队尾插入
        newNode->prev_ = pBack;
        newNode->next_ = pBack->next_;
        pBack->next_ = newNode;
        pBack = newNode;
    }
    size_++;

    return 0;
}

int CircularQueue::pop_front()
{
    assert(!empty());
    Node* tempNode = pFront;

    if (pFront->next_!=NULL)
    {
        pFront->next_->prev_ = pFront->prev_;
    }
    pFront = pFront->next_;
    delete tempNode;
    size_--;

    return 0;
}

DataType CircularQueue::front()
{
    assert(!empty());
    return pFront->data_;
}

int CircularQueue::size()
{
    return size_;
}

bool CircularQueue::empty()
{
    return size_==0;
}

bool CircularQueue::full()
{
    return size_ == maxSize_;
}

//test.cpp

#include
#include"vector.h"

using std::cout;
using std::endl;


int main()
{
    std::cout << "hello" << std::endl;
    CircularQueue queue(3);
    queue.push_back(1);
    queue.push_back(2);
    queue.push_back(3);
    cout << queue.front() << "-" << queue.size() << endl;
    queue.pop_front();
    cout << queue.front() << "-" << queue.size() << endl;
    queue.pop_front();
    cout << queue.front() << "-" << queue.size() << endl;

    queue.pop_front();
    queue.push_back(4);
    queue.push_back(5);
    queue.push_back(6);
    cout << queue.front() << "-" << queue.size() << endl;

    queue.pop_front();
    cout << queue.front() << "-" << queue.size() << endl;
    queue.pop_front();
    cout << queue.front() << "-" << queue.size() << endl;
    queue.pop_front();
    cout << "-" << queue.size() << endl;

    return 0;
}