队列 - 以带头结点的循环链表表示队列(C++)
程序员文章站
2024-03-21 14:14:58
...
问题描述:假设以带头结点的循环链表表示队列,并且是设一个指针指向队尾元素节点(注意:不设头指针),试着编写相应的队列初始化、入队列以及出队列的算法。
完整代码如下:
/* 77.5 - 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针) */
/* 循环队列 - 队列初始化、入队、出队 */
//Y_27学习笔记
#include <iostream>
#include <malloc.h>
using namespace std;
//单链表的节点定义
template <typename T>
class link
{
public:
T data; //用于保存节点元素的内容 - 数据域
link<T>* next; //用于指向后继节点的指针 - 指针域
link(const T info,const link<T>* NextValue = NULL)
{
data = info;
next = (link<T>*)NextValue;
}
link(const link<T>* NextValue)
{
next = (link<T>*)NextValue;
}
link() {}
};
//带头节点的循环链式队列的定义
template <typename T>
class ListQueue
{
private:
link<T>* rear; //指向队尾元素节点的尾指针
public:
ListQueue(); //构造函数
~ListQueue(); //析构函数
bool EnListQueue(const T item); //入队
bool OutListQueue(T &item); //出队
};
//构造函数 - 生成链表的头节点(链表的初始化)
template <typename T>
ListQueue<T>::ListQueue()
{
rear = new link<T>(); //请求系统分配内存,并让rear指向这块内存
if( !rear )
cout << "分配内存失败" << endl;
else
{
rear->next = rear; //头节点独自成环
}
}
//析构函数 - 释放链表空间
template <typename T>
ListQueue<T>::~ListQueue()
{
link<T>* head,*p;
head = rear->next; //带头节点的循环链表的释放
while(head != NULL)
{
p = head;
head = head->next;
delete p;
p = NULL;
}
}
//入队
template <typename T>
bool ListQueue<T>::EnListQueue(const T item)
{
link<T>* p; //p指向新生成的节点
p = new link<T>(item);
if( !p )
return false;
//入队将新节点插入到循环链表中的实现
p->data = item;
p->next = rear->next;
rear->next = p;
rear = p;
return true;
}
//出队
template <typename T>
bool ListQueue<T>::OutListQueue(T &item)
{
link<T>* head, *p;
head = rear->next; //找到头节点
if( head == rear ) //这里rear指向的其实是实际元素中的最后一个元素,而head指向的却是实际元素的前一个位置元素
{
cout << "队列为空,无法出队" << endl;
return false;
}
p = head->next; //指向要出队元素、链表中的元素出队相当于删除该节点
item = p->data; //将要出队的元素值赋值给item
head->next = p->next; //绕过被删除节点,指向被删除节点的下一个节点
delete p; //释放被删除节点的空间
p = NULL; //释放指向被删除节点的指针
return true;
}
int main()
{
ListQueue<int> A; //类模板的实例化
int num,i,item; //num入队元素个数
cout << "请输入要入队的元素个数:";
cin >> num;
//以下为测试代码、读者可自行设计
//入队
for( i = 0; i < num; i++ )
{
cout << "请输入第" << i+1 << "个入队元素: ";
cin >> item;
A.EnListQueue(item);
}
cout << endl;
//出队
cout << "出队" << endl;
for( i = 0; i < num; i++ )
{
cout << "出队的第" << i+1 << "个元素:";
A.OutListQueue(item);
cout << item << endl;
}
return 0;
}
运行结果:
推荐阅读
-
设以带头结点的双向循环链表表示的线性表L=(a1,a2,……,an)。
-
以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素。
-
队列 - 以带头结点的循环链表表示队列(C++)
-
假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(算法)
-
假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点
-
java原子化结点结合非阻塞思想以实现链表式队列的插入(可做无阻塞队列使用)
-
java原子化结点结合非阻塞思想以实现链表式队列的插入(可做无阻塞队列使用)
-
MyDS 带头节点的循环双向链表实现双端队列
-
C++封装顺序表和带头结点的双向循环链表
-
以带头节点的单向循环链表表示队列