Category Archives: Queue

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?

For example consider the array

A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]

This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.

This algorithm takes O(n) time.

Here is the C++ code.

Problem Source: SPOJ REPROAD

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();
}
}
}