#include "pch.h"
#include <iostream>

template <typename T>
class list {
public:
	class node {
	public:
		node*next;
		T key;
		node() {
			next = nullptr;
		}
	};
	int _size;
		node* head;
		node*front;
		list() {
			head = nullptr;
			front = nullptr;
			int _size = 0;
		}

		void push(T key) {
			node*n = new node();
				n->key = key;

			front->next = n;
			front = n;

			if (head == nullptr)
				head = front;

			_size++;
		}

		void rem(int i) {
			int j = 0;
			node*n = head;
			node*p = nullptr;
			while (j < i) {
				p = n;
				n = n->next;
				j++;
			}

			if (p == nullptr) {
				front = n->next;
			}
			else {
				p->next = n->next;
			}
		}

		T operator [](int i) {
			int j = 0;
			node*n = head;
			while (j < i) {
				n = n->next;
				j++;
			}

			return n->key;
		}

		int size() {
			return _size;
		}
};
////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <list>
using namespace std;

template<typename T, typename C>
class Stack {
private:
	C container;
public:
	//Не обязательно их писать, но Кеков сказал, что это больше похоже на структуру паттерна
	virtual void push(T key) = 0;
	virtual T pop() = 0;
	virtual bool empty() = 0;
	virtual T top() = 0;
	virtual int size() = 0;
};

//Специализация стека под лист из STL
template<typename T>
class Stack<T, list<T>> {
private:
	list<T> container; //несущий контейнер
public:
	void push(T key)
	{
		container.push_back(key);
	}
	T pop()
	{
		auto it = container.end();
		advance(it, -1);
		T key = *it;
		container.pop_back();
		return key;
	}
	bool empty()
	{
		return container.size() == 0;
	}
	int size() {
		return container.size();
	}
	T top() {
		auto it = container.end();
		advance(it, -1);
		T key = *it;
		return key;
	}
};

template<typename T, typename C>
class Queue {
private:
	C container;
public:
	virtual void push(T key) = 0;
	virtual T pop() = 0;
	virtual bool empty() = 0;
	virtual T top() = 0;
	virtual int size() = 0;
};


template<typename T>
class Queue<T, list<T>> {
private:
	list<T> container;
public:
	void push(T key) {
		container.push_back(key);
	}
	bool empty() {
		return container.size() == 0;
	}
	int size() {
		return container.size();
	}
	T top() {
		auto it = container.begin();
		T key = *it;
		return key;
	}
	T pop() {
		auto it = container.begin();
		T key = *it;
		container.erase(it);
		return key;
	}
};

template<typename T, typename C>
class PriorityQueue {
private:
	C container;
public:
	virtual void push(T key) = 0;
	virtual T pop() = 0;
	virtual bool empty() = 0;
	virtual T top() = 0;
	virtual int size() = 0;
};

template<typename T>
class PriorityQueue<T, list<T>> {
private:
	list<T> container;
public:
	void push(T key) {
		container.push_back(key);
		container.sort();
	}

	bool empty() {
		return container.size() == 0;
	}
	int size() {
		return container.size();
	}
	T top() {
		auto it = container.begin();
		T key = *it;
		return key;
	}
	T pop() {
		auto it = container.begin();
		T key = *it;
		container.erase(it);
		return key;
	}
};

int main()
{
	list<int> l;
	l.push(1);
	l.push(2);
	l.push(3);
	l.rem(1);
    std::cout << "Hello World!\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.