//

// Created by DevilInChina on 2018/9/18.

//

#include "List.cpp"

template <typename T>

class ListQueue{

public:

ListQueue():Data(){

Size = 0;

}

void push(const T&a){

++Size;

Data.push_back(a);

}

bool pop(){

if(Size){

--Size;

Data.pop_front();

return true;

}

return false;

}

bool empty(){

return !Size;

}

T&front(){

return Data.front();

}

unsigned int size(){ return Size;}

private:

unsigned int Size;

List<T>Data;

};

template <typename T>

class ListDoubleQueue{

public:

ListDoubleQueue():Data(){Size = 0;}

void show(std::function<void(const T&a)> Fun

=[](const T&a)->void{std::cout<<a<<" ";}){

Data.show(Fun);

}

void push_back(const T&a){

++this->Size;

this->Data.push_back(a);

}

void push_front(const T&a){

++this->Size;

this->Data.push_front(a);

}

bool pop_back(){

if(this->Size){

--this->Size;

this->Data.pop_back();

return true;

}

return false;

}

bool pop_front(){

if(this->Size){

--this->Size;

this->Data.pop_front();

return true;

}

return false;

}

T&back(){

return this->Data.back();

}

bool empty(){

return !Size;

}

T&front(){

return this->Data.front();

}

unsigned int size(){

return this->Size;

}

private:

unsigned int Size;

List<T>Data;

};

#define BEGIN_SIZE 44971

template <typename T>

class Stack {

public:

explicit Stack(unsigned int k = BEGIN_SIZE) : MaxSize(k ? k : 1) {

data = new T[MaxSize];

Top = 0;

}

void pop() {

--Top;

}

void push(const T &ele) {

data[Top++] = ele;

}

bool Pop_safe() {

if (Top) {

--Top;

return true;

}

return false;

}

bool Push_safe(const T &ele) {

if (Top + 1 < MaxSize) {

data[Top++] = ele;

return true;

}

return false;

}

bool empty() {

return !Top;

}

unsigned int size() {

return Top;

}

T &top() {

return data[Top - 1];

}

void reverse() {

auto tmp(new T[Top + 1]);

unsigned int mak = 0;

while (!empty()) {

tmp[mak++] = top();

pop();

}

for (unsigned int i = 0; i < mak; ++i) {

push(tmp[i]);

}

delete[]tmp;

}

~Stack() {

delete[]data;

}

private:

__Index MaxSize;

__Index Top;

T *data;

};

template <typename T>

class Queue{

public:

explicit Queue(unsigned int k = BEGIN_SIZE) : maxs(k ? k : 1) {

data = new T[maxs];

Back = Front = 0;

}

bool empty(){

return Back==Front;

}

bool push(const T&element){

__Index __next = (Back+1)%maxs;

if(__next!=Front){

data[Back] = element;

Back = __next;

return true;

}

else return false;

}

const T&front()const{

return data[Front];

}

T&front(){

return data[Front];

}

bool pop(){

if(empty()){

return false;

}

else {

++Front;

Front%=maxs;

}

}

__Index size(){

if(Front <= Back){

return Back-Front;

} else {

return maxs-Front+Back;

}

}

private:

__Index maxs;

__Index Back;

__Index Front;

T *data;

};

template <typename T>

class ListStack{

public:

ListStack():Data(){

Size = 0;

}

void push(const T&a){

++Size;

Data.push_back(a);

}

bool pop(){

if(Size){

--Size;

Data.pop_back();

return true;

}

return false;

}

T&top(){

return Data.back();

}

bool empty(){

return Size==0;

}

unsigned int size(){ return Size;}

private:

unsigned int Size;

List<T>Data;

};

/**

std::string Trans(unsigned long long Number,int System){///10进制转N进制

Stack<char>res(100);///

std::string ret;

if(System < 2 or System > 62)///超出表达范围

return ret;

std::function<char(unsigned long long )>fun = [](unsigned long long a)->char{

if(a<10)return char(a+'0');

else if(a<26)return char(a-10+'a');

else return char(a-37+'A');

};

while (Number){

res.push(fun(Number%System));

Number/=System;

}

while (!res.empty()){

ret.push_back(res.top());

res.pop();

}

return ret;

}

*/