By the end of this lesson, you should be able to:
In this Lesson, we discuss in detail the linked Queue data structure and more approaches to manipulating linked data structure nodes.
A linked Queue is a linear linked data structure, as each node in a Queue links to one other node. We must keep track of both the first and last nodes in a Queue, and call them the front and rear nodes.
Figure 1 displays the workings of the linked Queue. Use and to see how it works:
_Queue_Node Class
Other than its name, the _Queue_Node class is identical to the _Stack_Node class.
A linked Queue is initialized with:
__init__ Method
class Queue:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty queue. Values are stored in a
linked structure.
Use: queue = Queue()
-------------------------------------------------------
Returns:
a new Queue object (Queue)
-------------------------------------------------------
"""
self._front = None
self._rear = None
self._count = 0
The queue initialization is simple: the private attribute _front
points to the first _Queue_Node in the queue, the private attribute _rear
points to the last _Queue_Node in the queue, and the private attribute _size
keeps track of the number of nodes in the queue. (Defining the is_empty
and __len__ methods is trivial and left as an exercise to
the student.)
insert Method
insert Method
def insert(self, value):
"""
-------------------------------------------------------
Inserts a copy of value into the queue.
Use: queue.insert(value)
-------------------------------------------------------
Parameters:
value - a data element (?)
Returns:
a copy of value is added to the rear of queue.
-------------------------------------------------------
"""
node = _Queue_Node(value, None)
if self._front is None:
self._front = node
else:
self._rear._next = node
self._rear = node
self._count += 1
return
When inserting a node into a Queue, the node is added after the rear
node of the Queue. insert creates a new _Queue_Node object
and adds a value to it. The _next link of the new node is
always set to point to None, as there are no nodes
following it. The old rear node is set to point to the new rear node,
and the _rear link is updated accordingly. The front link
is changed only if the queue is empty.
remove Method
Removing a node from a linked queue means extracting the value from the front node then removing that node from the Queue. The Queue's front link must now point to the next node in the Queue. This is easy: get the current front node's link to its next node by referring to its next node attribute, then make that node the new front. The Queue count must be explicitly updated as well.
Writing this method is left as an exercise for the student.
Previously we looked at combining the contents of two Stacks by Moving Nodes Between Stacks. As noted there, we
moved the top nodes one at a time because we were alternating the
contents of the source Stacks into the target Stack. What if we simply
wanted to append the contents of one data structure to another? This
isn't easily possible with Stacks because we don't immediately know
where the bottom of a Stack is. We do, however, know exactly where the
rear of a linked Queue is through the _rear attribute.
Figure 1 displays appending one linked Queue to the end of another. Use and to see how it works:
The analogy we can use here is that of connecting two chains together. To turn two chains into a longer chain, we don't have to break each link off the second chain and add them one by one to the end of the first chain - all we have to do is to connect the last link of the first chain to the first link of the second chain, and we now have a new, complete, longer chain.
Note that we can also move individual nodes from the front of one Queue
to the rear of another, or from the front of one Queue to the front of
another, in a way very similar to Moving Nodes Between
Stacks. We could call these private helper methods _move_front_to_rear
and _move_front_to_front.
Implement and test the _move_front_to_rear and _move_front_to_front
methods for a linked Queue.
We often need to traverse, or walk through, a linked structure. To print the contents of a linked structure, for example, we start at the top, or the front, as appropriate, and we visit every node until there are no nodes left to visit. We may also want to traverse a linked structure in order to find a node, to count nodes, or to insert a node in the proper place in a sorted list. (Note that we can traverse a linked structure using either iteration or recursion. We will use only iteration in these examples and examine recursion later.)
Printing the contents of a linked structure is the simplest version of traversing a linked structure. In this example we will traverse the contents of a linked Queue.
We first have to decide which end of the Queue to start from. If we start from the rear of the Queue we won't get far, simply because the rear node does not link to any other node - we have nowhere to go. The front node links to the next node, which in turn links to the next node, and so on. Clearly, this is where to start. (With the Stack we must start from the top node as there is no other way into the linked structure.)
We want to make sure that we do not change the linked structure in any way, so we must leave the front and rear links alone. We can, however, set a temporary link to point to the front node, and change that temporary link as we go.
The sample print method prints the contents of a Queue from
front to rear. Code Listing 1 gives this method. The actual code is
quite simple:
print Method
def print(self):
"""
-------------------------------------------------------
Prints the contents of Queue from front to rear.
Use: q.print()
-------------------------------------------------------
Returns:
None
-------------------------------------------------------
"""
curr = self._front
while curr is not None:
print(curr._value)
curr = curr._next
return
The code itself is quite simple. The variable curr (short
for current as it is referring to the 'current' node being
processed) is the name given to the temporary link used to traverse the
linked Queue. At each step in the traversal, the print
method prints the contents of the current node, then moves onto the next
node by referencing the current node's next node link. When curr
is None, the end of the Queue has been found.
Use and to see how it works:
In this Lesson, we introduced the linked Queue data structure and saw how it differed from a linked Stack with attributes for the front, rear, an count. We also discussed how to link two data structures together in \(O(1)\) time, and how to traverse a linked data structure.