Last Updated on September 13, 2022 by Gokul Kannan
Brief about Stack Data structure:
A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack will be on the top of the stack.
Functions in the stack:-
- push() function that adds an element on the top of the stack.
- pop() function that removes an element from the top of the stack.
The above two functions are part of the standard stack but we are going to design a new type of stack having these two more functions.
- findMiddle() function that will return the middle element of the stack.
- deleteMiddle() function that will delete the middle element.
Method 1:
Before starting the implementation of such type of stack we need to think that an array or linked list will be more efficient.
- If we choose Array then adding or removing an element from the middle of the array will cost more than O(1).
- If we choose a singly linked list then, moving the middle pointer in both directions is not possible.
- So, the best idea is to choose a Doubly Linked List (DLL). So, We can delete the middle element in O(1) time by maintaining a pointer pointing to the middle of DLL, and here, we can easily move the mid-pointer in both directions using previous and next pointers.
Code Implementation:
/* C++ Program to implement a new type of stack
having findMiddle() and
deleteMiddle() functions */
#include <bits/stdc++.h>
using namespace std;
class myStack {
struct Node {
// members of Node of the LinkedList
int num;
Node* next;
Node* prev;
Node(int num) { this->num = num; }
};
// members of the stack
Node* head = NULL;
Node* mid = NULL;
int size = 0;
public:
// push element in the stack
void push(int data){
Node* temp = new Node(data);
if (size == 0) {
head = temp;
mid = temp;
size++;
return;
}
head->next = temp;
temp->prev = head;
// move head pointer to next of head
head = head->next;
if (size % 2 == 1) {
mid = mid->next;
}
size++;
}
//pop element from the stack
int pop()
{
int data=-1;
if (size != 0) {
data=head->num;
if (size == 1) {
head = NULL;
mid = NULL;
}
else {
head = head->prev;
head->next = NULL;
if (size % 2 == 0) {
mid = mid->prev;
}
}
size--;
}
return data;
}
// find middle element of the stack
int findMiddle(){
if (size == 0) {
return -1;
}
// mid pointer points to middle of the linked list
return mid->num;
}
void deleteMiddle()
{
if (size != 0) {
if (size == 1) {
head = NULL;
mid = NULL;
}
else if (size == 2) {
head = head->prev;
mid = mid->prev;
head->next = NULL;
}
else {
mid->next->prev = mid->prev;
mid->prev->next = mid->next;
if (size % 2 == 0) {
mid = mid->prev;
}
else {
mid = mid->next;
}
}
size--;
}
}
};
int main(){
myStack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
s.push(6);
s.push(7);
cout <<"Top of stack : "<< s.pop() << endl;
//one element is popped out of the stack
cout <<"Top of stack : "<< s.pop() << endl;
cout <<"Middle Element of stack: "<< s.findMiddle() << endl;
// middle element of stack deleted
s.deleteMiddle();
cout <<"Current Middle Element : "<< s.findMiddle() << endl;
}
Output
Top of stack : 7
Top of stack : 6
Middle Element of stack: 3
Current Middle Element : 4
Method 2:
Now, we are going to learn a new approach to design a stack with operations on middle element by using a standard stack and a deque.
We will use a standard stack to store half of the elements and the other half of the elements in the deque. By this approach, we will be able to find the middle element very fast
Before every insert operation:-
- Before pushing any element we will first check the size of these two containers i.e standard stack and deque. If the size of both containers is the same then just push this element in the deque.
- If the size is not equal then pop the front element of the deque and push popped element into the stack and this new element is pushed into the back of the deque.
For more clearly see the Dry run below:-
Code Implementation:
#include <bits/stdc++.h>
using namespace std;
class myStack {
stack<int> st;
deque<int> dq;
public:
void add(int element){
dq.push_back(element);
if (dq.size() > st.size() + 1) { // if this condition results true
// pop element from dequeue and push into stack
int temp = dq.front();
dq.pop_front();
st.push(temp);
}
}
void pop(){
int element = dq.back();
dq.pop_back();
if (st.size() > dq.size()) {
int temp = st.top();
st.pop();
dq.push_front(temp);
}
}
int getMiddleElement() {
// front element of the dequeue is the middle element
return dq.front();
}
void deleteMiddleElement(){
dq.pop_front();
if (st.size() > dq.size()) {
// new middle element should come at front of deque
int temp = st.top();
st.pop();
dq.push_front(temp);
}
}
};
int main(){
myStack s;
s.add(8);
s.add(1);
s.add(5);
// printing the middle element
cout << "Middle Element: " << s.getMiddleElement() << endl;
s.add(7);
s.add(2);
// printing the middle element
cout << "Middle Element: " << s.getMiddleElement() << endl;
// delete middle element
s.deleteMiddleElement();
cout << "Middle Element: " << s.getMiddleElement() << endl;
// delete middle element
s.deleteMiddleElement();
cout << "Middle Element: " << s.getMiddleElement() << endl;
// pop element on the top of the stack
s.pop();
}
Output
Middle Element: 1
Middle Element: 5
Middle Element: 7
Middle Element: 1
This article tried to discuss How to Design a Stack with operations on Middle element. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.