# Implement queue using stack

In last post, we learned about stack data structure, in this post, we will discuss another data structure called queue. However, problem at hand is to implement queue using stack. Implement following functions on queue using stack
1. push() : inserts element at the back of queue.
2. pop() : removes element from front of the queue.
3. peek() : return element at front of the queue.
4. empty() : returns true if there is no element in queue.

Keep in mind that you can only use standard stack operations : push(), pop(), peek() and empty()

Stack is data structure where the element which is entered at top is taken out from top. It’s called LIFO pattern. Oppose to that queue is a FIFO data structure, where elements are entered at the rear and taken out from front. So effectively, we have to implement a FIFO data structure using LIFO data structure.

## Implement queue using stack : Line of thoughts

To implement a FIFO using LIFO data structure, we need two stacks.

Push()
When element is inserted i.e `push()` operation, new element has to be pushed down the stack at bottom, as this should be the last element to be popped. So, to push an element in queue, we will take out all existing elements from stack s1 and put them into stack s2. Now, push the new element on to stack s1. At last, pop all elements from stack s2 back to stack s1. Below picture shows what happens when you we push 3 to queue and what happens behind the scene using stacks.

Complexity of push operation with this method is `O(n)`. If there are n elements already inserted into queue, inserting a new element will require n pops from s1, n pushes to s2, then n pops from s2 and then again pushes to s1.

Pop()
If we follow the push operation described above, pop operation would be nothing but to return top of s1, which is constant operation with complexity of `O(1)`.

Peek and empty functions also run always on stack s1. For peek, return `s1.peek()` and for empty return `s1.empty()`

### Queue with stack : Push O(n), pop O(1) implementation

```package com.company;

import java.util.Stack;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStack {
private Stack<Integer> s1;
private Stack<Integer> s2;

public QueueWithStack(){
s1 = new Stack<>();
s2 = new Stack<>();
}

public void push(int x){
if(s1.empty()) s1.push(x);
else{
while(!s1.empty()){
s2.push(s1.pop());
}
s2.push(x);
while(!s2.empty()){
s1.push(s2.pop());
}
}
}

public int pop(){
if(s1.empty()) return -1;
return s1.pop();
}

public boolean isEmpty(){
return s1.empty();
}

public int peek(){
return s1.peek();
}
}
```

Test class for above implementation would be:

```package test;

import com.company.QueueWithStack;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStackTest {

QueueWithStack tester = new QueueWithStack();
@Test
public void queueTest() {

tester.push(2);
tester.push(3);
tester.push(5);
tester.push(1);

assertEquals(2, tester.pop());
assertEquals(3, tester.pop());
assertEquals(5, tester.peek());
assertEquals(false, tester.isEmpty());
}
}
```

Can we do better than `O(n)` while pushing element in queue?

### Queue with stack : Push O(1), pop amortized complexity O(1) implementation

Push()
What if we push on s1 as it is. What does it change? It make push operation on queue `O(1)`.

Pop()
How does it impacts pop operation? If we pop all element from s1 and push them onto s2, at the top of s2 is actually the element we need. Also, due to this pop and push operation, s2 now contains all the elements in correct pop order for queue.
So idea is to always push in s1 as it is, however when popping out, check if s2 is empty or not? If not, then pop from s2 and return, if it is empty, pop all elements from s1 and push them all on s2 and return the top.

How does it impact the performance? Well, it is true that if there is not element in s2, we have pop and push on s2, which has complexity of `O(n)`. HOwever, all subsequent pop operations are O(1), this is called amortized complexity of `O(1)`.

Empty()
Queue to be empty, there should not any element in either s1 or s2.

Peek()
If s2 is empty, then pop from s1 and push on to s2 and then return peek of s2.

```package com.company;

import java.util.Stack;

/**
* Created by sangar on 23.9.18.
*/
public class QueueWithStackOptimized {
private Stack<Integer> s1;
private Stack<Integer> s2;
private int front;

public QueueWithStackOptimized(){
s1 = new Stack<>();
s2 = new Stack<>();
}

public void push(int x){
if(s1.empty()) front = x;
s1.push(x);
}

public int pop(){
if(!s2.empty()) return s2.pop();
if(!s1.empty()) return -1;

while(!s1.empty()){
s2.push(s1.pop());
}
return s2.pop();
}

public boolean isEmpty(){
return s1.empty() && s2.empty();
}

public int peek(){
if(!s2.empty()) return s2.peek();

return front;
}
}
```

Complexity of peek function is again amortized to `O(1)`. Can you write test cases for implemented queue?

Reference : Leetcode

Please share if there is something wrong or missing. If you want to have personal coaching from our experienced coaches, please reach out to us at [email protected]

# Matching parenthesis problem

We understood the concept of stack data structure in last post. Let’s discuss matching parenthesis problemwhich applies those concept. Problem statement is :

Given a string of parenthesis ‘(‘ and ‘)’, write a function which returns true if there are matching pairs and false if there are not. A matching pair means, there should be a closing parenthesis for an opening one, in correct order.

For example : `'((()))'`, function should return `TRUE`, but `')(())'` will return `FALSE`. Special case would be when there are equal number of parenthesis, closing and opening, but they are not in perfect order, hence function should return false in that case.

## Parenthesis matching problem : Line of thoughts

For each closing parenthesis, we need a corresponding opening parenthesis. There are two possibilities : Either we find one or we do not find one. If we do not find one, we can say that string does not contain matching parenthesis.
If there is corresponding opening parenthesis, then that opening parenthesis cannot be matched with any other closing parenthesis.

Also, note that every closing parenthesis will match with the most recent opening parenthesis if there is one. That means we are looking at a order where the parenthesis which came last needs to be fetched first, typical last in first out pattern, which is best implemented by stack.

For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen. Next closing parenthesis should complete pair with the one prior to last and so on.

### Parenthesis matching problem : Algorithm

1. For each character of input string
2. If character is opening parenthesis `'('`, put it on stack.
3. If character is closing parenthesis `')'`
1. Check top of stack, if it is `'('` , pop and move to next character.
2. If it is not `'('`, return false
4. After scanning the entire string, check if stack is empty. If stack is empty, return true else return false.

### Matching parenthesis problem : Implementation

```package com.company;

import java.util.Stack;

/**
* Created by sangar on 21.9.18.
*/
public class ParenthesisMatch {

public static boolean isMatchingParenthesis(String s) {
Stack<Character> stack = new Stack<>();

if (s == null) return true;

int len = s.length();
for(int i=0; i<len; i++){
switch(s.charAt(i)){
case '(' :
stack.push(s.charAt(i));
break;
case ')':
//If stack is empty, then there is an extra closing parenthesis
if(stack.isEmpty()) return false;
stack.pop();
break;
default:
return false;
}
}
//If stack is empty that means it's a matching parenthesis
return stack.empty();
}

public static void main(String[] args) {
String s = "()))";
System.out.println(isMatchingParenthesis(s));
}
}
```

Complexity of parenthesis matching algorithm is `O(N)` time to scan N length string and `O(N)` extra space for stack.
This problem is quite simple to solve, so if you are asked this question in interview, most probably interviewer wants to understand can you think of good test cases and put your code to test against them. Below are the few test cases you can try your code on.
Test cases

```1. ((())) : True
2. ())) : False
3. )((( : False
4. ( : False
5 Empty string : True
6. NULL pointer : False
```

Can you try solving this problem now on HackerEarth

Please share if there is something wrong or missing. If you are interested to take personal coaching from our experience teachers, please reach out to us at [email protected]