Computer science as an area of study comprises everything necessary for the design, construction, and use of computers.

We'll focus on one area of theoretical computer science, algorithms and data structures, and begin with abstract data types.

• Familiarity with a high-level programming language implementing dynamic arrays.

By the end of this, developers should be able to:

• Define abstract data type (ADT).
• Create stacks and queues from dynamic arrays.

1. Fork and clone this repository.

An ADT is a type defined by what it does, rather than how it is implemented. Specific implementations have limitations not found in the ADT and must be able to create instances of the type.

A stack implements a last in, first out data store (LIFO).

Stack operations:

• empty? - check to see if there are any items on a stack.
• push - add an item onto the top of a stack.
• pop - remove and return an item from the top of a stack.

Visualizing stack implementations:

• As an array.
• As a list.

A queue implements a first in, first out data store (FIFO).

Queue operations:

• empty? - check to see if there are any items in a queue.
• enqueue - add an item to the tail of a queue.
• dequeue - remove an item from the head of a queue.

Visualizing queue implementations:

• As an array
• As a list

In languages that have a "nothing" type, nil in Ruby, undefined in JavaScript, or None in Python, empty? need not be implemented. Instead, check for that type when calling pop or dequeue.

List operations:

• empty? - check to see if there are any items in a list.
• first - return the item at the head of a list.
• rest - return the tail of a list - the list comprised of all elements except the head (the element containing the item returned by first).
• prepend - create a one element list and add the existing head as its tail.
• delete - replace a list with rest, removing the head.

In your squads, discuss implementing these operations using an array.

What if this theoretical array type only provided index based access to elements (i.e. the [] operator) and required explicit allocation of space for elements? Would this change your implementation significantly? How would you handle adding an item to a "full" array?

• Data Structure Visualizations.

1. All content is licensed under a CC­BY­NC­SA 4.0 license.
2. All software code is licensed under GNU GPLv3. For commercial use or alternative licensing, please contact [email protected].