数据结构--队列Queue--链式队列、顺序队列

Michael阿明

发布于 2021-02-20 10:26:32

5580

发布于 2021-02-20 10:26:32

文章被收录于专栏：Michael阿明学习之路

队列：先进先出，就如排队一样，先到的，先排上

1.链式队列

1.1 头文件 listQueue.h

/**
 * @description: 链式队列
 * @author: michael ming
 * @date: 2019/4/1 22:47
 * @modified by:
 */

#ifndef QUEUE_LISTQUEUE_H
#define QUEUE_LISTQUEUE_H
template <class T>
struct SNode
{
    T data;
    SNode* pNext;
};

typedef unsigned int UINT;
template <class T>
class ListQueue
{
public:
    ListQueue(void);
    ~ListQueue(void);
    bool enqueue(const T& data);  //入队    从队列的尾部插入数据
    bool dequeue();		//出队   从队列的头部弹出数据
    UINT getlength() const;	//获得队列的长度
    bool empty() const;		//判断队列是否为空
    void erase();		//清空队列
    void print() const;       //打印队列
    SNode<T>* getHead();    //获取队首
    SNode<T>* getTail();    //获取队尾
private:
    SNode<T>* m_pHead;
    SNode<T>* m_pTail;
    UINT m_QueueLen;
};

#include "listQueue.cpp"
#endif //QUEUE_LISTQUEUE_H

1.2 类实现文件 listQueue.cpp

/**
 * @description: 链式队列实现文件
 * @author: michael ming
 * @date: 2019/4/1 22:47
 * @modified by:
 */
//#include "listQueue.h"
#include <iostream>
using namespace std;
template <class T>
ListQueue<T>::ListQueue():m_pHead(NULL),m_pTail(NULL),m_QueueLen(0){}
template <class T>
ListQueue<T>::~ListQueue()
{
    erase();
}
template <class T>
inline void ListQueue<T>::erase()
{
    SNode<T>* temp;
    while(m_pHead != NULL)
    {
        temp = m_pHead->pNext;
        delete m_pHead;
        m_pHead = temp;
    }
    m_pTail = NULL;
    m_QueueLen = 0;
}
template <class T>
bool ListQueue<T>::empty() const
{
    return m_pHead == NULL;
}
template <class T>
UINT ListQueue<T>::getlength() const
{
    return m_QueueLen;
}
template <class T>
bool ListQueue<T>::enqueue(const T &data)
{
    SNode<T>* newNode = new SNode<T>;
    newNode->data = data;
    newNode->pNext = NULL;
    if(m_pTail == NULL)
        m_pHead = m_pTail = newNode;
    else
    {
        m_pTail->pNext = newNode;
        m_pTail = newNode;
    }
    m_QueueLen++;
    return true;
}
template <class T>
bool ListQueue<T>::dequeue()
{
    if(m_pHead != NULL)
    {
        SNode<T>* temp = m_pHead;
        m_pHead = m_pHead->pNext;
        if(m_pHead == NULL)
            m_pTail == NULL;
        delete temp;
        m_QueueLen--;
        return true;
    }
    return false;
}
template <class T>
void ListQueue<T>::print() const
{
    cout << "-------------------------------------------" << endl;
    cout << "List Queue from head to tail as follow: " << endl;
    SNode<T>* temp = m_pHead;   int i = 0;
    while(temp != NULL)
    {
        cout << "No." << ++i << " elem is " << temp->data << endl;
        temp = temp->pNext;
    }
}
template <class T>
SNode<T>* ListQueue<T>::getHead()
{
    return m_pHead;
}
template <class T>
SNode<T>* ListQueue<T>::getTail()
{
    return m_pTail;
}

1.3 测试主函数 listqueue_main.cpp

/**
 * @description:
 * @author: michael ming
 * @date: 2019/4/1 22:49
 * @modified by:
 */
#include "listQueue.h"
#include <iostream>
int main()
{
    ListQueue<int> intqueue;
    int k = 5;
    for(int i = 0; i < k; ++i)
    {
        intqueue.enqueue(i);
    }
    intqueue.print();
    std::cout << "len of queue is " << intqueue.getlength() << std::endl;
    for(int i = 0; i < k-1; ++i)
    {
        intqueue.dequeue();
        std::cout << "after one dequeue: " << std::endl;
        intqueue.print();
    }
    std::cout << "len of queue is " << intqueue.getlength() << std::endl;
    std::cout << "head is " << intqueue.getHead()->data << std::endl;
    std::cout << "tail is " << intqueue.getTail()->data << std::endl;
    return 0;
}

1.4 valgrind测试运行结果

2. 顺序队列

基于数组实现，有容量限制

2.1 头文件 arrqueue.h

/**
 * @description: 顺序队列，内部基于数组
 * @author: michael ming
 * @date: 2019/4/2 21:24
 * @modified by:
 */
#ifndef QUEUE_ARRQUEUE_H
#define QUEUE_ARRQUEUE_H
typedef unsigned int UINT;
template <class T>
class arrQueue
{
public:
    arrQueue(const int capa = 10);
    ~arrQueue(void);
    bool enqueue(const T& data);  //入队    从队列的尾部插入数据
    bool dequeue();		//出队   从队列的头部弹出数据
    UINT getlength() const;	//获得队列的长度
    bool empty() const;		//判断队列是否为空
    bool full() const;      //判断队列是否满
    void erase();		//清空队列
    void print() const;       //打印队列
    const T& getHead() const;    //获取队首
    const T& getTail() const;    //获取队尾
private:
    int m_pHead;
    int m_pTail;
    UINT m_QueueLen;
    UINT m_capacity;
    T* arrQ;
};

#include "arrqueue.cpp"
#endif //QUEUE_ARRQUEUE_H

2.2 类实现文件 arrqueue.cpp

/**
 * @description: 顺序队列实现文件
 * @author: michael ming
 * @date: 2019/4/2 21:26
 * @modified by:
 */
#include <iostream>
using namespace std;
template <class T>
arrQueue<T>::arrQueue(const int capa):m_pHead(0),m_pTail(-1),m_QueueLen(0),m_capacity(capa)
{
    arrQ = new T[m_capacity];
}
template <class T>
arrQueue<T>::~arrQueue()
{
    erase();
    delete [] arrQ;
}
template <class T>
inline void arrQueue<T>::erase()
{
    m_QueueLen = 0;
    m_pHead = 0;
    m_pTail = -1;
}
template <class T>
bool arrQueue<T>::empty() const
{
    return m_QueueLen == 0;
}
template <class T>
bool arrQueue<T>::full() const
{
    return m_QueueLen == m_capacity;
}
template <class T>
bool arrQueue<T>::enqueue(const T &data)
{
    if(full())
        return false;
    else
    {
        if(empty())
        {
            m_pHead = m_pTail = 0;
            arrQ[0] = data;
            m_QueueLen++;
        }
        else if(m_pTail < m_capacity-1)
        {
            arrQ[++m_pTail] = data;
            m_QueueLen++;
        }
        else    //队列没满，但是队尾到达数组末尾了，数据整体移至数组头部
        {
            for(UINT i = 0; i < m_QueueLen; ++i)
            {
                arrQ[i] = arrQ[m_pHead++];
            }
            m_pHead = 0;
            arrQ[m_QueueLen++] = data;
            m_pTail = m_QueueLen - 1;
        }
        return true;
    }
}
template <class T>
bool arrQueue<T>::dequeue()
{
    if(empty())
        return false;
    else
    {
        m_pHead++;
        m_QueueLen--;
        if(m_QueueLen == 0)
        {
            m_pHead = 0;
            m_pTail = -1;
        }
        return true;
    }
}
template <class T>
UINT arrQueue<T>::getlength() const
{
    return m_QueueLen;
}
template <class T>
const T& arrQueue<T>::getHead() const
{
    return arrQ[m_pHead];
}
template <class T>
const T& arrQueue<T>::getTail() const
{
    return arrQ[m_pTail];
}
template <class T>
void arrQueue<T>::print() const
{
    if(empty())
        cout << "empty queue!" << endl;
    cout << "arrQueue from head to tail as follow:" << endl;
    int j = m_pHead;
    for(UINT i = 0; i < m_QueueLen; )
    {
        cout << "No." << ++i << " elem is " << arrQ[j++] << endl;
    }
    cout << "--------------print end----------------" << endl;
}

2.3 测试主程序 arrqueue_main.cpp

/**
 * @description:
 * @author: mingm
 * @date: 2019/4/1 22:44
 * @param:
 * @return:
 */
#include <iostream>
#include "arrqueue.h"
int main()
{
    arrQueue<int> intqueue(7);
    for(UINT i = 0; i < 8; ++i)
    {
        intqueue.enqueue(i);
        intqueue.print();
    }
    for(UINT i = 0; i < 5; ++i)
    {
        intqueue.dequeue();
        intqueue.print();
    }
    intqueue.enqueue(100);
    intqueue.print();
    cout << "the length of queue is " << intqueue.getlength() << endl;
    cout << "head is " << intqueue.getHead() << ", tail is " << intqueue.getTail() << endl;
    return 0;
}