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
