Middle Stack

Design a stack with operations on middle element

The idea is to use Doubly Linked List (DLL). We can delete middle element in O(1) time by maintaining mid pointer. We can move mid pointer in both directions using previous and next pointers.

  1. void push(int val); Time complexity: O(1)

  2. int pop(); Time complexity: O(1)

  3. int mid(); Time complexity: O(1)

public class MidStack {
    Node head = null;
    Node mid = null;
    int count;

    public MidStack() {
        this.count = 0;
    }

    public void push(int val) {
        Node newNode = new Node(val);
        newNode.prev = null; // since we are adding at the beginning, prev is always NULL.

        newNode.next = head; // link the added node to the previous list
        this.count++;    // increase the number of items in the stack

        // change the mid pointer in two cases
        // 1. when we insert the first element
        // 2. number of the nodes in the list is odd
        if (this.count == 1) {
            mid = newNode;
        } else {
            head.prev = newNode;
            if (count % 2 != 0) {
                mid = mid.prev;
            }

        }
        head = newNode; // move head ot point to the new node.
    }

    public int pop() {
        if (this.count == 0) {
            return -1;
        }
        Node tmpHead = this.head;
        int item = head.value;
        this.head = tmpHead.next;

        // if the linked list doesn't become empty, update prev pointer to null
        if (this.head != null) {
            this.head.prev = null;
        }

        this.count--;

        // update the mid pointer when we have even number of elements in the stack
        if (this.count % 2 == 0) {
            this.mid = this.mid.next;
        }

        return item;
    }

    public int findMid() {
        if (this.count == 0) {
            return -1;
        }
        return this.mid.value;
    }
}

class Node {
    int value;
    Node prev;
    Node next;

    public Node(int value){
        this.value = value;
    }
}

Another implmentation found from Github

public class MidStack<E> {
    private class Entry<E> {
        E elem;
        Entry<E> prev;
        Entry<E> next;

        Entry(E elem) {
            this.elem = elem; prev = null; next = null;
        }
    }

    Entry<E> top;
    Entry<E> mid;
    int size;

    public MidStack() {
        top = null;
        mid = null;
        size = 0;
    }

    public void push(E elem) {
        Entry<E> entry = new Entry<E>(elem);
        if (top != null) {
            top.next = entry;
            entry.prev = top;
        }
        top = entry;
        size++;
        if (mid == null) mid = top;
        else mid = size()%2 == 1 ? mid.next : mid;
    }

    public E pop(E elem) {
        if (size() == 0)
            throw new EmptyStackException();
        E r = top.elem;
        top = top.prev;
        size--;
        mid = size()%2 == 0 ? mid.prev : mid;
        return r;
    }

    public E findMiddle() {
        if (size() == 0)
            throw new EmptyStackException();
        return mid.elem;
    }

    public void deleteMiddle() {
        if (size() == 0)
            throw new EmptyStackException();
        if (size() == 1) 
            mid = top = null;
        size--;
        mid.next.prev = mid.prev;
        if (mid.prev != null) mid.prev.next = mid.next;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        MidStack<Integer> stack = new MidStack<Integer>();
        stack.push(1);
        System.out.println(stack.findMiddle());
        stack.push(2);
        stack.push(3);
        System.out.println(stack.findMiddle());
        stack.deleteMiddle();
        stack.push(4);
        stack.push(5);
        System.out.println(stack.findMiddle());
    }
}