stacks_queues_sets_handout.md

CUNY Tech Prep 2016-2017

Lab 2 Handout: Stacks, Queues, and Sets

Definitions

• Stacks
  • are an abstract data type that serves as an ordered collection of elements. It provides two primary operations, push(x) to insert elements into the collection, and pop() to remove the most recently inserted element from the collection. This a LIFO (Last In, First Out) collection data type.
• Queues
  • are an abstract data type that serves as an ordered collection of elements. It provides two primary operations, add(x) to insert elements into the collection, and remove() to remove the first-most inserted element from the collection. This a FIFO (First In, First Out) collection data type.
• Sets
  • are an abstract data type that serves as an unordered collection of elements. It provides two primary operations, add(x) to insert elements into the collection, and remove(x) to remove specific elements. The collection keeps only unique element values, discarding duplicate entries.

Review Materials

Videos:

• Stacks and Queues, by DerekBanas (16min)
• Stacks and Queues, by BlondieBytes (27min)

Textbook:

• Stacks, Queues, and Deques
• Basic Sets
• Stacks and Queues

Additional Resources:

• Test your knowledge, including Big-O

Questions to consider

• When do you use a Stack vs a Queue?
• Stacks and Queues are simply interfaces to abstract concepts. Both Stacks and Queues can be implemented with either Arrays or LinkedLists. In each case, there are pros and cons. For each, the stack and queue, compare the pros and cons of implementing it with Arrays vs LinkedLists.
• What are the different ways we can implement a Set?