algorithm - Design a stack with operations on middle element

Question

How to implement a stack which will support 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. Find Middle which will return middle element of the stack.
4. Delete Middle which will delete the middle element

Answer 1

Use a LinkedList data structure with an extra pointer to the middle element. Also, you need another variable Var to store whether the LinkedList has an even or odd elements.

• Push which adds an element to the top of stack.

Add the element to the head of the LinkedList. Update the pointer to the middle element according to Var

• Pop which removes an element from top of stack.

Remove the head of the LinkedList. Update the pointer to the middle element according to Var

• Find Middle which will return middle element of the stack.

Use the pointer to the middle element

• Delete Middle which will delete the middle element

Copy next element's value to middle, remove next element. Here is a more detailed description: http://www.mytechinterviews.com/singly-linked-list-delete-node

Answer 2

Use a LinkedList datastructure with a pointer to head, tail, and middle elements.

This would give you the O(1) time complexity for pushing, popping, and deleting the middle elements as well as the search.

The only trick would be to move the "middle" element pointer correctly when adding or subtracting elements from this datastructure.

Answer 3

Here is the implementation based on array

/**
 * Stack implementation with 
 * push // push the element at top of stack
 * pop // removes and returns the element from top of stack
 * findMiddle // returns the element from middle of stack
 * deleteMiddle // deletes the element from middle of stack
 * @author manjeet
 * @param <E>
 */

public class Stack<E> {
  private final int size;
  private int top;
  private E[] elements;

  /**
   * Constructor with default size
   */
  public Stack() {
    this(10);
  }

  public Stack(int s) {
    size = s > 0 ? s : 10;
    top = -1;
    elements = (E[]) new Object[size]; 
  }

  /**
   * Push element e to stack if it is not full
   * @param e
   */
  public void push(E e) {
    if (top == size - 1){
     // if stack is full
        System.out.println("Stack is full, cannot push element " +  e);
    }else{
        elements[++top] = e; // place e on Stack
    } 
  }

  /**
   * pop element from the top of the stack if it is not empty
   * @return top of the stack
   */
  public E pop() {
    E e = null;
    if (top == -1){
     // if stack is empty
        System.out.println("Stack is empty, cannot pop");
    }else{
        e = elements[top--]; // remove and return top element of Stack
    } 
    return e;
  }

  /**
   * Give middle element of the stack if it is not empty
   * @return middle element of the stack
   */
  E findMiddle() {
      if (top == -1){
          System.out.println("Stack is empty, cannot pop");
          return null;
      }
      return elements[top/2];
  }

  /**
   * Delete middle element of the stack if it is not empty
   * @return middle element of the stack
   */
  E deleteMiddle(){
      if (top == -1){
          System.out.println("Stack is empty, cannot pop");
          return null;
      }
      int index = (int)top/2;
      E middle = elements[index];
      System.arraycopy(elements, index+1 , elements, index, (top-index));
      top--;
      return middle;
  }

  public static void main(String args[]) {

      Stack<Integer> stack = new Stack<Integer>();
      stack.push(1);
      stack.push(2);
      stack.push(3);
      stack.push(4);
      stack.push(5);
      stack.push(6);
      stack.push(7);

      System.out.println("deleted=" + stack.deleteMiddle());
      System.out.println("middle=" + stack.findMiddle());
      System.out.println("popped=" + stack.pop());



    }
}