容器适配器之stack，queue和优先级队列---基于List实现的链栈，链队列，优先级队列

适配器：

• 以某种既有的容器作为底部结构，定义新的接口，使之成为具有某种特殊用途的容器，这种具有新接口的容器称为适配器。

链栈：

#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大佬详细解读