0

With an array based deque why is add and remove from the front ammortized O(1)? It would make sense to me that it would always be O(n) because either operation would mean that the current values of the array would need to be "moved" over to the the right of the 0 index to add and over to the left to remove...

My professor says that you don't need to shift, just update hi and lo. I'm not entirely sure what he means.

This is not a C++ question per se, but I am trying to understand it in this language.

ohbrobig
  • 939
  • 2
  • 13
  • 34
  • I assume that it just moves the pointer to the "front" and "back" to different places in the array. This changes the logical structure of the queue without having to actually shuffle around everything inside it. – Weak to Enuma Elish Nov 22 '15 at 01:48

2 Answers2

1

You have 2 pointers (hi and lo) that point to each end of the deque :

"aaaaa" <- hi
"bbbbb"
"ccccc"
"ddddd"<- lo

Then when you pop from one end or the other, you simply return what the pointer is pointing to and change the pointer to point to next/prev:

 //"aaaa" is still in the array but not considered part of the deque
 "bbbbb" <- hi
 "ccccc"
 "ddddd" <- lo

Much simplified example:

class Deque {
int deque[10];
int hi, lo;   // Initialize in constructor to -1 to flag deque is empty

public:
void push_front(int x) {
    // First time, add to middle of array
    if (-1 == lo) {
        hi = lo = 5; // Since array size is 10;
        deque[5] = x;
    }
    // Shift required?
    else if (lo == 0) {
        // Check if deque is full
        if (9 == hi) {
             // return error or get more space
        }
        else {
             // Shift by one
             // More optimally you would shift enough to move data to center of array
             for (int i = hi; i >= lo; --i) {
                 deque[i + 1] = deque[i];
             }
             // Update hi
             hi += 1;
             // Store in lo - lo remains at 0
             deque[0] = x;
         }
     }
     // No shift required
     else {
         deque[--lo] = x;
     }
 }
 // TODO: push_back, pop_front, pop_back
001
  • 13,291
  • 5
  • 35
  • 66
  • damnit, i should have realized it uses pointers. ok, that makes sense now. but if you add to front don't you still have to move/shift items? – ohbrobig Nov 22 '15 at 01:54
  • Yes, shifting would occur when adding, but only when you run out of space at either end. – 001 Nov 22 '15 at 01:56
  • Lets say you created this deque: {3, 5, 10, 12}, then did five addfronts. (Dont worry about size/space). Wouldn't each addfront mean you would have to shift, and after each addfront the lo would refer to the new value? – ohbrobig Nov 22 '15 at 02:00
  • It depends. Ex: your array is big enough to hold 100 numbers and the 3 in your example is at `array[50]`, and 12 is at `array[53]`. Then your 5 addfronts would not require any shifting. – 001 Nov 22 '15 at 02:05
  • @ohbrobig when you allocate a new memory block, you copy the old elements to the *middle* of the block instead of the beginning. Then you can add to the front or the back without shifting, until you bump into a boundary again. – Mark Ransom Nov 22 '15 at 02:10
  • Also, I just want to clarify: it doesn't have to be a pointer (`int *x`). Since you are using an array, `hi` and `lo` can be integer indices into the array. – 001 Nov 22 '15 at 02:18
  • @MarkRansom Is there a C++ implementation viewable somewhere? this is logical, I just want to know how they copy to the "middle" – ohbrobig Nov 22 '15 at 02:30
  • @ohbrobig I added an example. It's incomplete and off the top of my head, but hopefully it will clarify. – 001 Nov 22 '15 at 02:51
  • @ohbrobig the C++ definition of `std::deque` has additional constraints that make it more complicated to implement, so that won't work as an example. I'm unaware of any others. But is it really that confusing to copy one start/end sequence to another of the same size with an arbitrary offset? – Mark Ransom Nov 22 '15 at 03:28
0

I do not understand the exact C++ implementation of a deque, but here's my best attempt to rationalize your professor's claims about the time complexity:

From cppreference and cplusplus, it seems that deques are stored non-contiguously.

Here is another StackOverflow question that provides a helpful image and some enriching information.

Note how the start simply points to the front, but how it is also possible to have unused portions of the separate chunks. So perhaps it's not necessary to move everything when popping the front, if we can simply mark the old front as 'unused', and somewhat similarly for the back.

EDIT: My guess is that because there is unusued portions at the beginning and end, it is relatively easy to add to the front or the back, until, as John said in his own answer, you run out of room/'hit a boundary'.

Community
  • 1
  • 1
Kelvin Lee
  • 65
  • 8
  • `std::deque` is required to be non-contiguous because it has constraints on iterator invalidation and such. It's not strictly necessary for amortized O(1) insertion at either end. – Mark Ransom Nov 22 '15 at 03:31
  • I tried to research what you meant by 'iterator invalidation' as I'm not familiar with the term. Based on what I tried to research, I assume that these 'constraints' are because of the characteristics of a deque (only able to pop/push the front/back). Is that true? On top of that, I don't understand why 'constraints on iterator invalidation' would require 'non-contiguous' storage. Could you help explain this requirement? – Kelvin Lee Nov 22 '15 at 06:14
  • I was wrong, iterators are allowed to be invalidated on insertion but references aren't. This means that each element needs to stay at its original memory location, it can't be moved as the size of the `deque` increases - this is why it must be non-contiguous. Compare to `vector` where references get invalidated whenever the container changes size. See http://stackoverflow.com/questions/6438086/iterator-invalidation-rules for the rules. – Mark Ransom Nov 22 '15 at 15:30
  • Thank you for the extra link. I will continue researching with the points you have provided in mind [: – Kelvin Lee Nov 22 '15 at 19:04