Как устроена очередь? Чем она отличается от стека?

Очередь — это структура данных, работающая по принципу FIFO. FIFO означает: То есть элемент, который был добавлен первым, извлекается первым.

Очередь — это структура данных, работающая по принципу FIFO.

FIFO означает:

First In — First Out

То есть элемент, который был добавлен первым, извлекается первым.

Пример из жизни — очередь в магазине: кто пришел первым, того обслуживают первым.

Как работает очередь?

Представим очередь:

начало → 10, 20, 30 ← конец

Если добавить элемент 40, он попадет в конец:

начало → 10, 20, 30, 40 ← конец

Если извлечь элемент, будет удален первый элемент 10.

начало → 20, 30, 40 ← конец

Основные операции очереди

1. Enqueue

Enqueue — добавление элемента в конец очереди.

const queue = [];

queue.push(10);
queue.push(20);
queue.push(30);

const queue: number[] = [];

queue.push(10);
queue.push(20);
queue.push(30);

package main
func main() {
  queue := []int{}

  queue = append(queue, 10)
  queue = append(queue, 20)
  queue = append(queue, 30)
}

public class Example {
  public static void main(String[] args) {
    var queue = new java.util.ArrayList<Integer>();

    queue.add(10);
    queue.add(20);
    queue.add(30);
  }
}

queue = []

queue.append(10)
queue.append(20)
queue.append(30)

---

2. Dequeue

Dequeue — удаление элемента из начала очереди.

const first = queue.shift(); // 10

const first = queue.shift(); // 10

package main
func main() {
  first := queue[0] // 10
}

public class Example {
  public static void main(String[] args) {
    var first = queue.remove(0); // 10
  }
}

first = queue.pop(0) # 10

---

3. Front

Просмотр первого элемента без удаления.

const front = queue[0];

const front = queue[0];

package main
func main() {
  front := queue[0]
}

public class Example {
  public static void main(String[] args) {
    var front = queue[0];
  }
}

front = queue[0]

---

4. IsEmpty

Проверка, пуста ли очередь.

const isEmpty = queue.length === 0;

const isEmpty = queue.length === 0;

package main
func main() {
  isEmpty := len(queue) == 0
}

public class Example {
  public static void main(String[] args) {
    var isEmpty = queue.length() == 0;
  }
}

isEmpty = len(queue) == 0

---

5. Size

Получение количества элементов в очереди.

const size = queue.length;

const size = queue.length;

package main
func main() {
  size := len(queue)
}

public class Example {
  public static void main(String[] args) {
    var size = queue.length();
  }
}

size = len(queue)

Отличие очереди от стека

Где применяется очередь?

Очереди используются:

• в операционных системах;
• при планировании задач;
• в обработке запросов;
• в сетевых технологиях;
• в очередях печати;
• в алгоритме обхода графа в ширину;
• в системах сообщений;
• в веб-серверах.

Разновидности очередей

Есть несколько разновидностей очередей:

• обычная очередь;
• циклическая очередь;
• двусторонняя очередь;
• очередь с приоритетом.

В очереди с приоритетом первым извлекается не обязательно самый старый элемент, а элемент с наибольшим приоритетом.

Вывод

Очередь — это структура данных, где первым извлекается тот элемент, который был добавлен раньше всех. Главное отличие от стека: стек работает по принципу LIFO, а очередь — по принципу FIFO.