.. _QueueLinked:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "QueueLinked";ODSA.SETTINGS.MODULE_LONG_NAME = "Linked Queues";ODSA.SETTINGS.MODULE_CHAPTER = "Linear Structures"; ODSA.SETTINGS.BUILD_DATE = "2016-11-25 11:27:02"; 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:


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

.. avmetadata:: 
   :author: Cliff Shaffer
   :requires: queue
   :satisfies: linked queue
   :topic: Lists

.. odsalink:: AV/List/lqueueCON.css   

Linked Queues
=============

Linked Queues
-------------

The linked queue implementation is a straightforward adaptation
of the linked list.
Here is the linked queue class declaration.

.. codeinclude:: Lists/LQueue
   :tag: LQueue1,LQueue2

|

.. inlineav:: lqueueIntroCON ss
   :long_name: Linked Queue Intro
   :points: 0.0
   :required: False
   :threshold: 1.0
   :output: show    
   
|

.. inlineav:: lqueueEnqueueCON ss
   :long_name: Linked Queue Enqueue
   :points: 0.0
   :required: False
   :threshold: 1.0
   :output: show   
   
.. avembed:: Exercises/List/LqueueEnqueuePRO.html ka
   :module: QueueLinked
   :long_name: Linked Queue Enqueue Exercise
   :points: 1.0
   :required: True
   :threshold: 5.0
   :exer_opts: JXOP-debug=true&amp;JOP-lang=en&amp;JXOP-code=java


Linked Dequeue
--------------

.. inlineav:: lqueueDequeueCON ss
   :long_name: Linked Queue Dequeue
   :points: 0.0
   :required: False
   :threshold: 1.0
   :output: show 
   
.. avembed:: Exercises/List/LqueueDequeuePRO.html ka
   :module: QueueLinked
   :long_name: Linked Queue Dequeue Exercise
   :points: 1.0
   :required: True
   :threshold: 5.0
   :exer_opts: JXOP-debug=true&amp;JOP-lang=en&amp;JXOP-code=java


Comparison of Array-Based and Linked Queues
-------------------------------------------

All member functions for both the array-based and linked queue
implementations require constant time.
The space comparison issues are the same as for the equivalent stack
implementations.
Unlike the array-based stack implementation, there is no convenient
way to store two queues in the same array,
unless items are always transferred directly from one queue to the other.

Stack and Queue Summary Questions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. avembed:: Exercises/List/StackQSumm.html ka
   :module: QueueLinked
   :long_name: Stack/Queue Summary Exercise
   :points: 1.0
   :required: True
   :threshold: 5.0
   :exer_opts: JXOP-debug=true&amp;JOP-lang=en&amp;JXOP-code=java


.. odsascript:: AV/List/llist.js
.. odsascript:: AV/List/lqueueIntroCON.js
.. odsascript:: AV/List/lqueueEnqueueCON.js
.. odsascript:: AV/List/lqueueDequeueCON.js