Lecture Notes for SE 598, Data Structures and Algorithms

28 June 2000, Implementing Dequeues

1. operations and behavior

   1. create - create a dequeue

   2. delete - delete a dequeue

   3. read - place a value in a dequeue

   4. write - retrieve a value from a dequeue

   5. grow - add a new element to the end of the dequeue

   6. shrink - delete an element from the end of the dequeue

   7. size - return the number of elements in a dequeue

2. design

   1. what data structures are best for implementing dequeues?

   2. how can the operations best be implemented?

   3. these questions are related

      1. the interesting point is that dequeues can grow and shrink from both ends

   4. use an array

      1. an array with two pointers, one to the front and one to the back

      2. creating and deleting is fast and simple

      3. reading and writing is fast and of slight complexity

      4. grow is slow and moderately complex, shrink is fast and slightly complex

         1. if array space exists, move an end pointer for new space

         2. for a linear array, shift contents to open up space

         3. for a circular array, not a problem

         4. for a full array, grow requires copying in either case

      5. size is fast and easy, possibly with an auxiliary variable

   5. use a linked list

      1. have a head with two pointers, one to the front and the other to the back

      2. creating is fast and simple, deleting is slow and simple

      3. reading and writing are slow and slightly complex

      4. grow and shrink are fast and simple

      5. size is fast and simple with an auxiliary variable

   6. combine linked lists and arrays

      1. use a linked list with an linear array index

      2. creating is fast and moderately complex, deleting is slow and simple

      3. reading and writing are fast and moderately complex

      4. grow is slightly slow and moderately complex, shrink is fast and simple

      5. size is fast and simple with an auxiliary variable

      6. grouping linked-list elements into arrays improves grow performance

   7. use two vectors

      1. each vector represents an end of the dequeue

      2. creating is fast and simple

      3. reading and writing are fast and slightly complex

      4. grow and shrink are fast and slightly complex

      5. size is fast and simple

This page last modified on 26 June 2000.