1. We saw that Queues and Stacks are quite similar. One may ask a natural questi
ID: 3725641 • Letter: 1
Question
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.
Explanation / Answer
Please find my naswer for Q1.
Please repost oters in separate post.
(a)
Implement a queue from two stacks and O(1) extra storage.
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
(b)
Implement a stack from two queues and O(1) extra storage.
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.
push(s, x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.