Category Archives: Stack

Implementing Stack with GetMin operation

In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack.

The trick here is to use another stack which stores the minimum values of the original stack. The top of Min-stack always contains the minimum of stack elements so far inserted.

The Push operation is implemented as follows.
When an element is pushed on to the stack, we have to compare that with top of min-stack. If the new element is minimum, We have to push that element onto the min-stack too. We need not push that element on to min-stack if it is not lesser than top of min-stack.

The Pop operation is implemented as follows.
While popping the element from the original stack, we should also make sure that if minimum element is popped, it should also be removed from Min-stack.

The following table explains the logic.



Operation
Stack
Min-stack
Description
Push(5)
5
5
5 pushed on to both the stacks
Push(2)
5 2
5 2
2 is pushed to both stacks
Push(3)
5 2 3
5 2
3 is not pushed to min-stack because it is not minimum
Push(1)
5 2 3 1
5 2 1
1 is pushed to both because it is new minimum
Pop()
5 2 3
5 2
1 is popped from both because it is minimum
Pop()
5 2
5 2
No need to pop from min-stack because 3 is not minimum

  
Observe that top of min-stack always contains the minimum element.

Following is the Java code which implements the above approach.

import java.util.Stack;

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/4/13
* Time: 7:04 AM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
MinStack mStack = new MinStack();
mStack.push(5);
System.out.println(mStack.getMin());
mStack.push(2);
System.out.println(mStack.getMin());
mStack.push(3);
System.out.println(mStack.getMin());
mStack.push(1);
System.out.println(mStack.getMin());
mStack.pop();
System.out.println(mStack.getMin());
mStack.pop();
mStack.pop();
System.out.println(mStack.getMin());
}
static class MinStack
{
Stack<Integer> dataStack;
Stack<Integer> minStack;
public MinStack()
{
dataStack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int d)
{
//Push that element to the original stack
dataStack.push(d);
//If either Min-stack is empty or
// newly inserted element is lesser, push it into min-stack also
if( minStack.empty() || d < minStack.peek())
{
minStack.push(d);
}
}
public int pop()
{
//pop the element from the original stack
int res = dataStack.pop();
//If the popped element is also the minimum,
//pop from the min-stack also
if( res == minStack.peek() )
{
minStack.pop();
}
return res;
}
//This function simply returns the top of min-stack
public int getMin()
{
return minStack.peek();
}
}
}

Implementing a stack using queue

How do you implement a stack using Queue?

This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack.

This can be done using two queues. One queue acts as the main queue while the other acts as the helper queue.

There are two approaches to solve this problem.

  • Making the pop operation costly and push operation simple
  • Making the push operation costly and pop operation simple

First approach:
 

  • Push operation is simple. It always adds the element to the main queue.
  • To implement pop operation, we remove all but one element from the main queue and add them to the helper queue. We finally remove the remaining one element from main queue and return it. Mark the helper queue as main queue.


Second approach:

  • Pop operation is simple. It simply removes element from the main queue and return it.
  • Push operation first adds the element to the helper queue. Then it removes elements from main queue one by one and add them to the helper queue. The intent behind this is to make the last inserted element to be available for removing. Finally make the helper queue as main queue.


The following table gives snapshots of the algorithm at different stages. Assume the queue is presented from left to right. The left most element is at the front of the queue and right most element is at the rear of the queue.


Operation
First queue
Second queue
Result
Push(1)
1
1 added to the main queue
Push(2)
1 2
2 added to the main queue
Pop()
1
Second queue became the main queue and 2 is removed and returned.
Push(3)
1 3
3 added to the main queue
Push(4)
1 3 4
4 added to the main queue
Pop()
1 3
First queue became the main queue and 4 is removed and returned.

Observe that the elements are popped in the LIFO order.

We will see the implementation of first approach in this post. Implementation of second approach can be taken as an exercise.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 8/26/13
* Time: 4:47 PM
*/
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args)
{
Stack2Queues stck = new Stack2Queues();
stck.push(1);
stck.push(2);
System.out.println(stck.pop());
stck.push(3);
System.out.println(stck.pop());
System.out.println(stck.pop());
stck.push(4);
stck.push(5);
System.out.println(stck.pop());
System.out.println(stck.pop());
}
static class Stack2Queues
{
Queue<Integer> q1;
Queue<Integer> q2;
int activeQ;
public Stack2Queues()
{
q1 = new LinkedList<Integer>();
q2 = new LinkedList<Integer>();
activeQ = 1;
}
public void push(int data)
{
Queue<Integer> q;
if( activeQ == 1)
q = q1;
else
q = q2;
q.add(data);
}
public int pop()
{
Queue<Integer> mainQ;
Queue<Integer> helperQ;
if( activeQ == 1)
{
mainQ = q1;
helperQ = q2;
activeQ = 2;
}
else
{
mainQ = q2;
helperQ = q1;
activeQ = 1;
}
while( mainQ.size() > 1 )
{
helperQ.add(mainQ.remove());
}
return mainQ.remove();
}
}
}

Implementing Queue using Stack

How to implement a Queue data structure using Stack?

We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.

To quickly refresh Stacks, and Queues knowledge;
Stacks are the LIFO (Last-In-First-Out) list in which the last element inserted is the first to be removed.(Example: stack of plates kept in a cafeteria)
Queue is a FIFO ( First-In-First-Out) list in which the first element inserted is the first to be removed (Example: Line of people waiting for a ticket at any counter)

The trick here is to use two stacks, one for adding the data(push-stack), and one for removing the data(pop-stack). So we have to implement enqueue() and dequeue() operations in terms of only stack methods.

enqueue():
First check if the pop-stack is empty. If it is empty, we directly push the element onto the push-stack.
Otherwise We pop all the elements from the pop-stack one-by-one and push them onto the push-stack. Then we push the current element.

dequeue():

First check if the push-stack is empty. If it is empty, we directly pop the element from the pop-stack.
Otherwise we pop all the element from the push-stack one-by-one and push them onto the pop-stack.
Then we pop the element from the pop-stack and return that.

Let us understand this logic with an example. Let us represent the stacks from left to right assuming that the rightmost element is top.

The following table explains a series of enqueue() and dequeue() operations and the status of push and pop-stacks.


Operation
Push-stack
Pop-stack
Comment
Enqueue(1)
1
1 added to push-stack
Enqueue(2)
1, 2
2 added to push-stack
Dequeue()
2
1 removed from queue
Enqueue(3)
2, 3
3 added to push-stack
Enqueue(4)
2, 3, 4
4 added to push-stack
Dequeue()
4, 3
2 removed from queue
Enqueue(5)
3, 4, 5
5 added to push-stack
Dequeue()
5, 4
3 removed from queue

Observe that order of the removed elements. They are in the order of insertion. Performing a series of only enqueue/dequeue operations does not cause any performance problems, as it does not require the elements to be copied between the two stacks.

At any point of time, only one stack is occupied
The worst case occurs when enqueue, and dequeue operations are performed alternatively.

*Abstract Data type: A specification which gives the methods that should be supported by a data structure.

Following is the implementation in Java. I have omitted some exception handling to keep the code simple and clear.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 8/23/13
* Time: 1:20 PM
* To change this template use File | Settings | File Templates.
*/
import java.util.Stack;
public class Main {
public static void main(String[] args)
{
Q2Stacks intQueue = new Q2Stacks();

intQueue.enqueue(1);
intQueue.enqueue(2);
System.out.println(intQueue.dequeue());
intQueue.enqueue(3);
System.out.println(intQueue.dequeue());
intQueue.enqueue(4);
intQueue.enqueue(5);
System.out.println(intQueue.dequeue());
intQueue.enqueue(6);
System.out.println(intQueue.dequeue());
System.out.println(intQueue.dequeue());
System.out.println(intQueue.dequeue());

}
static class Q2Stacks
{
private Stack<Integer> pushStack;
private Stack<Integer> popStack;

public Q2Stacks()
{
pushStack = new Stack<Integer>();
popStack = new Stack<Integer>();
}

public void enqueue(int data)
{
if( !popStack.empty() )
{
while( !popStack.empty())
{
pushStack.push(popStack.pop());
}
}
pushStack.push(data);
}

public int dequeue()
{
if( !pushStack.empty() )
{
while( !pushStack.empty() )
{
popStack.push( pushStack.pop() );
}
}
return popStack.pop();
}
}
}

Bracket matching problem

Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example.

Let us consider the following problem. We have a string which contains only ‘(‘ and ‘)’ characters. We have to write a program to check if it forms a valid expression.
For example the string “(()())” is a valid expression where as “(()()” and “())” are not.

The algorithm for solving the question goes like this. 

1. For each character in the string
    If the symbol is ‘(‘
         push it on to the stack
   else
        If the stack is empty
            return false
       If top of the stack contains ‘(‘
            pop off the top element
2. If the stack is empty return true otherwise return false

Here is the program which implements the above algorithm.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool isValidExpr(string input)
{
stack<char> stck;

for(int i = 0; i < input.length() ; i++)
{
char ch = input.at(i);

if( ch == '(' ) //if open brace, push
{
stck.push(ch);
}
else //closed brace
{
if( stck.empty() )// if stack is empty, there no matching open brace
return false;
if ( stck.top() == '(' ) //matching open brace found, so pop
{
stck.pop();
}
}
}
if( stck.empty() )
return true;
return false;
}

int main()
{
string inputExpr;
cin>>inputExpr;
if( isValidExpr(inputExpr) )
cout<<"Valid Expression";
else
cout<<"Invalid Expression";
return 0;
}