容器适配器之stack，queue和优先级队列---基于List实现的链栈，链队列，优先级队列
容器适配器之stack，queue和优先级队列---基于List实现的链栈，链队列，优先级队列
大忽悠爱学习
发布于 2021-11-15 10:39:08
发布于 2021-11-15 10:39:08
文章被收录于专栏：c++与qt学习
适配器：
- 以某种既有的容器作为底部结构，定义新的接口，使之成为具有某种特殊用途的容器，这种具有新接口的容器称为适配器。
链栈：
#include"List.hpp"
template<class T>
class Stack
{
private:
List<T> stackL;//链表
public:
stack(){}
~stack() {};
//求数据元素个数
int size()const { return stackL.Size(); }
//判断是否为空
bool Empty()const { return stackL.Empty(); }
//获取栈顶元素的常量型引用
const T& Top()const { return stackL.back(); }
//弹栈---弹出栈顶元素
T Pop()
{
//临时值保存链尾元素
T item = stackL.back();
//删除尾元素
stackL.pop_back();
//返回保存的临时尾元素
return item;
}
//压栈
void push(const T& item)
{
//尾插---链尾就是栈头
stackL.push_back(item);
}
//清空栈
void clear()
{
stackL.clear();
}
};链队列：
#include"List.hpp"
template<class T>
class Queue
{
private:
List<T> queueL;//链表
public:
Queue() {};
~Queue() {};
//获取队列长度
int Size()const
{
return queueL.Size();
}
//判断是否为空
bool Empty()const
{
return queueL.empty();
}
//获取队头元素--只读
const T& Front()const
{
return queueL.front();
}
//入队
void Push(const T& item)
{
queueL.push_back(item);
}
//出队---对头元素出队
T Pop()
{
//临时值保存队头元素
T item = queueL.front();
//队头元素出队
queueL.pop_front();
//返回临时值保存的队头元素
return item;
}
//清空队列
void Clear()
{
queueL.clear();
}
};优先级队列
#include"List.hpp"
template<class T>
class PQueue
{
List<T> queueL;
public:
PQueue() {}
~PQueue(){}
int size()const
{
return queueL.Size();
}
bool Empty()const
{
return queueL.empty();
}
//队头元素
const T& front()const
{
return queueL.front();
}
//入队
void push(const T& item)
{
queueL.push_back(item);
}
T pop();//出队
void clear()
{
queueL.clear();
}
};
template<class T>
T PQueue<T>::pop()
{
//itr用来遍历
//min假设begin初始元素最小
//这里iterator类是嵌套在List容器里面的，因此当我们在外部用到iterator类型的时候，要通过typename告诉编译器这是一个类型
typename List<T>::iterator itr=queueL.Begin(), min = queueL.Begin();
for (; itr != queueL.End(); itr++)
{
if ((*itr) < (*min))
min=itr;
}
T item = *min;
queueL.Erase(min);
return item;
}链表.hpp
- 我们这里把独立的迭代器类和节点类都放入链表类中，方便统一参数T使用
#pragma once
#include<cstdlib>
#include<iostream>
using namespace std;
/***************链表类模板的定义************/
template<class T>
class List//有头链表
{
private:
struct Node
{
T data;
Node* prev, * next;
Node(T d = 0, Node* p = NULL, Node* n = NULL) :data(d), prev(p), next(n) {}
};
Node* head;// 头节点指针
Node* tail;//尾节点指针
int size;//节点个数
//初始化函数
void init()
{
head = new Node;
tail = new Node;
size = 0;
//头和尾都需要创建一个节点，用来维护指针域，而不是数据域
head->next = tail;
tail->prev = head;
}
public:
class const_iterator
{
protected:
Node* current;
T& retrive()const { return current->data; }
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
explicit const_iterator(Node* p) :current(p) {}
friend class List<T>;
public:
//默认迭代器指向内容为空
explicit const_iterator() :current(NULL) {}
//const迭代器解引用得到的值不能进行修改，这里是常迭代器
const T& operator*()const { return retrive(); }
//前置++
const_iterator& operator++()
{
current = current->next;
return *this;
}
//后置++
const_iterator operator++(int)
{
//保留旧值
const_iterator old = *this;
//新值后移
++(*this);
return old;
}
//前置--
const_iterator& operator--()
{
current = current->prev;
return *this;
}
//后置--
const_iterator operator--(int)
{
//保留旧值
const_iterator old = *this;
//新值前移
--(*this);
return old;
}
//==
bool operator==(const const_iterator& rhs)const
{
return current == rhs.current;
}
//!=
bool operator!=(const const_iterator& rhs)const
{
return current != rhs.current;
}
};
class iterator : public const_iterator
{
protected:
//转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
explicit iterator(Node* p) :const_iterator(p) {}
friend class List<T>;
public:
explicit iterator() {};
//用普通迭代器可以修改当前迭代器指向位置的值
T& operator*()
{
return const_iterator::retrive();
}
//常对象调用----前置const不能作为重载条件，后置const可以
const T& operator*()const
{
return const_iterator::operator*();
}
//前++
iterator& operator++()
{
const_iterator::current = const_iterator::current->next;
return *this;
}
// 后置++
iterator operator++(int)
{
//保留旧值
iterator old = (*this);
//新值后移
++(*this);
return old;
}
// 前置--
iterator& operator--()
{
const_iterator::current = const_iterator::current->prev;
return *this;
}
// 后置--
iterator operator--(int)
{
//保留旧值
iterator old = *this;
--(*this);
return old;
}
//*******************************************************************
};
//默认构造函数
List() { init(); }
//复制构造函数
List(const List<T>& l)
{
//先初始化
init();
//再调用赋值运算符重载
operator=(l);
}
//赋值运算符重载
const List& operator=(const List& L);
//迭代器中的转换构造是在begin和end函数里面使用的
//开始迭代器---返回的迭代器已经可以间接操作head->next即第一个有效节点的位置
//注意这里返回的都是临时匿名迭代器对象
iterator Begin() { return iterator(head->next); }
const_iterator Begin()const { return const_iterator(head->next); }
//结束迭代器---返回的迭代器已经可以间接操作tail即最后一个有效节点的后一个位置
iterator End() { return iterator(tail); }
const_iterator End()const { return const_iterator(tail); }
//返回首元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
T& front() { return *Begin(); }
const T& front() const { return *Begin(); }
//返回尾元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
//但注意返回的应该是end迭代器前一个，即最后一个位置的有效元素
//这里迭代器重载了--运算符，因此迭代器--,就等于current指针前移
T& back() { return *(--End()); }
const T& back()const { return *(--End()); }
//头插---begin迭代器指向的是第一个有效位置，因此这里插入到第一个有效元素前
void push_front(const T& item)
{
Insert(Begin(), item);
}
//尾插函数---end迭代器指向最后一个有效元素后面一个位置，因此这里插入end迭代器之前，相当于插入的新元素成为了最后一个有效的元素
void push_back(const T& item)
{
Insert(End(), item);
}
//删除首节点---删除begin迭代器指向的第一个有效节点
void pop_front()
{
Erase(Begin());
}
//删除尾节点--删除end迭代器前面一个节点，因此end迭代器指向最后一个有效元素后面一个位置
void pop_back()
{
Erase(--End());//这里--end相当于current指针前移一位
}
//删除指定位置的函数
iterator Erase(iterator itr);
//插入节点的函数
iterator Insert(iterator itr, const T& item);
//获取节点个数
int Size()const { return size; }
//判空函数
bool empty()const { return size == 0; }
//清空----如果不为空，就一直进行头删操作
void clear() { while (!empty()) { pop_front(); } }
};
//插入节点的函数---插入指定迭代器位置之前
template<class T>
typename List<T>::iterator List<T>::Insert(iterator itr, const T& item)
{
//这里需要用p指向当前迭代器的current指针
Node* p = itr.current;
p->prev->next = new Node(item, p->prev, p);
p->prev = p->prev->next;
size++;
//插入到当前节点之前---返回已经指向当前新插入值位置的迭代器
return iterator(p->prev);
}
//删除指定位置的函数--返回删除当前迭代器的下一个位置
//这里
template<class T>
typename List<T>::iterator List<T>::Erase(iterator itr)
{
//p用来临时保存，方便一会delete
Node* p = itr.current;
iterator re(p->next);//当前迭代器的下一个位置的迭代器
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
size--;
return re;
}
//赋值运算符重载
template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
//清表
clear();
//逐个节点进行复制操作
for (const_iterator itr = L.Begin(); itr != L.End(); ++itr)
{
push_back(*itr);
}
return *this;
}main.cpp
#include <iostream>
using namespace std;
#include"queue.hpp"
#include"stack.hpp"
#include"prequeue.hpp"
void test()
{
Queue<int> q;
Stack<int> s;
for (int i = 0; i < 10; i++)
{
q.Push(i);
s.push(i);
}
cout << "打印q队列中的偶数元素" << endl;
while (!q.Empty())
{
if (q.Front() % 2 == 0)
cout << q.Front()<<" ";
q.Pop();
}
cout << endl;
cout << "打印s栈中的奇数元素" << endl;
while (!s.empty())
{
if (s.Top() % 2 != 0)
cout << s.Top()<<" ";
s.Pop();
}
cout << endl;
cout << "优先队列" << endl;
PQueue<int> p;
p.push(3);
p.push(6);
p.push(1);
p.push(8);
p.push(7);
while (!p.Empty())
{
//优先队列这里出队是按int整型的大小，从最小的开始出队
cout << p.pop() <<" ";
}
cout << endl;
}
int main()
{
test();
return 0;
}
注意：当我们在类外部实现insert函数的时候，typename用来声明iterator是一个类型，这里iterator是定义在List类模板中的一个类
总结:
- 如果类型是依赖于模板参数的限定名，那么在它之前必须加typename(除非是基类列表，或者在类的初始化成员列表中) typename大佬详细解读
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/04/26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
