Dequeue algorithm

Question

Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.

In my implementation I have maintained 4 pointers front1,rear1,front2,rear2.

Do you have any other algorithm with less pointers and O(1) complexity ? Please explain.

Answer 1

There are two common ways to implement a deque:

1. Doubly linked list: You implement a doubly linked list, and maintain pointers to the front and the end of the list. It is easy to both insert and remove the start/end of the linked list in O(1) time.
2. A circular dynamic array: In here, you have an array, which is treated as circular array (so elements in index=arr.length-1 and index=0 are regarded as adjacent).
   In this implementation you hold the index number of the "head", and the "tail". Adding element to the "head" is done to index head-1 (while moving the head backward), and adding element to the tail is done by writing it to index tail+1.
   This method is amortized O(1), and has better constants then the linked list implementation. However, it is not "strict worst case" O(1), since if the number of elements exceeds the size of the array, you need to reallocate a new array and move elements from the old one to the new one. This takes O(n) time (but needs to be done after at least O(n) operations), and thus it is O(1) amortized analysis, but can still fall to O(n) from time to time.