#include <iostream>
using namespace std;
 
typedef struct node{
	node *prev = nullptr;
	node *next = nullptr;
	int value;
}node;
 
class stack{
	public:
	stack();
 
	stack(int val);
 
	void push(int val);
 
	void pop();
 
	int top();
 
	void traverse();
 
	private:
 
	node* head;
 
	node* tail;
 
};
 
stack::stack(){
 
	this->head = (node*)calloc(1,sizeof(node));
	this->tail = (node*)calloc(1,sizeof(node));
	head->next=tail;
	head->prev=head;
	tail->next=tail;
	tail->prev=head;
 
};
 
 
stack::stack(int val){
 
	this->head = (node*)calloc(1,sizeof(node));
	this->tail = (node*)calloc(1,sizeof(node));
	head->next=tail;
	head->prev=head;
	tail->next=tail;
	tail->prev=head;
 
	node* temp = (node*)calloc(1,sizeof(node));
	temp->value = val;
	head->next = temp;
	temp->prev = head;
	temp->next = tail;
	tail->prev = temp;
};
 
void stack::push(int val){
	node* temp = (node*)calloc(1,sizeof(node));
	temp->value = val;
	temp->prev = head;
	temp->next = head->next;
	head->next->prev = temp;
	head->next = temp;
};
 
void stack::pop(){
	node *temp = head->next;
	temp->prev->next = temp->next;
	temp->next->prev = head;
	temp->next = temp;
	temp->prev = temp;
	free(temp);
}
 
int stack::top(){
	return this->head->next->value;
};
 
void stack::traverse(){
	node *temp = this->head->next;
		if(temp==this->tail){
			printf("no elements.");
			return;
		}
		while(temp!=this->tail){
			printf("%d ",temp->value);
			temp=temp->next;
		}
		printf("\n");
		return;
}
 
 
int main() {
	stack* test = new stack(3);
	stack* test2 = new stack();
	test2->push(1);
	test->push(4);
	test->push(7);
	test->push(9);
	printf("%d\n",test->top());
	test->traverse();
	printf("%d\n",test2->top());
	test2->traverse();
	return 0;
}