Data Structures - Abstract Data Types

Annotations:

• Queue is recursive data structure Items are added at the back of the queue
• FIFO Queue preserves order.
• We can only access the data from one place.
• Process the information in the same order they were received.

1. size
   1. O(1)
2. peek

   Annotations:

   • Return the last item, which is front most item in the Queue.
   • return self.items[-1]
   1. O(1)

      Annotations:

      • if self.items:     return self.items[-1]
3. is_empty

   Annotations:

   • return self.items == []
   • Returns a boolean value representing if the Queue is empty
   1. O(1)
4. enqueue

   Annotations:

   • -- insert the item at the 0th position
   1. O(n)

      Annotations:

      • The runtime is O(n) or linear time because inserting into the 0th index of the list enforces all the items to be pushed.
5. dequeue

   Annotations:

   • Returns and removes the front most item from the Queue
   • self.items.pop()
   1. O(1)

Annotations:

• LIFO

1. push
   1. O(1)
2. pop
   1. O(1)
3. peek

   Annotations:

   • Show us the next value which can be popped
   1. O(1)

      Annotations:

      • Indexing in the list is constant time
4. size

   Annotations:

   • Just use the length method of the list
   1. O(1)

      Annotations:

      • The method runs in constant time
5. is_empty
   1. O(1)

Annotations:

• Can add items to both ends.
• mutable and needs ordered collection of data structures. Can be implemented using list.
• limited access datatype
• If the string is palindrome. deque data structures is best.

1. add_front

   Annotations:

   • Inserting the items to the 0th position
   1. O(N)
2. add_rear

   Annotations:

   • Just append the item. Constant runt time as the items are added to the end.
   1. O(1)
3. remove_front

   Annotations:

   • Just use Lists builtin pop method and pass 0
   1. O(N)
4. remove_rear
   1. O(1)

      Annotations:

      • Just use the lists pop method without any argument
5. peek_front

   Annotations:

   • Return the item at list index 0th position.
   1. O(1)
6. size

   Annotations:

   • Return the length of self.items
   1. O(1)
   2. O(1)

      Annotations:

      • Just use the length fuction
7. is_empty
   1. O(1)
8. peek_rear

   Annotations:

   • return the item at -1 index for getting the last item from the list
   1. O(1)