How to implement a stack which will support the following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
Push and pop are standard stack operations.
Method 1:
The important question is, whether to use a linked list or array for the implementation of the stack?
Please note that we need to find and delete the middle element. Deleting an element from the middle is not O(1) for the array. Also, we may need to move the middle pointer up when we push an element and move down when we pop(). In a singly linked list, moving the middle pointer in both directions is not possible.
The idea is to use a Doubly Linked List (DLL). We can delete the middle element in O(1) time by maintaining mid pointer. We can move the mid pointer in both directions using previous and next pointers.
Following is implementation of push(), pop() and findMiddle() operations. If there are even elements in stack, findMiddle() returns the second middle element. For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 3.
C++
/* C++ Program to implement a stackthat supports findMiddle() anddeleteMiddle in O(1) time */#include <bits/stdc++.h>using namespace std;class myStack { struct Node { int num; Node* next; Node* prev; Node(int num) { this->num = num; } }; // Members of stack Node* head = NULL; Node* mid = NULL; int size = 0;public: void push(int data) { Node* temp = new Node(data); if (size == 0) { head = temp; mid = temp; size++; return; } head->next = temp; temp->prev = head; // update the pointers head = head->next; if (size % 2 == 1) { mid = mid->next; } size++; } int pop() { int data=-1; if (size != 0) { Node* toPop = head; data = toPop->num; if (size == 1) { head = NULL; mid = NULL; } else { head = head->prev; head->next = NULL; if (size % 2 == 0) { mid = mid->prev; } } delete toPop; size--; } return data; } int findMiddle() { if (size == 0) { return -1; } return mid->num; } void deleteMiddle() { if (size != 0) { Node* toDelete = mid; 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; } } delete toDelete; size--; } }};int main(){ myStack st; st.push(11); st.push(22); st.push(33); st.push(44); st.push(55); st.push(66); st.push(77); st.push(88); st.push(99); cout <<"Popped : "<< st.pop() << endl; cout <<"Popped : "<< st.pop() << endl; cout <<"Middle Element : "<< st.findMiddle() << endl; st.deleteMiddle(); cout <<"New Middle Element : "<< st.findMiddle() << endl; return 0;}// This code is contributed by Nikhil Goswami// Updated by Amsavarthan LV |
Java
/* Java Program to implement a stack that supportsfindMiddle() and deleteMiddle in O(1) time *//* A Doubly Linked List Node */class DLLNode { DLLNode prev; int data; DLLNode next; DLLNode(int data) { this.data = data; }}/* Representation of the stack data structure that supports findMiddle() in O(1) time. The Stack is implemented using Doubly Linked List. It maintains pointer to head node, pointer to middle node and count of nodes */public class myStack { DLLNode head; DLLNode mid; DLLNode prev; DLLNode next; int size; /* Function to push an element to the stack */ void push(int new_data) { /* allocate DLLNode and put in data */ DLLNode new_node = new DLLNode(new_data); // if stack is empty if (size == 0) { head = new_node; mid = new_node; size++; return; } head.next = new_node; new_node.prev = head; head = head.next; if (size % 2 != 0) { mid = mid.next; } size++; } /* Function to pop an element from stack */ int pop() { int data = -1; /* Stack underflow */ if (size == 0) { System.out.println("Stack is empty"); // return -1; } if (size != 0) { data = head.data; if (size == 1) { head = null; mid = null; } else { head = head.prev; head.next = null; if (size % 2 == 0) { mid = mid.prev; } } size--; } return data; } // Function for finding middle of the stack int findMiddle() { if (size == 0) { System.out.println("Stack is empty now"); return -1; } return mid.data; } void deleteMiddleElement() { // This function will not only delete the middle // element // but also update the mid in case of even and // odd number of Elements // when the size is even then findmiddle() will show the // second middle element as mentioned in the problem // statement 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--; } } // Driver program to test functions of myStack public static void main(String args[]) { myStack ms = new myStack(); ms.push(11); ms.push(22); ms.push(33); ms.push(44); ms.push(55); ms.push(66); ms.push(77); ms.push(88); ms.push(99); System.out.println("Popped : " + ms.pop()); System.out.println("Popped : " + ms.pop()); System.out.println("Middle Element : " + ms.findMiddle()); ms.deleteMiddleElement(); System.out.println("New Middle Element : " + ms.findMiddle()); }}// This code is contributed by Abhishek Jha// Updated by Amsavarthan Lv |
Python3
''' Python3 Program to implement a stack that supports findMiddle() and deleteMiddle in O(1) time '''''' A Doubly Linked List Node '''class DLLNode: def __init__(self, d): self.prev = None self.data = d self.next = None''' Representation of the stack data structure that supports findMiddle() in O(1) time. The Stack is implemented using Doubly Linked List. It maintains pointer to head node, pointer to middle node and count of nodes '''class myStack: def __init__(self): self.head = None self.mid = None self.count = 0''' Function to create the stack data structure '''def createMyStack(): ms = myStack() ms.count = 0 return ms''' Function to push an element to the stack '''def push(ms, new_data): ''' allocate DLLNode and put in data ''' new_DLLNode = DLLNode(new_data) ''' Since we are adding at the beginning, prev is always NULL ''' new_DLLNode.prev = None ''' link the old list of the new DLLNode ''' new_DLLNode.next = ms.head ''' Increment count of items in stack ''' ms.count += 1 ''' Change mid pointer in two cases 1) Linked List is empty 2) Number of nodes in linked list is odd ''' if(ms.count == 1): ms.mid = new_DLLNode else: ms.head.prev = new_DLLNode # Update mid if ms->count is odd if((ms.count % 2) != 0): ms.mid = ms.mid.prev ''' move head to point to the new DLLNode ''' ms.head = new_DLLNode''' Function to pop an element from stack '''def pop(ms): ''' Stack underflow ''' if(ms.count == 0): print("Stack is empty") return -1 head = ms.head item = head.data ms.head = head.next # If linked list doesn't become empty, # update prev of new head as NULL if(ms.head != None): ms.head.prev = None ms.count -= 1 # update the mid pointer when # we have even number of elements # in the stack, i,e move down # the mid pointer. if(ms.count % 2 == 0): ms.mid = ms.mid.next return item# Function for finding middle of the stackdef findMiddle(ms): if(ms.count == 0): print("Stack is empty now") return -1 return ms.mid.datadef deleteMiddle(ms): if(ms.count == 0): print("Stack is empty now") return ms.count-=1 ms.mid.next.prev=ms.mid.prev ms.mid.prev.next=ms.mid.next if ms.count %2==1: ms.mid=ms.mid.next else: ms.mid=ms.mid.prev# Driver codeif __name__ == '__main__': ms = createMyStack() push(ms, 11) push(ms, 22) push(ms, 33) push(ms, 44) push(ms, 55) push(ms, 66) push(ms, 77) push(ms, 88) push(ms, 99) print("Popped : " + str(pop(ms))) print("Popped : " + str(pop(ms))) print("Middle Element : " + str(findMiddle(ms))) deleteMiddle(ms) print("New Middle Element : " + str(findMiddle(ms))) # This code is contributed by rutvik_56. # Updated by Amsavarthan Lv |
C#
/* C# Program to implement a stackthat supports findMiddle()and deleteMiddle in O(1) time */using System;class GFG { /* A Doubly Linked List Node */ public class DLLNode { public DLLNode prev; public int data; public DLLNode next; public DLLNode(int d) { data = d; } } /* Representation of the stack data structure that supports findMiddle() in O(1) time. The Stack is implemented using Doubly Linked List. It maintains pointer to head node, pointer to middle node and count of nodes */ public class myStack { public DLLNode head; public DLLNode mid; public int count; } /* Function to create the stack data structure */ myStack createMyStack() { myStack ms = new myStack(); ms.count = 0; return ms; } /* Function to push an element to the stack */ void push(myStack ms, int new_data) { /* allocate DLLNode and put in data */ DLLNode new_DLLNode = new DLLNode(new_data); /* Since we are adding at the beginning, prev is always NULL */ new_DLLNode.prev = null; /* link the old list of the new DLLNode */ new_DLLNode.next = ms.head; /* Increment count of items in stack */ ms.count += 1; /* Change mid pointer in two cases 1) Linked List is empty 2) Number of nodes in linked list is odd */ if (ms.count == 1) { ms.mid = new_DLLNode; } else { ms.head.prev = new_DLLNode; // Update mid if ms->count is odd if ((ms.count % 2) != 0) ms.mid = ms.mid.prev; } /* move head to point to the new DLLNode */ ms.head = new_DLLNode; } /* Function to pop an element from stack */ int pop(myStack ms) { /* Stack underflow */ if (ms.count == 0) { Console.WriteLine("Stack is empty"); return -1; } DLLNode head = ms.head; int item = head.data; ms.head = head.next; // If linked list doesn't become empty, // update prev of new head as NULL if (ms.head != null) ms.head.prev = null; ms.count -= 1; // update the mid pointer when // we have even number of elements // in the stack, i,e move down // the mid pointer. if (ms.count % 2 == 0) ms.mid = ms.mid.next; return item; } // Function for finding middle of the stack int findMiddle(myStack ms) { if (ms.count == 0) { Console.WriteLine("Stack is empty now"); return -1; } return ms.mid.data; } void deleteMiddle(myStack ms){ if (ms.count == 0) { Console.WriteLine("Stack is empty now"); return; } ms.count-=1; ms.mid.next.prev=ms.mid.prev; ms.mid.prev.next=ms.mid.next; if(ms.count %2!=0){ ms.mid=ms.mid.next; }else{ ms.mid=ms.mid.prev; } } // Driver code public static void Main(String[] args) { GFG ob = new GFG(); myStack ms = ob.createMyStack(); ob.push(ms, 11); ob.push(ms, 22); ob.push(ms, 33); ob.push(ms, 44); ob.push(ms, 55); ob.push(ms, 66); ob.push(ms, 77); ob.push(ms, 88); ob.push(ms, 99); Console.WriteLine("Popped : " + ob.pop(ms)); Console.WriteLine("Popped : " + ob.pop(ms)); Console.WriteLine("Middle Element : " + ob.findMiddle(ms)); ob.deleteMiddle(ms); Console.WriteLine("New Middle Element : " + ob.findMiddle(ms)); }}// This code is contributed// by Arnab Kundu// Updated by Amsavarthan Lv |
Javascript
class node { constructor(value) { this.value = value, this.prev = null, this.next = null }}class Mystack { constructor(){ this.head = null, this.middle = this.head, this.tail = this.head, this.size = 0 } // Function to insert value in a stack push(val) { if (!this.head) { let temp = new node(val) this.head = temp; this.middle = this.head; this.tail = this.head; this.size++ } else { let newTail = new node(val) this.tail.next = newTail newTail.prev = this.tail this.tail = this.tail.next this.size++ if (this.size % 2 !== 0) { this.middle = this.middle.next } } } // Function to remove values from stack pop() { if (!this.head) { console.log('stack is empty') } else { let temp = this.tail.prev this.tail = temp this.tail.next = null this.size-- if (this.size % 2 === 0) { this.middle = this.middle.prev } } } // Function to get the middle element of the stack findMiddle(){ console.log(this.middle.value) return this.middle.value } // Function to delete the middle value of the stack deleteMiddle() { let leader = this.middle.prev; let after = this.middle.next; leader.next = after after.prev = leader if (this.size % 2 !== 0) { this.middle = leader } else { this.middle = after } this.size-- console.log(this.middle.value) } // Function to print the remaining stack printStack() { let curr = this.head; let arr = [] while (curr) { arr.push(curr.value) curr = curr.next; } console.log(arr) return arr }}const helloStack = new Mystack()helloStack.push(10)helloStack.push(15) helloStack.push(30) helloStack.push(5) helloStack.push(8)helloStack.push(11) helloStack.pop() helloStack.findMiddle()helloStack.deleteMiddle()helloStack.deleteMiddle()helloStack.printStack() |
C
/* Program to implement a stack that supports findMiddle() and deleteMiddle in O(1) time */#include <stdio.h>#include <stdlib.h>/* A Doubly Linked List Node */struct DLLNode { struct DLLNode* prev; int data; struct DLLNode* next;};/* Representation of the stack data structure that supports findMiddle() in O(1) time. The Stack is implemented using Doubly Linked List. It maintains pointer to head node, pointer to middle node and count of nodes */struct myStack { struct DLLNode* head; struct DLLNode* mid; int count;};/* Function to create the stack data structure */struct myStack* createMyStack(){ struct myStack* ms = (struct myStack*)malloc(sizeof(struct myStack)); ms->count = 0; return ms;};/* Function to push an element to the stack */void push(struct myStack* ms, int new_data){ /* allocate DLLNode and put in data */ struct DLLNode* new_DLLNode = (struct DLLNode*)malloc(sizeof(struct DLLNode)); new_DLLNode->data = new_data; /* Since we are adding at the beginning, prev is always NULL */ new_DLLNode->prev = NULL; /* link the old list of the new DLLNode */ new_DLLNode->next = ms->head; /* Increment count of items in stack */ ms->count += 1; /* Change mid pointer in two cases 1) Linked List is empty 2) Number of nodes in linked list is odd */ if (ms->count == 1) { ms->mid = new_DLLNode; } else { ms->head->prev = new_DLLNode; if (ms->count & 1) // Update mid if ms->count is odd ms->mid = ms->mid->prev; } /* move head to point to the new DLLNode */ ms->head = new_DLLNode;}/* Function to pop an element from stack */int pop(struct myStack* ms){ /* Stack underflow */ if (ms->count == 0) { printf("Stack is empty\n"); return -1; } struct DLLNode* head = ms->head; int item = head->data; ms->head = head->next; // If linked list doesn't become empty, update prev // of new head as NULL if (ms->head != NULL) ms->head->prev = NULL; ms->count -= 1; // update the mid pointer when we have even number of // elements in the stack, i,e move down the mid pointer. if (!((ms->count) & 1)) ms->mid = ms->mid->next; free(head); return item;}// Function for finding middle of the stackint findMiddle(struct myStack* ms){ if (ms->count == 0) { printf("Stack is empty now\n"); return -1; } return ms->mid->data;}void deleteMiddle(struct myStack* ms){ if (ms->count == 0) { printf("Stack is empty now\n"); return; } ms->count -= 1; ms->mid->next->prev = ms->mid->prev; ms->mid->prev->next = ms->mid->next; if (ms->count % 2 != 0) { ms->mid=ms->mid->next; }else { ms->mid=ms->mid->prev; }}// Driver program to test functions of myStackint main(){ /* Let us create a stack using push() operation*/ struct myStack* ms = createMyStack(); push(ms, 11); push(ms, 22); push(ms, 33); push(ms, 44); push(ms, 55); push(ms, 66); push(ms, 77); push(ms, 88); push(ms, 99); printf("Popped : %d\n", pop(ms)); printf("Popped : %d\n", pop(ms)); printf("Middle Element : %d\n", findMiddle(ms)); deleteMiddle(ms); printf("New Middle Element : %d\n", findMiddle(ms)); return 0;}//Updated by Amsavarthan Lv |
Output
Popped : 99 Popped : 88 Middle Element : 44 New Middle Element : 55
The space complexity of the myStack class is O(n), where n is the number of elements in the stack, as the space used by the stack grows linearly with the number of elements.
Method 2: 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 which were added recently will be present in the deque. Insert operation on myStack will add an element into the back of the deque. The number of elements in the deque stays 1 more or equal to that in the stack, however, whenever the number of elements present in the deque exceeds the number of elements in the stack by more than 1 we pop an element from the front of the deque and push it into the stack. The pop operation on myStack will remove an element from the back of the deque. If after the pop operation, the size of the deque is less than the size of the stack, we pop an element from the top of the stack and insert it back into the front of the deque so that size of the deque is not less than the stack. We will see that the middle element is always the front element of the deque. So deleting of the middle element can be done in O(1) if we just pop the element from the front of the deque.
Consider Operations on My_stack:
Operation stack deque
add(2) { } {2}
add(5) {2} {5}
add(3) {2} {5,3}
add(7) {2,5} {3,7}
add(4) {2,5} {3,7,4}
deleteMiddle() {2,5} {7,4}
deleteMiddle() {2} {5,4}
pop() {2} {5}
pop() { } {2}
deleteMiddle() { } { }
C++
#include <bits/stdc++.h>using namespace std;class myStack { stack<int> st; deque<int> dq;public: void add(int data) { dq.push_back(data); if (dq.size() > st.size() + 1) { int temp = dq.front(); dq.pop_front(); st.push(temp); } } void pop() { int data = dq.back(); dq.pop_back(); if (st.size() > dq.size()) { int temp = st.top(); st.pop(); dq.push_front(temp); } } int getMiddleElement() { return dq.front(); } void deleteMiddleElement() { dq.pop_front(); if (st.size() > dq.size()) { // new middle element int temp = st.top(); // should come at front of deque st.pop(); dq.push_front(temp); } }};int main(){ myStack st; st.add(2); st.add(5); cout << "Middle Element: " << st.getMiddleElement() << endl; st.add(3); st.add(7); st.add(4); cout << "Middle Element: " << st.getMiddleElement() << endl; st.deleteMiddleElement(); cout << "Middle Element: " << st.getMiddleElement() << endl; st.deleteMiddleElement(); cout << "Middle Element: " << st.getMiddleElement() << endl; st.pop(); st.pop(); st.deleteMiddleElement();}//By- Vijay Chadokar |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class MyStack { Stack<Integer> s; Deque<Integer> dq; MyStack() { s = new Stack<Integer>(); dq = new ArrayDeque<Integer>(); } void add(int data) { dq.addLast(data); if (dq.size() > s.size() + 1) { int temp = dq.pollFirst(); s.push(temp); } } void pop() { int data = dq.pollLast(); if (s.size() > dq.size()) { int temp = s.pop(); dq.offerFirst(temp); } } int getMiddleElement() { return dq.getFirst(); } void deleteMiddleElement() { dq.pollFirst(); if (s.size() > dq.size()) { int temp = s.pop(); dq.offerFirst(temp); } }}class GFG { public static void main(String[] args) { MyStack s = new MyStack(); s.add(2); s.add(5); System.out.println("Middle element:" + s.getMiddleElement()); s.add(3); s.add(7); s.add(4); System.out.println("Middle element:" + s.getMiddleElement()); s.deleteMiddleElement(); System.out.println("Middle element:" + s.getMiddleElement()); s.deleteMiddleElement(); System.out.println("Middle element:" + s.getMiddleElement()); s.pop(); s.pop(); s.deleteMiddleElement(); }} |
Python3
# Python approach for above codest = []dq = []def add(data): dq.append(data) if (len(dq) > len(st) + 1): temp = dq[0] dq.pop(0) st.append(temp)def pop(): data = dq[len(dq) - 1] dq.pop() if (len(st) > len(dq)): temp = st[0] st.pop() dq.insert(temp,0)def getMiddleElement(): return dq[0]def deleteMiddleElement(): dq.pop(0) if (len(st) > len(dq)): # new middle element temp = st[0] # should come at front of deque st.pop() dq.insert(temp,0)add(2)add(5)print("Middle Element: ", getMiddleElement())add(3)add(7)add(4)print("Middle Element: ", getMiddleElement())deleteMiddleElement()print("Middle Element: ", getMiddleElement())deleteMiddleElement()print("Middle Element: ", getMiddleElement())pop()pop()deleteMiddleElement()# This code is contributed by adityamaharshi21 |
C#
// Include namespace systemusing System;using System.Collections.Generic;public class MyStack{ public Stack<int> s; public LinkedList<int> dq; public MyStack() { this.s = new Stack<int>(); this.dq = new LinkedList<int>(); } public void add(int data) { this.dq.AddLast(data); if (this.dq.Count > this.s.Count + 1) { var temp = this.dq.First.Value; this.dq.RemoveFirst(); this.s.Push(temp); } } public void pop() { var data = this.dq.Last.Value; this.dq.RemoveLast(); if (this.s.Count > this.dq.Count) { var temp = this.s.Pop(); this.dq.AddFirst(temp); } } public int getMiddleElement() { return this.dq.First.Value; } public void deleteMiddleElement() { this.dq.RemoveFirst(); if (this.s.Count > this.dq.Count) { var temp = this.s.Pop(); this.dq.AddFirst(temp); } }}public class GFG{ public static void Main(String[] args) { var s = new MyStack(); s.add(2); s.add(5); Console.WriteLine("Middle element:" + s.getMiddleElement().ToString()); s.add(3); s.add(7); s.add(4); Console.WriteLine("Middle element:" + s.getMiddleElement().ToString()); s.deleteMiddleElement(); Console.WriteLine("Middle element:" + s.getMiddleElement().ToString()); s.deleteMiddleElement(); Console.WriteLine("Middle element:" + s.getMiddleElement().ToString()); s.pop(); s.pop(); s.deleteMiddleElement(); }}// This code is contributed by aadityaburujwale. |
Javascript
// Javascript code for deleting// the middle element in O(1)class myStack { constructor() { this.st = []; this.dq = []; } add(data) { this.dq.push(data); if (this.dq.length > this.st.length + 1) { let temp = this.dq[0]; this.dq.shift(); this.st.push(temp); } } pop() { let data = this.dq[this.dq.length - 1]; this.dq.shift(); if (this.dq.length < this.st.length) { let temp = this.st[0]; this.st.shift(); this.dq.unshift(temp); } } getMiddleElement() { return this.dq[0]; } deleteMiddleElement() { this.dq.shift(); if (this.dq.length < this.st.length) { // new middle element let temp = this.st[0]; // should come at front of deque this.st.pop(); this.dq.unshift(temp); } }}// Driver Codelet st = new myStack;st.add(2);st.add(5);console.log("Middle Element: ", st.getMiddleElement());st.add(3);st.add(7);st.add(4);console.log("Middle Element: ", st.getMiddleElement());st.deleteMiddleElement();console.log("Middle Element: ", st.getMiddleElement());st.deleteMiddleElement();console.log("Middle Element: ", st.getMiddleElement());st.pop();st.pop();st.deleteMiddleElement();// This code is contributed by adityamaharshi21 |
Output
Middle Element: 5 Middle Element: 3 Middle Element: 7 Middle Element: 5
This article is contributed by Keyut. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
