Stacks & QueuesProblem 4 of 38
Find the middle element of a stack
Problem Statement
Design a stack that supports the following operations in addition to push, pop:
findMiddle(): Returns the middle element of the stackdeleteMiddle(): Deletes the middle element of the stack
For a stack with n elements, the middle element is at position (n+1)/2 from the bottom (1-indexed), or n/2 from the top (0-indexed).
Example:
Stack: [1, 2, 3, 4, 5] (5 is top)
findMiddle() -> 3
deleteMiddle() -> Stack becomes [1, 2, 4, 5]
Stack: [1, 2, 3, 4] (4 is top)
findMiddle() -> 2 (or 3 depending on convention)
Approach 1: Using Auxiliary Stack (Brute Force)
Intuition
To find the middle, pop half the elements to an auxiliary stack, access the middle, then restore the elements. This is simple but inefficient.
Algorithm
- Calculate the middle position (size/2)
- Pop elements from main stack to auxiliary stack until reaching middle
- Access/delete the middle element
- Push elements back from auxiliary stack to main stack
java
import java.util.*;
public class StackWithMiddle {
private Stack<Integer> stack;
public StackWithMiddle() {
stack = new Stack<>();
}
public void push(int x) {
stack.push(x);
}
public int pop() {
if (stack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack.pop();
}
public int findMiddle() {
if (stack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
Stack<Integer> temp = new Stack<>();
int n = stack.size();
int mid = n / 2;
// Pop half elements to temp
for (int i = 0; i < mid; i++) {
temp.push(stack.pop());
}
int middleElement = stack.peek();
// Restore elements
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
return middleElement;
}
public void deleteMiddle() {
if (stack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
Stack<Integer> temp = new Stack<>();
int n = stack.size();
int mid = n / 2;
// Pop half elements to temp
for (int i = 0; i < mid; i++) {
temp.push(stack.pop());
}
// Remove middle element
stack.pop();
// Restore elements
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
}
public int size() {
return stack.size();
}
public boolean empty() {
return stack.isEmpty();
}
public static void main(String[] args) {
StackWithMiddle s = new StackWithMiddle();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
System.out.println("Middle: " + s.findMiddle()); // 3
s.deleteMiddle();
System.out.println("After delete, new middle: " + s.findMiddle()); // 2
}
}Complexity Analysis
- Time Complexity: O(n) for findMiddle and deleteMiddle
- Space Complexity: O(n) for auxiliary stack
Approach 2: Using Doubly Linked List (Optimal)
Intuition
Use a doubly linked list to implement the stack. Maintain a pointer to the middle element. Update the middle pointer on each push/pop operation based on the new size of the stack. This allows O(1) access to the middle element.
Algorithm
- Use a DLL with head pointing to top of stack
- Maintain a middle pointer
- On push: if size was even, move middle to previous node
- On pop: if size was odd, move middle to next node
- For deleteMiddle: remove middle node and update pointer
java
public class StackWithMiddleOptimal {
private class Node {
int data;
Node prev, next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node head; // Top of stack
private Node mid; // Middle element
private int count;
public StackWithMiddleOptimal() {
head = null;
mid = null;
count = 0;
}
public void push(int x) {
Node newNode = new Node(x);
if (count == 0) {
head = mid = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
// If count was even, move middle to previous
if (count % 2 == 0) {
mid = mid.prev;
}
}
count++;
}
public int pop() {
if (count == 0) {
throw new RuntimeException("Stack is empty");
}
int val = head.data;
head = head.next;
if (head != null) {
head.prev = null;
}
count--;
// If count was odd, move middle to next
if (count > 0 && count % 2 == 1) {
mid = mid.next;
}
if (count == 0) {
mid = null;
}
return val;
}
public int findMiddle() {
if (count == 0) {
throw new RuntimeException("Stack is empty");
}
return mid.data;
}
public void deleteMiddle() {
if (count == 0) {
throw new RuntimeException("Stack is empty");
}
if (count == 1) {
head = mid = null;
count = 0;
return;
}
Node toDelete = mid;
// Update middle pointer before deletion
if (count % 2 == 1) {
mid = mid.next;
} else {
mid = mid.prev;
}
// Remove the middle node
if (toDelete.prev != null) {
toDelete.prev.next = toDelete.next;
}
if (toDelete.next != null) {
toDelete.next.prev = toDelete.prev;
}
count--;
}
public int size() {
return count;
}
public boolean empty() {
return count == 0;
}
public static void main(String[] args) {
StackWithMiddleOptimal s = new StackWithMiddleOptimal();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
System.out.println("Middle: " + s.findMiddle()); // 3
s.deleteMiddle();
System.out.println("New Middle: " + s.findMiddle()); // 2
s.push(6);
System.out.println("Middle after push: " + s.findMiddle()); // 4
}
}Complexity Analysis
- Time Complexity: O(1) for all operations including findMiddle and deleteMiddle
- Space Complexity: O(n) for storing elements in doubly linked list
Key Takeaways
- Doubly linked list enables O(1) middle access by maintaining a middle pointer
- The key insight is to update the middle pointer during push/pop based on parity of count
- For push: move middle backward if count was even (adding element increases elements above middle)
- For pop: move middle forward if count was odd (removing element decreases elements above middle)
- This is a classic example of trading space for time optimization
- The brute force approach with auxiliary stack is O(n) for middle operations