Skip to main content
Engineering LibreTexts

3.3: Queues

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    A queue is a basic data structure that is used throughout programming. You can think of it as a line in a grocery store. The first one in the line is the first one to be served.Just like a queue.

    A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.

    Queue<item-type> Operations


    Adds an item onto the end of the queue.


    Returns the item at the front of the queue.


    Removes the item from the front of the queue.


    True if no more items can be dequeued and there is no front item.


    True if no more items can be enqueued.


    Returns the number of elements in the queue.

    All operations except get-size() can be performed in \({\displaystyle O(1)}\) time. get-size() runs in at worst \({\displaystyle O(N).}\)

    Linked List Implementation

    The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue.

    type Queue<item_type>
      data list:Singly Linked List<item_type>
      data tail:List Iterator<item_type>
        list := new Singly-Linked-List()
        tail := list.get-begin() # null
      end constructor

    When you want to enqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything

     method enqueue(new_item:item_type)
       if is-empty()
         tail := list.get-begin()
         list.insert_after(new_item, tail)
       end if
     end method

    The front item on the queue is just the one referred to by the linked list's head pointer

      method front():item_type
        return list.get-begin().get-value()
      end method

    When you want to dequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator.

      method dequeue()
        if is-empty()
          tail := list.get-begin()
        end if
      end method

    A check for emptiness is easy. Just check if the list is empty.

      method is-empty():Boolean
      end method

    A check for full is simple. Linked lists are considered to be limitless in size.

      method is-full():Boolean
        return False
      end method

    A check for the size is again passed through to the list.

      method get-size():Integer
        return list.get-size()
      end method
    end type

    Performance Analysis

    In a linked list, accessing the first element is an \({\displaystyle O(1)}\) operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick \({\displaystyle O(1)}\) operations.

    The checks for empty/fullness as done here are also \({\displaystyle O(1)}\).

    The performance of getSize() depends on the performance of the corresponding operation in the linked list implementation. It could be either \({\displaystyle O(n)}\), or \({\displaystyle O(1)}\), depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

    • Queue (Wikipedia)

    3.3: Queues is shared under a CC BY-SA license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?