Принцип FIFO (First In, First Out)

Материал из m6a
Перейти к: навигация, поиск

Принцип FIFO (First In, First Out) — это принцип организации данных, при котором первый добавленный элемент является первым, который будет извлечен. Этот принцип является основой для структуры данных, называемой очередью (queue).

Основные понятия

  1. Очередь (Queue): Абстрактная структура данных, представляющая собой упорядоченную коллекцию элементов, в которой добавление элементов происходит в конец очереди (rear), а удаление элементов происходит из начала очереди (front).
  2. Начало очереди (Front): Место, откуда происходит удаление элементов из очереди.
  3. Конец очереди (Rear): Место, куда происходит добавление элементов в очередь.
  4. Добавление элемента (Enqueue): Операция добавления нового элемента в конец очереди.
  5. Удаление элемента (Dequeue): Операция удаления элемента из начала очереди.
  6. Первый вошел, первым вышел (First In, First Out - FIFO): Элемент, добавленный в очередь первым, будет удален из очереди первым.

Свойства FIFO

  1. Упорядоченность: Элементы в очереди хранятся в определенном порядке, который определяется порядком их добавления.
  2. Ограниченный доступ: Доступ к элементам очереди ограничен началом и концом очереди. Невозможно получить доступ к элементам, находящимся внутри очереди, без удаления элементов из начала очереди.
  3. Справедливость: Элементы обслуживаются в порядке их поступления, что обеспечивает справедливость при обработке данных.

Операции над очередью

  1. Enqueue (Добавление): Добавляет новый элемент в конец очереди.
    1. Сложность: $O(1)$
  2. Dequeue (Удаление): Удаляет элемент из начала очереди и возвращает его значение.
    1. Сложность: $O(1)$
  3. Peek (Просмотр): Возвращает значение элемента, находящегося в начале очереди, не удаляя его.
    1. Сложность: $O(1)$
  4. isEmpty (Проверка на пустоту): Проверяет, является ли очередь пустой. Возвращает `true`, если очередь пуста, и `false` в противном случае.
    1. Сложность: $O(1)$
  5. size (Размер): Возвращает количество элементов в очереди.
    1. Сложность: $O(1)$

Реализация очереди

Очередь можно реализовать с использованием массивов или связных списков. Существуют различные типы очередей, такие как линейная очередь и циклическая очередь.

  1. Реализация очереди с использованием массива (линейная очередь):
    1. ```python
    2. class Queue:
    3. def __init__(self, capacity):
    4. self.capacity = capacity
    5. self.arr = [None] * capacity
    6. self.front = 0
    7. self.rear = -1
    8. self.size = 0
    10. def enqueue(self, data):
    11. if self.size == self.capacity:
    12. print("Queue Overflow")
    13. return
    14. self.rear += 1
    15. self.arr[self.rear] = data
    16. self.size += 1
    18. def dequeue(self):
    19. if self.size == 0:
    20. print("Queue Underflow")
    21. return None
    22. data = self.arr[self.front]
    23. self.arr[self.front] = None
    24. self.front += 1
    25. self.size -= 1
    26. return data
    28. def peek(self):
    29. if self.size == 0:
    30. print("Queue is empty")
    31. return None
    32. return self.arr[self.front]
    34. def isEmpty(self):
    35. return self.size == 0
    37. def size(self):
    38. return self.size
    39. ```
  2. Реализация очереди с использованием массива (циклическая очередь):
    1. ```python
    2. class CircularQueue:
    3. def __init__(self, capacity):
    4. self.capacity = capacity
    5. self.arr = [None] * capacity
    6. self.front = 0
    7. self.rear = -1
    8. self.size = 0
    10. def enqueue(self, data):
    11. if self.size == self.capacity:
    12. print("Queue Overflow")
    13. return
    14. self.rear = (self.rear + 1) % self.capacity
    15. self.arr[self.rear] = data
    16. self.size += 1
    18. def dequeue(self):
    19. if self.size == 0:
    20. print("Queue Underflow")
    21. return None
    22. data = self.arr[self.front]
    23. self.arr[self.front] = None
    24. self.front = (self.front + 1) % self.capacity
    25. self.size -= 1
    26. return data
    28. def peek(self):
    29. if self.size == 0:
    30. print("Queue is empty")
    31. return None
    32. return self.arr[self.front]
    34. def isEmpty(self):
    35. return self.size == 0
    37. def size(self):
    38. return self.size
    39. ```
  2. Реализация очереди с использованием связного списка:
    1. ```python
    2. class Node:
    3. def __init__(self, data):
    4. self.data = data
    5. self.next = None
    7. class Queue:
    8. def __init__(self):
    9. self.front = None
    10. self.rear = None
    11. self.size = 0
    13. def enqueue(self, data):
    14. new_node = Node(data)
    15. if self.rear is None:
    16. self.front = new_node
    17. self.rear = new_node
    18. else:
    19. self.rear.next = new_node
    20. self.rear = new_node
    21. self.size += 1
    23. def dequeue(self):
    24. if self.front is None:
    25. print("Queue Underflow")
    26. return None
    27. data = self.front.data
    28. self.front = self.front.next
    29. if self.front is None:
    30. self.rear = None
    31. self.size -= 1
    32. return data
    34. def peek(self):
    35. if self.front is None:
    36. print("Queue is empty")
    37. return None
    38. return self.front.data
    40. def isEmpty(self):
    41. return self.front is None
    43. def size(self):
    44. return self.size
    45. ```

Применение очередей

Очереди используются в широком спектре приложений, включая:

  1. Планирование задач: Очереди используются для управления порядком выполнения задач в операционных системах и других системах.
  2. Обработка запросов: Очереди используются для обработки запросов к серверам и другим ресурсам.
  3. Моделирование: Очереди используются для моделирования реальных систем, таких как очереди в магазинах, банках и т.д.
  4. Поиск в ширину (BFS): Очереди используются для хранения информации о посещенных вершинах графа при поиске в ширину.
  5. Буферизация данных: Очереди используются для буферизации данных между производителем и потребителем.
  6. Системы обмена сообщениями: Очереди используются для асинхронной передачи сообщений между различными компонентами системы.

Примеры использования очереди

  1. Моделирование очереди в магазине:
    1. ```python
    2. import time
    3. import random
    5. class Customer:
    6. def __init__(self, id):
    7. self.id = id
    8. self.arrival_time = time.time()
    9. self.service_time = random.randint(2, 5)
    11. class StoreQueue:
    12. def __init__(self):
    13. self.queue = []
    14. self.customer_id = 1
    16. def add_customer(self):
    17. customer = Customer(self.customer_id)
    18. self.queue.append(customer)
    19. print(f"Customer {customer.id} arrived at {time.strftime('%H:%M:%S', time.localtime(customer.arrival_time))}")
    20. self.customer_id += 1
    22. def serve_customer(self):
    23. if self.queue:
    24. customer = self.queue.pop(0)
    25. print(f"Serving customer {customer.id}. Service time: {customer.service_time} seconds.")
    26. time.sleep(customer.service_time)
    27. print(f"Customer {customer.id} finished service.")
    28. else:
    29. print("No customers in the queue.")
    31. def run_simulation(self, num_customers=5):
    32. for _ in range(num_customers):
    33. self.add_customer()
    34. time.sleep(random.randint(1, 3)) # Simulate random arrival times
    35. while self.queue:
    36. self.serve_customer()
    38. store = StoreQueue()
    39. store.run_simulation()
    40. ```
  2. Задача о горячей картошке (Hot Potato):
    1. ```python
    2. def hot_potato(names, num):
    3. queue = list(names)
    4. while len(queue) > 1:
    5. for i in range(num):
    6. queue.append(queue.pop(0))
    7. eliminated = queue.pop(0)
    8. print(f"{eliminated} исключен.")
    9. return queue[0]
    11. names = ["Bill", "David", "Susan", "Jane", "Kent", "Brad"]
    12. winner = hot_potato(names, 7)
    13. print(f"Победитель: {winner}")
    14. ```

Преимущества и недостатки использования очередей

Преимущества:

  1. Справедливость: Элементы обслуживаются в порядке их поступления.
  2. Простота реализации: Очереди легко реализовать с использованием массивов или связных списков.
  3. Широкий спектр применения: Очереди используются в различных областях программирования.

Недостатки:

  1. Ограниченный доступ: Доступ к элементам очереди ограничен началом и концом очереди.
  2. Фиксированный размер (при реализации с использованием массива): При реализации очереди с использованием массива необходимо заранее определять его размер, что может быть ограничением в некоторых случаях.
  3. Необходимость сдвига элементов (при реализации с использованием линейной очереди): При удалении элемента из начала очереди необходимо сдвигать все последующие элементы на одну позицию влево, что может быть неэффективным при большом количестве элементов.

Понимание принципа FIFO и очередей является важным для разработки эффективного и надежного программного обеспечения.

Источник — «http://wiki.m6a.ru/index.php?title=Принцип_FIFO_(First_In,_First_Out)&oldid=1114»