This has no particular code behind it. It\'s for my algorithms class. A deque (p

Question

This has no particular code behind it. It's for my algorithms class.

A deque (pronounced "deck") is like a queue, but one can insert and delete at either end -that is, one can insert/delete at both the head and the tail. The object of this problem is to implement a deque using three stacks, called Head, Tail, and Temp, in such a way that all insert/delete operations take amortized O(1) time (a) The two stacks Head and Tail contain, respectively, the front and rear elements of the deque. The tops of the stacks are the ends of the deque so they are accessible, while the bottom stack elements are the innermost of the deque. The four deque operations are insert/delete from the front and insert/delete from the rear. Describe the insert operations (b) The delete operations are simple if the corresponding stack is not empty-just pop the top element off the appropriate stack. But if the stack you need to pop from is empty, you need to get to the bottom element on the other stack. Explain how to do this using the Temp stack to split the contents of the non-empty stack into two halves so that Head and Tail contain, respectively, the front and rear elements of the deque (c) What is the worst-case cost of each of the four operations? (d) Using a potential function proportional to the absolute value of |Head - |Tail], show the amortizead time of the four operations is O(1). |Head and |Tail are, respectively, the numbers of elements on Head and Tail.

Explanation / Answer

(a) Assume, deque is empty. And we have two empty stacks Head and Tail. To insert an element in the front of deque, push that element in the Head stack, To insert an element in the rear of deque, push that element in the Tail stack. Like this, whenever we need to insert in the front, we have do perform push in the Head stack and whenever we need to insert in the rear, we have to perform push in the Tail stack.

(b) Assume |Head| =n and Tail is empty. We need to delete an element from rear of deque. Since Tail is empty, we need to get the bottom element of Head. Temp is empty now, pop first Floor(n/2) elements from Head one by one and push in to Temp. By doing so, first floor(n/2) front elements of deque will be placed in Temp in reverse order. Now the remaining (n-floor(n/2)) elements in Head will be poped one by one and will be pushed in to Tail. By doing so, the last (n-floor(n/2)) elements of deque will be placed in order, in Tail. Now, Head is empty and the floor(n/2) elements in Temp will be transformed to Head by pop and push operation like before. Now the elements will be placed in Head and Tail as asked in the question.

(c) The worst case cost of front and tail insert operations are O(1), whereas the delete operations are O(n).

(d) Obviously, the cost of insertion is O(1) and the delete operation depends on ||Head|-|Tail|| and for any n, this again give the cost O(1).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.