当前位置： 移动技术网 > IT编程>开发语言>C/C++ > c++双向链表构成的队列

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

2018年09月13日  | 移动技术网IT编程  | 我要评论

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网