Skip to main content
Lesson 39 - Queues
ZIPPDF (letter)
Lesson MenuPreviousNext
  
Implementing Queues as a Linked List page 5 of 8

  1. A queue can be implemented as an array or a linked list. If we use a linked list to implement a queue we must deal with the following issues.

  2. Two external pointers must be used to keep track of the front and end of the queue. When discussing a queue it is traditional to add new data at the end of the queue, as in "get in at the end of the line." The term enqueue is used to describe this operation.


    An Enqueue Operation - Inserting at the End


  3. Data will be removed from the "front" of the queue. This operation is called dequeue.


    A Dequeue Operation - Deletion from the Front


  4. A queue can be implemented as a singly linked list if the two external pointers are appropriately placed.

  5. When a new piece of data is added to the tail of the queue (enqueue), the external pointer last must be changed to point to the new node added to the list.

  6. When an old piece of data is extracted from the queue (dequeue), the external pointer first must be changed to point to the appropriate node after the data has been removed.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.