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;
}