1.

We saw that

Queues

and Stacks

are quite similar.

One may ask a

natural

question

, how similar they are;

c

an you buil

d one of them from the other

?

It turns

out that, they can not be conver

ted to each other trivially.

In fact,

[1] shows that

(

i

) Simulating one stack by one queue requires

O

(n

4/3

log n)

time

and in the

opposite direction

(

ii

) Simulating one queue by one stack requires

O(n

2

) time.

Howev

er, following questions are attackable.

(a)

I

mplement a queue from two stacks and O(1) extra storage.

(b)

I

mplement a stack from two queues and O(1) extra storage.

2

.

Priority Queues

:

(a) Build a priority queue using arrays.

(b) Build a priority queue using linked lists.

3

.

Binary heap

:

(a)

Bui

ld a

binary heap

using arrays (i.e. implement max and insert functions

which need heap

-

up and heap down operations)

.

(b) Build a binary heap using trees

.

(c) Design and implement an algorithm that has O(log

n

)

complexity for all max,

min and insert functions.