CIS 250 - Stacks and queues

These topics are covered in detail in the text, so these notes won't bother reiterating them. The class session will discuss some topics in detail, and then illustrate their implementation with some of the programs listed on this page. If you don't have the text, then you can get most of the details of the data structures we will be discussing using Wikipedia:

• Wikipedia article on linked lists
• Wikipedia article on stacks
• Wikipedia article on queues
• Wikipedia article on recursion

Objectives

• use stacks to store and retrieve data
• use queues to store and retrieve data
• use templating to make linked lists, stacks, and queues more general
• use dynamic memory allocation to make data structures more memory efficient

Templates, Stacks, Queues, Deques

• note: linked lists may not have a particular removal order
• note: stacks are LIFO (last in, first out data structures)
• note: queues are FIFO (first in, first out data structures)
• Templated linked lists:
  • MyObj.h: simple class used for filling tlist
  • tlist.h: implementation of templated linked list class using dynamic memory allocation
  • TestTList.cpp: test driver for tlist.h
  • gll.h: implementation of templated linked list class using reference variables
  • testgll.cpp: test driver for gll.h
• Stack: stack.h       TestStack1.cpp
• Stack with templating: stackt.h       TestStack2.cpp
• Stack with dynamic allocation and templating: stackd.h       TestStack3.cpp
• Queue with dynamic allocation and templating: queued.h       TestQueue3.cpp