队列的学习（一）用数组和链表实现单向队列
队列（Queue）是一种先进先出的数据结构，类似于现实生活中排队的场景。它有两个基本操作：入队（enqueue）和出队（dequeue）。在本文中，我们将介绍如何使用数组和链表来实现单向队列。
数组实现单向队列
数组实现单向队列需要两个指针，一个指向队头（front），一个指向队尾（rear）。入队操作时，将数据插入到队尾，即rear指针指向的位置；出队操作时，将队头数据删除，即front指针指向的位置。使用数组实现单向队列的优点是简单易懂，缺点是容易产生假溢出（队列未满但无法插入数据）。
以下是使用数组实现单向队列的代码示例：
class ArrayQueue: def __init__(self, capacity: int): self.capacity = capacity self.data = [None] * capacity self.front = 0 self.rear = 0 def enqueue(self, item: int) -> bool: if self.rear == self.capacity: return False self.data[self.rear] = item self.rear += 1 return True def dequeue(self) -> int: if self.front == self.rear: return None item = self.data[self.front] self.front += 1 return item
链表实现单向队列
链表实现单向队列只需要一个指针，即指向队尾的节点，每个节点包含一个数据域和一个指向下一个节点的指针。入队操作时，创建一个新节点，将其插入到队尾节点后面；出队操作时，删除队头节点即可。使用链表实现单向队列的优点是不会产生假溢出，缺点是需要较多的空间存储指针信息。
以下是使用链表实现单向队列的代码示例：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class LinkedQueue: def __init__(self): self.head = ListNode() self.tail = self.head def enqueue(self, item: int) -> None: new_node = ListNode(item) self.tail.next = new_node self.tail = new_node def dequeue(self) -> int: if self.head.next is None: return None item = self.head.next.val self.head.next = self.head.next.next if self.head.next is None: self.tail = self.head return item
以上是使用数组和链表分别实现单向队列的方法。根据实际需求，选择合适的实现方式即可。
队列的学习（一）用数组和链表实现单向队列
队列（Queue）是一种先进先出的数据结构，类似于现实生活中排队的场景。它有两个基本操作：入队（enqueue）和出队（dequeue）。在本文中，我们将介绍如何使用数组和链表来实现单向队列。
数组实现单向队列
数组实现单向队列需要两个指针，一个指向队头（front），一个指向队尾（rear）。入队操作时，将数据插入到队尾，即rear指针指向的位置；出队操作时，将队头数据删除，即front指针指向的位置。使用数组实现单向队列的优点是简单易懂，缺点是容易产生假溢出（队列未满但无法插入数据）。
以下是使用数组实现单向队列的代码示例：
class ArrayQueue: def __init__(self, capacity: int): self.capacity = capacity self.data = [None] * capacity self.front = 0 self.rear = 0 def enqueue(self, item: int) -> bool: if self.rear == self.capacity: return False self.data[self.rear] = item self.rear += 1 return True def dequeue(self) -> int: if self.front == self.rear: return None item = self.data[self.front] self.front += 1 return item
链表实现单向队列
链表实现单向队列只需要一个指针，即指向队尾的节点，每个节点包含一个数据域和一个指向下一个节点的指针。入队操作时，创建一个新节点，将其插入到队尾节点后面；出队操作时，删除队头节点即可。使用链表实现单向队列的优点是不会产生假溢出，缺点是需要较多的空间存储指针信息。
以下是使用链表实现单向队列的代码示例：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class LinkedQueue: def __init__(self): self.head = ListNode() self.tail = self.head def enqueue(self, item: int) -> None: new_node = ListNode(item) self.tail.next = new_node self.tail = new_node def dequeue(self) -> int: if self.head.next is None: return None item = self.head.next.val self.head.next = self.head.next.next if self.head.next is None: self.tail = self.head return item
以上是使用数组和链表分别实现单向队列的方法。根据实际需求，选择合适的实现方式即可。
