class CircularBufferArray:
def __init__(self, capacity):
self.capacity = capacity
self.buffer = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def enqueue(self, value):
if self.is_full():
return
self.buffer[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.is_empty():
return None
value = self.buffer[self.head]
self.buffer[self.head] = None
self.head = (self.head + 1) % self.capacity
self.size -= 1
return value
def peek(self):
if self.is_empty():
return None
return self.buffer[self.head]
class Node:
def __init__(self, value):
self.value = value
self.next = None
class CircularBufferList:
def __init__(self, capacity):
self.capacity = capacity
self.size = 0
self.head = None
self.tail = None
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def enqueue(self, value):
if self.is_full():
return
new_node = Node(value)
if self.is_empty():
self.head = self.tail = new_node
new_node.next = new_node
else:
new_node.next = self.head
self.tail.next = new_node
self.tail = new_node
self.size += 1
def dequeue(self):
if self.is_empty():
return None
value = self.head.value
if self.size == 1:
self.head = self.tail = None
else:
self.head = self.head.next
self.tail.next = self.head
self.size -= 1
return value
def peek(self):
if self.is_empty():
return None
return self.head.value
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self):
return self.size == 0
def enqueue(self, value):
new_node = Node(value)
if self.is_empty():
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.size += 1
def dequeue(self):
if self.is_empty():
return None
value = self.head.value
self.head = self.head.next
if self.head is None:
self.tail = None
self.size -= 1
return value
if __name__ == "__main__":
import time
n = 1000000
capacity = 10000
buf_array = CircularBufferArray(capacity)
start = time.perf_counter()
for i in range(n):
if not buf_array.is_full():
buf_array.enqueue(i)
else:
buf_array.dequeue()
buf_array.enqueue(i)
time_array = time.perf_counter() - start
buf_list = CircularBufferList(capacity)
start = time.perf_counter()
for i in range(n):
if not buf_list.is_full():
buf_list.enqueue(i)
else:
buf_list.dequeue()
buf_list.enqueue(i)
time_list = time.perf_counter() - start
simple_list = LinkedList()
start = time.perf_counter()
for i in range(n):
simple_list.enqueue(i)
if simple_list.size > capacity:
simple_list.dequeue()
time_simple = time.perf_counter() - start
print(f"Циклический буфер на массиве: {time_array} сек")
print(f"Циклический буфер на списоке: {time_list} сек")
print(f"Обычный список: {time_simple} сек")