PYTHON

7.7 Our CircularQueue class of Section 7.2.2 provides a rotate( ) method that has semantics equivalent to Q.enqueue(Q.dequeue()), for a nonempty queue. Implement such a method for the LinkedQueue class of Sec- tion 7.1.2 without the creation of any new nodes.

**7.2.2**

7.2.2 Implementing a Queue with a Circularly Linked List

To implement the queue ADT using a circularly linked list, we rely on the intuition of Figure 7.7, in which the queue has a head and a tail, but with the next reference of the tail linked to the head. Given such a model, there is no need for us to explicitly store references to both the head and the tail; as long as we keep a reference to the tail, we can always find the head by following the tails next reference.

Code Fragments 7.9 and 7.10 provide an implementation of a CircularQueue class based on this model. The only two instance variables are tail, which is a reference to the tail node (or None when empty), and size, which is the current number of elements in the queue. When an operation involves the front of the queue, we recognize self. tail. next as the head of the queue. When enqueue is called, a new node is placed just after the tail but before the current head, and then the new node becomes the tail.

In addition to the traditional queue operations, the CircularQueue class supports a rotate method that more efficiently enacts the combination of removing the front element and reinserting it at the back of the queue. With the circular representation, we simply set self. tail = self. tail. next to make the old head become the new tail (with the node after the old head becoming the new head).

class CircularQueue: Queue implementation using circularly linked list for storage.

class Node: Lightweight, nonpublic class for storing a singly linked node. (omitted here; identical to that of LinkedStack. Node)

def init (self): Create an empty queue. self. tail = None self. size = 0

# will represent tail of queue # number of queue elements

def len (self): Return the number of elements in the queue. return self. size

def is empty(self): Return True if the queue is empty. return self. size == 0

Code Fragment 7.9: Implementation of a CircularQueue class, using a circularly linked list as storage (continued in Code Fragment 7.10).

7.2. Circularly Linked Lists 269

def first(self): Return (but do not remove) the element at the front of the queue.

Raise Empty exception if the queue is empty. if self.is empty( ):

raise Empty( Queue is empty ) head = self. tail. next return head. element

def dequeue(self): Remove and return the first element of the queue (i.e., FIFO).

Raise Empty exception if the queue is empty. if self.is empty( ):

raise Empty( Queue is empty ) oldhead = self. tail. next if self. size == 1:

self. tail = None else:

self. tail. next = oldhead. next self. size ?= 1 return oldhead. element

# removing only element # queue becomes empty

# bypass the old head

def enqueue(self, e): Add an element to the back of queue.

newest = self. Node(e, None) if self.is empty( ):

newest. next = newest else:

newest. next = self. tail. next

self. tail. next = newest self. tail = newest self. size += 1

# node will be new tail node # initialize circularly

# new node points to head # old tail points to new node # new node becomes the tail

def rotate(self): Rotate front element to the back of the queue. if self. size > 0:

self. tail = self. tail. next # old head becomes new tail

Code Fragment 7.10: Implementation of a CircularQueue class, using a circularly linked list as storage (continued from Code Fragment 7.9).

**7.1.2**

7.1.2 Implementing a Queue with a Singly Linked List

As we did for the stack ADT, we can use a singly linked list to implement the queue ADT while supporting worst-case O(1)-time for all operations. Because we need to perform operations on both ends of the queue, we will explicitly maintain both a head reference and a tail reference as instance variables for each queue. The natural orientation for a queue is to align the front of the queue with the head of the list, and the back of the queue with the tail of the list, because we must be able to enqueue elements at the back, and dequeue them from the front. (Recall from the introduction of Section 7.1 that we are unable to efficiently remove elements from the tail of a singly linked list.) Our implementation of a LinkedQueue class is given in Code Fragments 7.7 and 7.8.

class LinkedQueue: FIFO queue implementation using a singly linked list for storage.

class Node: Lightweight, nonpublic class for storing a singly linked node. (omitted here; identical to that of LinkedStack. Node)

def init (self): Create an empty queue. self. head = None self. tail = None self. size = 0

# number of queue elements Return the number of elements in the queue.

def len (self):

return self. size

def is empty(self): Return True if the queue is empty. return self. size == 0

def first(self): Return (but do not remove) the element at the front of the queue. if self.is empty():

raise Empty( Queue is empty ) return self. head. element # front aligned with head of list

Code Fragment 7.7: Implementation of a queue ADT using a singly linked list (continued in Code Fragment 7.8).

7.1. SinglyLinkedLists 265

def dequeue(self): Remove and return the first element of the queue (i.e., FIFO).

Raise Empty exception if the queue is empty. if self.is empty():

raise Empty( Queue is empty ) answer = self. head. element self. head = self. head. next self. size ?= 1

if self.is empty(): self. tail = None

return answer

# special case as queue is empty # removed head had been the tail

def enqueue(self, e): Add an element to the back of queue.

newest = self. Node(e, None) if self.is empty():

self. head = newest else:

self. tail. next = newest self. tail = newest self. size += 1

# node will be new tail node # special case: previously empty

# update reference to tail node

Code Fragment 7.8: Implementation of a queue ADT using a singly linked list (continued from Code Fragment 7.7).

Many aspects of our implementation are similar to that of the LinkedStack class, such as the definition of the nested Node class. Our implementation of dequeue for LinkedQueue is similar to that of pop for LinkedStack, as both remove the head of the linked list. However, there is a subtle difference because our queue must accurately maintain the tail reference (no such variable was maintained for our stack). In general, an operation at the head has no effect on the tail, but when dequeue is invoked on a queue with one element, we are simultaneously removing the tail of the list. We therefore set self. tail to None for consistency.

There is a similar complication in our implementation of enqueue. The newest node always becomes the new tail. Yet a distinction is made depending on whether that new node is the only node in the list. In that case, it also becomes the new head; otherwise the new node must be linked immediately after the existing tail node.

In terms of performance, the LinkedQueue is similar to the LinkedStack in that all operations run in worst-case constant time, and the space usage is linear in the current number of elements.