Category Archives: Stack

Get Minimum Element From Stack in O(1)

By | | , ,
Leave a comment

Get minimum element from stack in O(1).

In this problem, we have to design a stack that supports push, pop, top, and retrieving the minimum element in constant time (O(1)).

      push(x) — Push element x onto stack.

     pop() — Removes the element on top of the stack.

     top() — Get the top element.

     getMin() — Retrieve the minimum element in the stack.

For example: Suppose, If we push the following elements in a stack.

9  ==> Top
1
2
3

Then if we call getMin() method, It should return 1 in O(1) (constant time).

→

Implement Queue using Two Stacks – Java Code & Algorithm

By | | , , ,
Leave a comment

How to implement a queue using two stacks. In this tutorial, I am going to discuss how to implement a first in first out (FIFO) queue using only two stacks.

In this problem, we are going to implement following methods of QueueUsingStack class:

void push(int x) – Insert an element x.
int pop() –  Removes the element (In FIFO order).
int peek() – Returns the element which is present at the front of the queue.
boolean empty() – Returns true if no element is present else false.

For example –

→

Check Balanced Parentheses in an Expression

By | | , , ,
Leave a comment

Write a java code to check balanced parentheses in an expression using stack.

Given an expression containing characters ‘{‘,’}’,'(‘,’)’,'[‘,’]’. We have to write a code to check whether an input string has valid parentheses.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example –

i) {[]}) – Invalid

ii) {()}[] – Valid

→