CC-19 : Implement Stack that returns middle element in O(1) time.

Description:

Implement and test a stack that returns the middle element in O(1) time.

Test cases and expected outputs:

Input Parameters	Expected outputs
Stack nodes: (top of stack)28 <- 3 <- 34 <- 17 <- 33 <- 9 <-	Stack size: 6 Stack Middle: 34
Stack nodes: (top of stack)3 <- 34 <- 17 <- 33 <- 9 <-	Stack size: 5 Stack Middle: 17

Pseudocode:

The stack will internally use two Deques for storing the elements.

In case of even number of elements in the stack, the first Deque will store first half of the elements of the stack while the second Deque will store second half of elements of the stack.

In case of odd number of elements in the stack, the first Deque will store first half of the elements plus one element, while the second Deque will store second half of elements of the stack.

This way the last element of the first Deque will always be the middle element of the stack and can be returned in O(1) time.

add() method:

Add the data as first element of Deque1.

If Deque1.size() is greater than Deque2.size()+1:

Remove last element of Deque1 and add as first element of Deque2.

remove() method:

Remove first element of Deque1 and set its data value in variable removedInt.

If Deque1.size() is less thanDequeue2.size():

Remove first element of Deque2 and add as last element of Deque1.

Return removedInt.

getMiddle() method:

return last element of Deque1.

Code:

public class StackWithMiddleInO1 {
	
private Deque<Integer> deque1=new LinkedList<Integer>();
private Deque<Integer> deque2=new LinkedList<Integer>();

public int get() {
	return deque1.peekFirst();
}

public int getMiddle() {
	return deque1.peekLast();
}

public boolean add(int data){
	deque1.addFirst(data);
	if (deque1.size() > deque2.size()+1) {
		deque2.offerFirst(deque1.pollLast());
	}
	return true;
}

public int remove() {
	int removedInt=deque1.pollFirst();
	if (deque1.size() < deque2.size()) {
		deque1.offerLast(deque2.pollFirst());
	}
	return removedInt;
}

public int getSize() {
	return (deque1.size()+deque2.size());
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;

public class StackWithMiddleInO1 {
	
private Deque<Integer> deque1=new LinkedList<Integer>();
private Deque<Integer> deque2=new LinkedList<Integer>();

public int get() {
	return deque1.peekFirst();
}

public int getMiddle() {
	return deque1.peekLast();
}

public boolean add(int data){
	deque1.addFirst(data);
	if (deque1.size() > deque2.size()+1) {
		deque2.offerFirst(deque1.pollLast());
	}
	return true;
}

public int remove() {
	int removedInt=deque1.pollFirst();
	if (deque1.size() < deque2.size()) {
		deque1.offerLast(deque2.pollFirst());
	}
	return removedInt;
}

public int getSize() {
	return (deque1.size()+deque2.size());
}

public void printStack() throws Exception   {
    System.out.println();
	System.out.println("**********************************************************");
	System.out.print("Stack nodes: ");
	Iterator itr=deque1.iterator();
	System.out.print("(top of stack)");
	while (itr.hasNext()) {
		System.out.print(itr.next());	
		System.out.print(" <- ");
	} 
	itr=deque2.iterator();
	while (itr.hasNext()) {
		System.out.print(itr.next());
		System.out.print(" <- ");
	} 
	System.out.println();
		System.out.println("**********************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}  
  	
public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	try {
	StackWithMiddleInO1 stack=new StackWithMiddleInO1();
	System.out.print("Add to Stack 9");
	stack.add(9);
	stack.printStack();
	System.out.print("Add to Stack 33");
	stack.add(33);
	stack.printStack();
	System.out.print("Add to Stack 17");
	stack.add(17);
	stack.printStack();
	System.out.print("Add to Stack 34");
	stack.add(34);
	stack.printStack();
	System.out.print("Add to Stack 3");
	stack.add(3);
	stack.printStack();
	System.out.print("Add to Stack 28");
	stack.add(28);
	stack.printStack();
	
	System.out.println("Stack size: "+stack.getSize());
	System.out.println("Stack Middle: "+stack.getMiddle());
	
	System.out.print("\nRemove from Stack");
	stack.remove();
	stack.printStack();
	System.out.println("Stack size: "+stack.getSize());
	System.out.println("Stack Middle: "+stack.getMiddle());
	
	System.out.print("Remove from Stack");
	stack.remove();
	stack.printStack();
	System.out.println("Stack size: "+stack.getSize());
	System.out.println("Stack Middle: "+stack.getMiddle());
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
	
}
	
}