赞
踩
链式队列是基于单链表的存储表示。所以在实现链式队列时使用了和链表一样的结点struct,结点的具体定义放在"Queue.h"的头文件中。链式队列有两个指针front,rear,front为队头指针,指向单链表的第一个结点,rear为队尾指针,指向单链表的最后一个结点,所以出队是删除第一个节点,入队是将新元素的结点插在单链表最后一个结点的后面。结构图如下:
本文链式队列对应的单链表没有设计空的头节点,因为头节点也没太大用处。
注意,当队列只有一个元素时,front == rear,因为该元素既是第一个元素也是最后一个元素。
这部分代码和上一篇循环队列的文章的Queue.h头文件相同,具体如下:
- #pragma once
- const int maxSize = 50; //顺序队列的最大元素个数
-
- template <class T>
- class Queue
- {
- public:
- Queue() {};
- ~Queue() {};
- virtual bool EnQueue(const T& x) = 0; //新元素入队
- virtual bool DeQueue(T& x) = 0; //队头元素出队
- virtual bool getFront(T& x) = 0; //获取队头元素
- virtual bool IsEmpty() const = 0; //判断队列是否为空
- virtual bool IsFull() const = 0; //判断队列是否满。顺序队列需要,链式队列不需要
- virtual int getSize() const = 0; //求队列元素的个数
- };
-
- //用struct定义节点,链式队才用的到
- template <class T>
- struct LinkNode {
- T data; //数据域
- LinkNode<T> * link; //指针域,指向下一个节点
- LinkNode() //仅初始化指针的构造函数
- {
- LinkNode<T> *ptr = nullptr;
- link = ptr;
- }
- LinkNode(const T& item, LinkNode<T> *ptr = nullptr) //初始化数据和指针成员的构造函数
- {
- data = item;
- link = ptr;
- }
- };
该头文件定义和实现了链式队列的类模板及其相关接口的实现,代码如下:
- #include <iostream>
- #include "Queue.h"
- using namespace std;
-
- template <class T>
- class LinkedQueue :public Queue<T>
- {
- public:
- LinkedQueue() :front(nullptr), rear(nullptr) {} //构造函数
- ~LinkedQueue() { makeEmpty(); } //析构函数
- void makeEmpty(); //清空队列
- bool EnQueue(const T& x); //新元素x入队
- bool DeQueue(T& x); //队首元素出队并由x接收
- bool IsEmpty() const { return (front == nullptr) ? true : false; }//队列是否为空
- bool getFront(T& x); //查看队首元素的值并由x接收
- int getSize() const; //求队列元素的个数,这里的const修饰this指针,即该函数运行过程中不允许对队列进行更改
-
- //注意父类中纯虚函数IsFull(),该函数一定要重写,避免LinkedQueue称为虚类而无法实例化对象
- bool IsFull() const { return false; } //链式队列内存是动态的,所以没有“队满”的概念,因此该函数用不到,直接返回false
-
-
- //重载左移位运算符输出队列中的元素,同理为了避免模板声明发生混淆错误,这里用template <class R>来区分LinkedQueue类模板的template <class T>
- template <class R>
- friend ostream & operator<< (ostream &out, LinkedQueue<R> &lq); //全局函数做友元
-
- private:
- LinkNode<T> *front, *rear; //front指向对头节点的指针,rear指向队尾结点的指针
- };
-
- template <class T>
- void LinkedQueue<T>::makeEmpty()
- {
- LinkNode<T> *p;
- while (front != nullptr) //逐个删除队列中的结点
- {
- p = front; //记录front
- front = front->link; //front指向当前被删结点的下一个结点
- delete p; //释放当前节点的内存
- }
- }
-
-
- template <class T>
- bool LinkedQueue<T>::EnQueue(const T& x)
- {//入队的新元素放在队尾
-
- if (front == nullptr) //如果原队列为空
- {
- front = rear = new LinkNode<T>(x);//只有一个元素时,front和rear均指向该结点,因为该节点既是队头又是队尾
- if (front == nullptr)
- return false; //内存分配失败
- }
- else //如果原队列不为空
- {
- //先建立存放新元素的结点,并由队列最后一个节点的link指针指向该节点
- rear->link = new LinkNode<T>(x);
- //检测内存是否分配成功
- if (rear->link == nullptr)
- return false; //内存分配失败
- rear = rear->link; //更新rear使其指向队尾结点
- return true;
- }
- }
-
-
- template <class T>
- bool LinkedQueue<T>::DeQueue(T& x)
- {//如果队列不为空,将队首结点从链式队列中删除,函数返回true,否则返回false
- if (IsEmpty())
- return false;
- LinkNode<T> *p = front; //记录front指针
- x = front->data; //x接收元素数据
- front = front->link; //更新rear
- delete p; //清理队首结点的内存
- return true;
- }
-
-
- template <class T>
- bool LinkedQueue<T>::getFront(T& x)
- {//若队列不为空,返回队后元素的值及true,否则返回false
- if (IsEmpty())
- return false;
- x = front->data; //x接收队首元素的值
- return true;
- }
-
-
- template <class T>
- int LinkedQueue<T>::getSize() const
- {//求队列元素的个数
- LinkNode<T> *p = front; int num = 0;
- while (p != nullptr)
- {
- p = p->link; //遍历每一个结点
- num++; //元素个数加1
- }
- return num;
- }
-
-
- template <class R>
- ostream & operator<<(ostream &out, LinkedQueue<R> &lq)
- {
- out << "链式队列中元素的个数为:" << lq.getSize() << endl;
- LinkNode<R> *p = lq.front; int i = 0;
- while (p != nullptr)
- {
- out << i << " : " << p->data << endl;
- i++;
- p = p->link; //准备输出下一个元素
- }
- return out; //实现链式输出
- }
老规矩,制作简单测试,剩下的小伙伴自行测试,放在“链式队列.cpp”文件中,代码如下:
- #include <iostream>
- #include "LinkedQueue.h"
- //LinkedQueue.h头文件已经有了using namespace std,所以这里就不用再写了
- int main()
- {
- LinkedQueue<int> LQ;
- for (int i = 0; i < 5; i++)
- LQ.EnQueue(i); //入队
- cout << LQ; //输出队列元素
-
- int x;
- LQ.DeQueue(x); //队首元素出队
- LQ.DeQueue(x);
- cout << LQ; //输出队列元素
-
- return 0;
- }
测试结果如下:
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。