fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node{
  5. 	int val;
  6. 	Node *prev, *next;
  7. 	Node(int data) : val(data), prev(NULL), next(NULL) {}
  8. 	Node(int data, Node *p, Node *n) : val(data), prev(p), next(n) {}
  9. };
  10.  
  11. class MidStack{
  12. public:
  13. 	Node *head, *mid;
  14. 	int size;
  15.  
  16. 	MidStack(){
  17. 		head = mid = NULL;
  18. 		size = 0;
  19. 	}
  20.  
  21. 	void push(int data){
  22. 		if(!head){
  23. 			head = mid = new Node(data);
  24. 			++size;
  25. 			return;
  26. 		}
  27.  
  28. 		head = new Node(data, NULL, head);
  29.  
  30. 		head->next->prev = head;
  31.  
  32. 		++size;
  33.  
  34. 		if(size & 1)
  35. 			mid = mid->prev;
  36. 	}
  37.  
  38. 	int pop(){
  39. 		if(!head)
  40. 			return -1;
  41.  
  42. 		int retVal = head->val;
  43.  
  44. 		Node *temp = head;
  45. 		head = head->next;
  46.  
  47. 		if(head)
  48. 			head->prev = NULL;
  49.  
  50. 		if(size & 1)
  51. 			mid = mid->next;
  52.  
  53. 		--size;
  54.  
  55. 		delete temp;
  56.  
  57. 		return retVal;
  58. 	}
  59.  
  60. 	int top(){
  61. 		if(!head)
  62. 			return -1;
  63.  
  64. 		return head->val;
  65. 	}
  66.  
  67. 	int getMid(){
  68. 		if(!mid)
  69. 			return -1;
  70.  
  71. 		return mid->val;
  72. 	}
  73.  
  74. 	int popMid(){
  75. 		if(!mid)
  76. 			return -1;
  77.  
  78. 		int retVal = mid->val;
  79. 		Node *temp = mid;
  80.  
  81. 		if(mid->prev)
  82. 			mid->prev->next = mid->next;
  83.  
  84. 		if(mid->next)
  85. 			mid->next->prev = mid->prev;
  86.  
  87. 		mid = (size & 1) ? mid->next : mid->prev;
  88.  
  89. 		--size;
  90.  
  91. 		if(!size)
  92. 			head = NULL;
  93.  
  94. 		delete temp;
  95.  
  96. 		return retVal;
  97. 	}
  98. };
  99.  
  100. int main() {
  101. 	int opt, val;
  102.  
  103. 	MidStack st;
  104.  
  105. 	cout<<"Operations available on Mid Stack are:\n"
  106. 	"1. Push element\n2. Pop element\n3. Top element\n"
  107. 	"4. Pop mid element\n5. Get mid element\n";
  108. 	cout<<"====================================\n";
  109.  
  110. 	while(true){
  111. 		cin>>opt;
  112.  
  113. 		switch(opt){
  114. 			case 1:
  115. 				cin>>val;
  116. 				cout<<"Enter the value to be pushed: "<<val<<"\n";
  117. 				st.push(val); 
  118. 				break;
  119. 			case 2:
  120. 				val = st.pop();
  121. 				if(val == -1)
  122. 					cout<<"The stack is empty!!\n";
  123. 				else
  124. 					cout<<"The deleted top element is: "<<val<<"\n";
  125. 				break;
  126. 			case 3:
  127. 				val = st.top();
  128. 				if(val == -1)
  129. 					cout<<"The stack is empty!!\n";
  130. 				else
  131. 					cout<<"The top element is: "<<val<<"\n";
  132. 				break;
  133. 			case 4:
  134. 				val = st.popMid();
  135. 				if(val == -1)
  136. 					cout<<"The stack is empty!!\n";
  137. 				else
  138. 					cout<<"The deleted middle element is: "<<val<<"\n";
  139. 				break;
  140. 			case 5:
  141. 				val = st.getMid();
  142. 				if(val == -1)
  143. 					cout<<"The stack is empty!!\n";
  144. 				else
  145. 					cout<<"The middle element is: "<<val<<"\n";
  146. 				break;
  147. 			case 6:
  148. 				exit(0);
  149. 		}
  150. 		cout<<"====================================\n";
  151. 	}
  152.  
  153. 	return 0;
  154. }
Success #stdin #stdout 0s 4332KB
comments (?)
stdin
copy 
1 1
1 2
1 3
5 3
1 4
5
1 5
5 3
2 5
4 5
4 5
4 5
4 5
3
6
stdout
copy 
Operations available on Mid Stack are:
1. Push element
2. Pop element
3. Top element
4. Pop mid element
5. Get mid element
====================================
Enter the value to be pushed: 1
====================================
Enter the value to be pushed: 2
====================================
Enter the value to be pushed: 3
====================================
The middle element is: 2
====================================
The top element is: 3
====================================
Enter the value to be pushed: 4
====================================
The middle element is: 2
====================================
Enter the value to be pushed: 5
====================================
The middle element is: 3
====================================
The top element is: 5
====================================
The deleted top element is: 5
====================================
The middle element is: 2
====================================
The deleted middle element is: 2
====================================
The middle element is: 3
====================================
The deleted middle element is: 3
====================================
The middle element is: 1
====================================
The deleted middle element is: 1
====================================
The middle element is: 4
====================================
The deleted middle element is: 4
====================================
The stack is empty!!
====================================
The stack is empty!!
====================================
https://ideone.com/MjYoLl
Mid stack with getMid, deleteMid in O(1)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!