Implementing stack using queues and vice versa

To implement stack using queues, with two cases : constant insertion time, linear removal time and vice-a-versa, see this stack overflow discussion

To implement a queue using two stacks,

// Basic solution
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( !s1.empty() ) s1.push(t);
        else  s2.push(t);
    }

    T dequeue()
    {
        T t;
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        return __dequeue(s1,s2);
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

// optimized solution : by saving the last operation
class Queue
{
    Stack s1; // used as main stack
    Stack s2; // used as stack for temp storage
    
    enqueue(T& t)
    {
        if ( last_operation == Dequeue ) 
            move( s2,s1);
        s1.push(t);
        last_operation = Enqueue;
    }

    T dequeue()
    {
        if ( s1.isEmpty() && s2.isEmpty() ) throw Exception();
        // if the last operation was dequeue, the required element
        // is already on the temp usage stack s2
        if ( last_operation == Dequeue )
            return s2.pop();

        T t= __dequeue(s1,s2);
        last_operation = Dequeue;
    }
    T __dequeue(Stack& from, Stack& to) 
    {
        size_t n = from.count();
        if (!n) return __dequeue(to, from);
        move(from, to, n-1);
        t = from.pop();
        move(to, from, n-1);
        return t;
    }
}

Also there is a interesting solution in Algorithms and Programming: Problems and Solutions - Page 90

We maintain the following invariant relation: stacks whose bottoms are
put together, form the queue. (In other words, listing all elements of one stack from
top to bottom and then of the other stack from bottom to top, we list all the queue
elements in the proper order.) To add an element to the queue, it is enough to add it to
one of the stacks. To check if the queue is empty, we must check that both stacks are
empty. When taking the first element from the queue, we should distinguish between
two cases. If the stack that contains the first element is not empty, there is no problem.
If that stack is empty, the required element is buried under all the elements of the
second stack. In this case, we move all the elements one-by-one onto the first stack
(their ordering is reversed) and return to the first case.
The number of operations for this step is not limited by any constant. However,
the requirement posed in the problem is still met. Indeed, any element of the queue
can participate in such a process at most once during its presence in the queue.

Binary Search of a string

Interesting problem : How can we apply binary search to search a string in a big word file?

We use a suffix array and sort this array. Once sorted, we apply binary search on this array. See Bentley Programming Pearls p.172. See also : Large-scale genome sequence processing By Masahiro Kasahara, Shinichi Morishita, p.56

We can optimize this even further by storing the radix representation of strings (see:Cormen's section in Hashing) and the problem will be reduced to binary search of numbers.

distance problem

A turnpike consists of n-1 stretches of road between n toll stations; Each stretch has an associated cost of travel. It is trivial to tell the cost of going between any 2 stations in O(n) time using only an array of the costs, or in constant time using a table of O(n^2) entries. Describe a data structure that requires O(n) space but allows the cost of any route to be computed in constant time.

Answer:

|------|-----|-----|-----|--------|
   a      b     c     d       e

An entry i in an array stores the sum of distance from the start of all stations <=i

i.e
distance[1] = a;
distance[2] = a+b;
distance[3] = a+b+c; 
and so on,

So distance between any two given stations i and j, distance[j] - distance[i]

Combinations of Brackets

Develop an algorithm to find out all valid combinations of n brackets. Like for n =3 possible combinations can be ((())) or ()()() or (()()) and so on.
Answer:

Use a stack. 
while( not end of input )
{
  ch = input character
  if ( ch is '(' ) then push it to stack.
  else pop from stack., and if the poped item is not '(' then error.
}
The stack should be empty now.

Merge unsorted linked lists

Write the algorithm to merge two unsorted linked lists.

Answer:^[1]

The bucket sort will give the best performance.

Add both the linked lists to a bucket data structure and then its simple to perform the bucket sort.

The complexity depends on the input values and how well they can be uniformly distributed among the buckets.

Implement a Queue using two stacks.

Write and algorithm to implement a Queue using 2 Stacks.

Answer:

class Queue
{
    private:
        Stack s[2];
    public:
        Enqueue(T item)
        {
            if ( last operation was enqueue )
            {
                S[1].push(s[0].pop());
                s[0].push(item);
            }
            else
            {
                while( !s[0].isempty() )
                {
                    s[1].push( s[0].pop() );
                }
                s[0].push(item);
            }
        }

        Dequeue()
        {
            if( last operation was dequeue)
            {
                return s[0].pop();
            }
            else
            {
                while(!s[1].isempty())
                {
                    s[0].push( s[1].pop() );
                }
                return s[0].pop();
            }
        }

};

Data structure for elements of 0 - N-1

Propose a data structure for the following:
- The data structure would hold elements from 0 to N-1.
There is no order on the elements (no ascending/descending order
requirement)

The complexity of the operations should be as follows:
* Initialization - O(1)
* Insertion of an element - O(1)
* Deletion of an element - O(1)
* Finding a element - O(1)
* Deleting all elements - O(1)

answer:

use an array (dynamically alloced) of size n.
and array[n] will indicate the count of an element.

Heap problem

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Solution:

The Heap has n elements,

n n-1 n-2 .....k....3 2 1
               ^^^^^^^^^^
               The Kth largest element happens somewhere in this range, 
               because it is a heap, and every parent >= child.

Possible solution, copy the last k elements to the temporary structure,
and build a heap which will take O(k) time and compare the root with the number x.

Reverse a Stack using Recursion

Write a Code to reverse a stack using recursion.

Answer:

template <typename T>
void ReverseStack(Stack s)
{
    if ( s.isEmpty() )
        return; // nothing to do
    else
    {
        T elem = s.Top();
        s.Pop();
        ReverseStack(s);
        s.Push(elem);
    }
}

Finding the Minimum element of a stack in O(1) time

Write the algo to return the Minimum element of a stack in O(1) time.

Answer:


Along with the normal stack, use another stack called the min stack.
The top of the min stack is ensured to have the min element as follows.
The elements are added to the min stack as follows:
During Push:
1. If the min stack is empty, then push the element that is being pushed into regular stack.
2. If the min stack is not empty, then if the element being pushed is <= MinStack.Top(), then push the element to MinStack.
During Pop:
3. If the element being popped from the normal stack is < element on min stack, then pop the element from min stack as well, or else leave the min stack untouched.

Ex: 6  8  2 3 7 1 9

After Push:

Regular stack:
6 8 2 3 7 1 9
Min Stack:
6 2 1

After Poping 9:
Regular stack:
6 8 2 3 7 1
Min Stack:
6 2 1

After Poping 1:
Regular stack:
6 8 2 3 7
Min Stack:
6 2

After Poping 3 , 7:
Regular stack:
6 8 2
Min Stack:
6 2

After Poping 2:
Regular stack:
6 8
Min Stack:
6

:
:
:
:
so on