Data structure - Stacks and Queues

STACKS & QUEUES

Inner class –

private class Node

{

                Employee item;

                Node next;

}

Stack Implementation : LinkedList vs Resizing array

LinkedList –

Pros – Every operation takes constant time in the worst case.

Cons – Uses extra time + space to deal with links (pointers).

Resizing Array –

Pros – Less wasted space.

Cons – Every operation takes constant AMORTIZED time.

One of the practical application of stack – To evaluate expression.

Technique – Dijkstra’s 2-stack algorithm.

Steps –

1)      Put values in one stack, operands in the other.

2)      Ignore ( i.e left parenthesis.

3)      For ) i.e. right parenthesis, pop 2 values from the value stack, pop operand from the operand stack, do the operation and put the output back (push) to the value stack.

Example – Evaluate :   (1 + 2) * ((3 – 1) + (4 * 5))

How a make a Queue using 2 stacks ?

1)      Create two stacks s-main and s-temp.

2)      For every enqueue operation, do push on s-main.

3)      For every dequeue operation, do the following –

a.       (n – 1) pop on s-main and (n – 1) push to s-temp.

b.      pop on s-main to the get the OUTPUT.

c.       (n – 1) pop on s-temp and (n – 1) push back to s-main.

Practical applications of Priority queues (implemented using binary heaps)

Requirement 1 – Find the largest M items out of the total of stream of N items. (example – Fraud detection: Isolate $$$ transactions, File maintenance: find top k largest files/ directories.

Requirement 2 – Not enough space to store all N items (otherwise we could have stored them all and sorted in NlogN time).

To solve problems while satisfying Requirement 1 and 2 above, PRIORITY QUEUES are the best.

For more details on heaps, look - http://lazynreclined.blogspot.in/2016/09/algorithms-heaps.html