能够实现队列的基本操作,建立队列的线性或者链式存储结构,实现队列的初始化,enqueue,dequeue等基本运算
时间: 2024-12-04 10:22:14 浏览: 8
在计算机科学中,队列是一种先进先出(First In First Out, FIFO)的数据结构,通常有两种基本的实现方式:线性存储结构(基于数组)和非线性存储结构(基于链表)。
**1. 线性存储结构(基于数组)**
```python
class LinearQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.front = -1
self.rear = -1
def is_empty(self):
return self.front == -1
def enqueue(self, data):
if (self.rear + 1) % len(self.queue) == self.front:
print("Queue is full")
else:
self.rear = (self.rear + 1) % len(self.queue)
self.queue[self.rear] = data
def dequeue(self):
if self.is_empty():
print("Queue is empty")
else:
data = self.queue[self.front]
self.queue[self.front] = None
self.front = (self.front + 1) % len(self.queue)
return data
```
**2. 链式存储结构(基于链表)**
```python
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
class LinkedListQueue:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def enqueue(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.is_empty():
print("Queue is empty")
else:
removed_data = self.head.value
self.head = self.head.next
if self.head is None:
self.tail = None
return removed_data
```
这两个例子分别展示了如何初始化队列、添加元素到队列尾部(enqueue)和从队列头部移除元素(dequeue)。队列的基本操作包括判断队列是否空、入队和出队。
阅读全文