CS201 Study Guide

Unit 2: Introduction to Stacks and Queues

2a. Recognize and visualize stacks and queues

  1. What is a stack?
  2. What is a queue?
  3. What is the essential difference between stacks and queues?
  4. Recognize diagrams that illustrate stacks and queues.
  5. Be able to modify a stack ADT so that it functions like a queue.

We mentioned lists earlier. That discussion continues in this unit; see pages 96-99 of this book. Lists form the foundation of stacks and queues. There is only a subtle difference between stacks and queues. Both add newly-arriving elements to the same end of the list. However, the stack processes the most recently-added element. It removes the element from the end of the list to which elements are added. Queues, on the other hand, remove elements from the other end of the list from which elements are added. In this way, stacks process the element that has been on the list the least amount of time (last-in/first-out, LIFO). Queues process the element that has been on the list the longest amount of time (first-in/first-out, FIFO). Thus, code that implements either abstract data type can be easily modified to implement the other type. Stacks can be easily modified to function as queues and vice versa.

 

2b. Solve software requirements that require stacks or queues

  1. What are the various means of implementing stacks and queues?
  2. How do an application's requirements lead to the selection of stack or queue ADTs?
  3. What are the various means of implementing lists?
  4. How can a vector be implemented as a linked-list?
  5. What should one look for to tell if an ADT's code implements a stack or queue?

Stacks are most commonly implemented using linked-lists (as shown on pages 120-127 of this book), as are queues (pages 127-144). There are means of implementing stacks using arrays that can be readily modified to act as queues. Understanding which applications are suitable for stacks and which are suitable for queues will help you see the practical side of these two abstract data types.

 

Unit 2 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included.

  • stack
  • queue
  • list
  • linked-list
  • array
  • push
  • pop
  • element
  • object
  • peek
  • buffer
  • rotate
  • head
  • tail
  • empty
  • insert
  • LIFO
  • FIFO
  • linear data structure
  • sequential access
  • top element
  • bottom element
  • circular list
  • list overflow