欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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