CS201 Study Guide

Unit 5: Linked Stacks, Queues, and Lists

5a. Show how lists, stacks, and queues are used to implement specific requirements

  1. What is a linked-list?
  2. How does a linked-list differ from a vector list?
  3. In what way does list implementation impact the list's abstract functionality?
  4. What is the basic functionality that has to be added to a list to create a queue?
  5. What is the basic functionality that has to be added to a list to create a stack?
  6. What are requirements specifically suitable for stacks?
  7. What are requirements specifically suitable for queues?

We continue our discussion of linked-lists on pages 103-120 of this book. Linked stacks and queues are built from linked-lists. Nodes (objects, elements) are the linked components that point to each other within linked-lists, as described in this article. Nodes are formed from structures or classes as objects. The objects generally contain pointers to other objects of the same class. However, it is not necessarily the case that all nodes of a linked-list are of the same class. Keep that generalization of the concept behind linked-lists in mind.


5b. Construct software to employ lists, stacks, and queues within larger applications

  1. What are singly-linked-lists?
  2. What are doubly-linked-lists?
  3. How does a singly-linked-list differ from a doubly-linked-list?
  4. If a stack or queue were implemented as a doubly-linked-list, what might its advantages be?
  5. What are applications within which stacks could be employed?
  6. What are applications within which queues could be employed?

Begin your review by exploring singly-linked and doubly-linked-lists. Selecting the particular implementation within applications is important since it is not unusual for the basic stack and queue functionalities to be insufficient. Be sure you understand linked stacks on pages 123-125 of this book, and their implementation, as described in this article. The same goes for linked queues (on page 133) and their implementation, as described here. Examine, build, and run these code examples using your favorite IDE.


Unit 5 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.

  • pointer
  • linked-list
  • singly-linked
  • doubly-linked
  • stack
  • queue
  • dynamic memory allocation
  • pointer to next
  • pointer to previous
  • head
  • current
  • tail
  • push
  • pop
  • insert
  • LIFO
  • FIFO