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

template<typename T>

class Stack {
	int size;
	int current;
	T* container;

	void copy(T* _container, int _size, int _current) {
		size = _size;
		current = _current;
		container = new T[size];

		for (int i = 0; i<current; i++)
			container[i] = _container[i];
	}

	void erase() {
		delete[] container;
	}

	void resize() {
		T* helper;
		helper = new int[size];

		for (int i = 0; i<current; i++)
			helper[i] = container[i];

		erase();
		copy(helper, 2 * size, current);

		delete[] helper;
	}

public:

	Stack() {
		size = 10;
		current = 0;
		container = new int[size];
	}

	Stack(Stack const &other) {
		copy(other.container, other.size, other.current);
	}

	Stack& operator=(Stack const &other) {
		if (this != &other) {
			erase();
			copy(other.container, other.size, other.current);
		}
		return *this;
	}

	~Stack() {
		erase();
	}

	bool empty() {
		if (current == 0) return true;
		else return false;
	}

	int getsize() {
		return current;
	}

	void push(int item) {
		if (size == current) resize();
		container[current] = item;
		current++;
	}

	void pop() {
		current--;
	}

	int top() {
		return container[current - 1];
	}

	void swap(int i1, int i2) {
		if (i1 >= 0 && i2 >= 0 &&
			i1<current &&i2<current) {

			int helper = container[i1];
			container[i1] = container[i2];
			container[i2] = helper;
		}
	}
};

class Queue {
	int size;
	int current;
	int* container;

	void copy(int* _container, int _size, int _current) {
		size = _size;
		current = _current;
		container = new int[size];

		for (int i = 0; i<current; i++)
			container[i] = _container[i];
	}

	void erase() {
		delete[] container;
	}

	void resize() {
		int* helper;
		helper = new int[size];

		for (int i = 0; i<current; i++)
			helper[i] = container[i];

		erase();
		copy(helper, 2 * size, current);

		delete[] helper;
	}

public:

	Stack() {
		size = 10;
		current = 0;
		container = new int[size];
	}

	Stack(Stack const &other) {
		copy(other.container, other.size, other.current);
	}

	Stack& operator=(Stack const &other) {
		if (this != &other) {
			erase();
			copy(other.container, other.size, other.current);
		}
		return *this;
	}

	~Stack() {
		erase();
	}

	bool empty() {
		if (current == 0) return true;
		else return false;
	}

	int getsize() {
		return current;
	}

	void push(int item) {
		if (size == current) resize();
		container[current] = item;
		current++;
	}

	void pop() {
		for (int i = 0; i<current - 1; i++) {
			container[i] = container[i + 1];
		}
		current--;
	}


	int top() {
		return container[current - 1];
	}

	void swap(int i1, int i2) {
		if (i1 >= 0 && i2 >= 0 &&
			i1<current &&i2<current) {

			int helper = container[i1];
			container[i1] = container[i2];
			container[i2] = helper;
		}
	}
};