fork(3) download
copy 
  1. import java.util.Stack;
  2. interface StackImpl{
  3. 	void push(int data);
  4. 	int pop();
  5.     int getMin();
  6.     int peek();
  7.     boolean isEmpty();
  8. }
  9. /**
  10.  * Implement Stack with Minimum Element Lookup in Constant Time
  11.  * @author Prateek Rathore
  12.  */
  13. class CustomStack implements StackImpl{
  14.  
  15. 	private Stack<Integer> minStack; // stack holding min Element
  16. 	private Stack<Integer> original; // orginal stack holding data
  17.  
  18. 	public CustomStack() {
  19. 		this.original = new Stack<Integer>();
  20. 		this.minStack = new Stack<Integer>();
  21. 	}
  22. 	/**
  23. 	 * Push Subroutine
  24. 	 */
  25. 	@Override
  26. 	public void push(int data) {
  27. 		if(original.isEmpty())
  28. 			minStack.push(data);
  29.  
  30. 		else{
  31. 			if(data < minStack.peek())
  32. 				minStack.push(data);
  33. 		}
  34. 		original.push(data);
  35. 	}
  36.  
  37. 	/**
  38. 	 *Pops element from the custom stack 
  39. 	 */
  40. 	@Override
  41. 	public int pop() {
  42. 		if(original.peek() == minStack.peek())
  43. 			minStack.pop();
  44.  
  45. 		return original.pop();
  46. 	}
  47.  
  48. 	/**
  49. 	 * Peek Minimum Element
  50. 	 */
  51. 	@Override
  52. 	public int getMin(){
  53. 		return minStack.peek();
  54. 	}
  55.  
  56. 	/**
  57. 	 * Peek for the element
  58. 	 */
  59. 	@Override
  60. 	public int peek() {
  61. 		return original.peek();
  62. 	}
  63.  
  64. 	@Override
  65. 	public boolean isEmpty() {
  66. 		return original.isEmpty();
  67. 	}
  68.  
  69. 	public static void main(String[] args) {
  70. 		CustomStack stack = new CustomStack();
  71.  
  72. 		//7 , 6 , 8 , 5 , 2 , 3, 1, 9, 4
  73. 		stack.push(7);
  74. 		stack.push(6);
  75. 		stack.push(8);
  76. 		stack.push(5);
  77. 		stack.push(2);
  78. 		stack.push(3);
  79. 		stack.push(1);
  80. 		stack.push(9);
  81. 		stack.push(4);
  82. 		System.out.println("Minimum Eleement is : "+ stack.getMin());
  83. 		System.out.println("Poped : " + stack.pop());
  84. 		System.out.println("Poped : " + stack.pop());
  85. 		System.out.println("Poped : " + stack.pop());
  86. 		System.out.println("Minimum Eleement is : "+ stack.getMin());
  87. 	}
  88. }
  89.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum Eleement is : 1
Poped : 4
Poped : 9
Poped : 1
Minimum Eleement is : 2
https://ideone.com/wDzWB2
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!