3.25 Write the routines to implement queues using a. linked lists b. arrays

在实现队列（Queue）的数据结构时，可以使用链表（Linked Lists）和数组（Arrays）这两种常见的数据结构。

a. 使用链接列表（Linked List）实现队列：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class QueueLL:
    def __init__(self):
        self.head = None
        self.tail = None

    # 入队操作（enqueue）
    def enqueue(self, data):
        new_node = Node(data)
        if not self.is_empty():
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node

    # 出队操作（dequeue）
    def dequeue(self):
        if self.is_empty():
            return None
        temp_data = self.head.data
        self.head = self.head.next
        if self.is_empty():
            self.tail = None
        return temp_data

    # 检查队列是否为空
    def is_empty(self):
        return self.head is None

    # 显示队列元素
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

b. 使用数组实现队列（Array-Based Queue）:

class QueueArray:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = -1
        self.rear = -1

    def is_empty(self):
        return self.front == self.rear

    def enqueue(self, data):
        if (self.rear + 1) % len(self.queue) == self.front:
            raise Exception("Queue full")
        if self.is_empty():
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % len(self.queue)
        self.queue[self.rear] = data

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue empty")
        value = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % len(self.queue)
        return value

    def display(self):
        if self.is_empty():
            print("Queue is empty")
        else:
            index = self.front
            while True:
                try:
                    print(self.queue[index], end=" -> ")
                    index = (index + 1) % len(self.queue)
                except IndexError:
                    break
            print("None")