.. _StackQueue:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "StackQueue";ODSA.SETTINGS.MODULE_LONG_NAME = "Stacks and Queues";ODSA.SETTINGS.MODULE_CHAPTER = "Lists, Stacks, and Queues"; ODSA.SETTINGS.BUILD_DATE = "2020-08-23 13:21:52"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:



.. odsalink:: AV/List/aqueueCON.css
.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer


=================
Stacks and Queues
=================

Container Class Design Issues
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   * Storing a record vs. Storing a reference to a record
   * Homogeneity: Allow different record types? Check and block?
   * Deletion: What happens to the record?


Stacks
~~~~~~
   LIFO: Last In, First Out.

   Restricted form of list: Insert and remove only at front of list.

   Notation:

   * Insert: PUSH
   * Remove: POP
   * The accessible element is called TOP.


Stack ADT
~~~~~~~~~
   .. codeinclude:: Lists/Stack
      :tag: Stack


Array-Based Stack (1)
~~~~~~~~~~~~~~~~~~~~~
   Issues:

   * Which end is the top?
   * Where does “top” point to?
   * What are the costs of the operations?


Array-Based Stack (2)
~~~~~~~~~~~~~~~~~~~~~
   .. codeinclude:: Lists/AStack
      :tag: AStack1


Linked Stack
~~~~~~~~~~~~
   .. codeinclude:: Lists/LStack
      :tag: LStack1

   What are the costs of the operations?


   How do space requirements compare to the array-based stack
   implementation?


Queues
~~~~~~
   FIFO: First in, First Out

   Restricted form of list: Insert at one end, remove from the other.

   Notation:

   * Insert: Enqueue
   * Delete: Dequeue
   * First element: Front
   * Last element: Rear


Queue Implementation (1)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueFirstCON ss
      :long_name: Array-based Queue Positions Slideshow
      :output: show


Queue Implementation (2)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueDriftCON ss
      :long_name: Array-based Queue Drift Slideshow
      :output: show


Queue Implementation (3)
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueBadCON ss
      :long_name: Array-based Queue Bad Representation Slideshow
      :output: show


Circular Queue (1)
~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueCircularCON ss
      :long_name: Circular Array-based Queue Slideshow
      :output: show


Circular Queue (2)
~~~~~~~~~~~~~~~~~~
   .. inlineav:: aqueueEmptyCON ss
      :long_name: Empty Circular Array-based Queue Slideshow
      :output: show

.. odsascript:: AV/List/aqueueFirstCON.js
.. odsascript:: AV/List/aqueueDriftCON.js
.. odsascript:: AV/List/aqueueBadCON.js
.. odsascript:: DataStructures/CircularQueue.js
.. odsascript:: AV/List/aqueueCircularCON.js
.. odsascript:: AV/List/aqueueEmptyCON.js