c++双向链表构成的队列
程序员文章站
2022-03-23 19:37:14
c++双向链表构成的队列:也可以看成循环队列的。需要仔细,重点是插入与弹出,结合前篇的绘图,总结逻辑是:1先外部元素建立连接,2后内部元素改变连接。
3改变内部元素连接时,留意前驱或后驱是否为空时...
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; }