#include <iostream>
using namespace std;

template <class x> class Stack {
public:
	Stack	(int m);
	~Stack	();
	int		StackIsFull();
	int		StackIsEmpty();
	void	Push(x e);
	void	Pop(x& e);
	void	PrintStack();
	int		top;
private:
	int		maxsize;
	
	x		*p;
};

int i,j,e,m;

template <class x> void pullup(Stack<x>& s){
	int e2;
	s.Pop(e2);
	if (j != m - i - 1){
		j++;
		pullup(s);
	}
	else
		s.Push(e);
	s.Push(e2);
}

int main(){

	Stack<int> s1(10);
	s1.Push(1);
	s1.Push(2);
	s1.Push(3);
	s1.Push(4);
	
	s1.PrintStack();

	m = s1.top + 1;
	for (i = 0; i < m - 1; i++){
		s1.Pop(e);
		j = 1;
		pullup(s1);
	}

	s1.PrintStack();
	return 0;
}


template <class x> Stack<x>::Stack(int m){
	maxsize = m;
	top = -1;
	p = new x[maxsize];
}

template <class x> Stack<x>::~Stack(){
	delete [] p;
}

template <class x> int Stack<x>::StackIsFull(){
	if (top == maxsize - 1)
			return 1;
	return 0;
}

template <class x> int Stack<x>::StackIsEmpty(){
	if (top == -1)
			return 1;
	return 0;
}

template <class x> void Stack<x>::Push(x e){
	if (!StackIsFull()){
		top++;
		p[top] = e;
	}
}

template <class x> void Stack<x>::Pop(x &e){
	if (!StackIsEmpty()){
		e = p[top];
		top--;
	}
}

template <class x> void Stack<x>::PrintStack(){
	x e;
	if (!StackIsEmpty()){
		Pop(e);
		PrintStack();
		cout << e << endl;
		Push(e);
	}
}