C++模拟实现循环顺序队列

C++中也会经常用的线性表链表，对比各自特点，
线性表更适合完成栈的操作，因为线性表实际是数组完成的，数据依次挨着排放，不需要前插把数据依次后移。
而链表更适合队列的操作，而链表为了方便数据的尾插，头删，推出了带头节点的循环队列。一下就是实现代码：

//带头的循环顺序队列
#include<iostream>
using namespace std;
typedef int DataType;
struct ListNode
{
    DataType _data;//该节点数据权重
    ListNode* _next;//指向后一个的节点
    ListNode* _prev;//指向前一个的节点
    //c++中的struct和C中不同，C++中的struct更像一个类，但是所以成员默认public公有，所以可以有函数，当然也有构造系统。
    ListNode(const DataType& data)
        :_next(NULL), _prev(NULL), _data(data)
    {}
};

class MyList 
{
    typedef ListNode Node;
public:
    MyList() 
    {
        _head = new Node(DataType());
        _head->_next = _head;
        _head->_prev = _head;
        //构造一个循环带头的链表头部初始状态
    }
    ~MyList()
    {
        ListNode *next = _head->_next;
        ListNode *cur = _head->_next;
        while (cur != _head) 
        {
            next = cur->_next;
            delete cur;
            cur = next;
        }
        delete _head;
        _head = NULL;
        //清理释放还是要一个节点一个节点的delete释放的。
    }
    MyList(const MyList & ls)
        :_head(new Node(0))
    {
        Node *src = ls._head->_next;//ls源
        Node *dst = _head->_next;//this目标
        Node *proc = _head;
        while (src != ls._head)
        {
            dst = new Node(src->_data);
            proc->_next = dst;
            dst->_prev = proc;
            proc = dst;
            src = src->_next;
        }
        dst->_next = _head;
        //所以头节点是没有经行值拷贝的
    }

     MyList& operator=(const MyList &ls)
    {
         if (ls._head != _head)
         {
             MyList l(ls);
             swap(l._head, _head);
             //赋值运算符重载用的是现代写法，更喜欢现代写法，因为很多事情不用自己处理，是代码的复用哦。
         }
         return *this;
    }
    Node*Find(const DataType &x)
    {
        Node *cur = _head->_next;
        while (cur != _head)
        {
            if (cur->_data == x)
                return cur;
            else cur = cur->_next;
        }
        if (_head->_data == x)
            return _head;
        return NULL;
        //遍历查找节点并返回该地址
    }
    void Insert(Node*pos, const DataType &x)
    {
    //和find连用哦pos就是利用find（值）返回的指针哦
        Node *newnode = new Node(x);
        Node* next = pos->_next;
        newnode->_prev = pos;
        newnode->_next = next;
        next->_prev = newnode;
        pos->_next = newnode;

    }
    void Erase(Node* pos)
    {
        Node *next = pos->_next;
        Node *prev = pos->_prev;
        next->_prev = prev;
        prev->_next = next;
        delete pos;
    }
    void PushBack(const DataType& x)
    {
        //Node *cur = _head;
        //while (cur->_next != _head)
        //{
        //  cur = cur->_next;
        //}
        //cur->_next = new Node(x);
        //cur->_next->_next = _head;
        //cur->_next->_prev = cur;
        //如果循环链表的尾插还有遍历，，，那循环还有啥用
        Node *cur = _head->_prev;
        cur->_next = new Node(x);
        Node *newnode = cur->_next;
        newnode->_next = _head;
        newnode->_prev = cur;
        _head->_prev = newnode;
    }
    void PushFront(const DataType &x)
    {
        Node *newnode = new Node(x);
        newnode->_next = _head->_next;
        newnode->_prev = _head;
        _head->_next->_prev = newnode;
        _head->_next = newnode;
    }
    void PopBack()
    {
        if (_head->_prev == _head)
            return;
        Node *prov = _head->_prev->_prev;
        Node *cur = _head->_prev;
        prov->_next = _head;
        _head->_prev = prov;
        delete cur;
    }
    void PopFront()
    {
        if (_head->_prev == _head)
            return ;
        Node* cur = _head->_next;
        Node* next = cur->_next;
        next->_prev = _head;
        _head->_next = next;
        delete cur;
    }
    size_t Size()
    {
        int count = 0;
        Node *cur = _head->_next;
        while (cur != _head)
        {
            count++;
            cur = cur->_next;
        }
        return count;
    }
    bool Empty()
    {
        if(Size() == 0)
        return 1;
        else
            return 0;
    }
//  void print()
//  {
//      Node *cur = _head;
//      while (cur->_next != _head)
//      {
//          cout << cur->_data;
//          cur = cur->_next;
//      }
//      cout << cur->_data;
//      cout << endl;
//  }
//print自己写完测试用的哦
private:
    Node *_head;
};

C++模拟实现循环顺序队列

浏览过的版块