7 Abstract Data Types

When using Python, most often you are concerned about what built-in functions or data structures do, not how they work. That makes you a client.

Data Structure: a concrete strategy for storing some data. For example, list and dict. Concerned with "how?"

Abstract Data Type: defines some kind of data and the operations that can be performed on it. It is a pure interface with no mention of an implementation. Concerned with "what?," there is no 1:1 correspondence between ADTS and data structures in any language.

• Set
  • Data: a collection of unique elements
  • Operations: get size, insert a value (without introducing duplicates), remove a specified value, check membership
• Multiset
  • Data: a collection of elements (possibly with duplicates)
  • Operations: same as Set, but the insert operation allows duplicates
• List
  • Data: an ordered sequence of elements
  • Operations: access element by index, insert a value at a given index, remove a value at a given index
• Map
  • Data: a collection of key-value pairs, where each key is unique and associated with a single value
  • Operations: lookup a value for a given key, insert a new key-value pair, remove a key-value pair, update the value associated with a given key
• Iterable
  • Data: a collection of values (may or may not be unique)
  • Operations: iterate through the elements of the collection one at a time.

3.2 Stacks and Queues

The Stack ADT

It contains zero or more items. When you add an item, it goes to the top of the stack ("pushing" onto the stack). Items can also be removed from the top ("popping" from the stack). This is LIFO.

Methods:

• is_empty
• push
• pop

Queue ADT

It contains zero more items. Items come in and out in FIFO. Adding an item to is called an enqueue operation and removal of an item a dequeue operation.

Methods:

• is_empty
• enqueue
• dequeue