Різниця між стеком і чергою

Стек проти черги

Стек - це упорядкований список, у якому вставлення та видалення елементів списку можна робити лише в одному кінці, що називається вгорі. З цієї причини стек розглядається як структура даних Last in First out (LIFO). Черга - це також упорядкований список, у якому вставлення елементів списку виконується в одному кінці, званому тилом, а видалення елементів робиться в іншому кінці, що називається переднім. Цей механізм вставки та видалення перетворює чергу в структуру даних "Перше в першому" (FIFO).

Що таке стек?

Як було сказано раніше, стек - це структура даних, в яку елементи додаються та вилучаються лише з одного кінця, який називається вершиною. Стек дозволяє лише дві основні операції, що називаються push і pop. Операція натискання додає новий елемент у верхню частину стека. Поп-операція видаляє елемент з верхньої частини стека. Якщо стек вже заповнений, під час операції натискання він вважається переповненням стека. Якщо поп-операція виконується у вже порожній стеці, вона вважається потоком стеку. Через малу кількість операцій, які можна було б виконати на стеці, вона розглядається як обмежена структура даних. Крім того, згідно з тим, як визначені операції push і pop, зрозуміло, що елементи, які були додані останніми до стеку, виходять із стеку першими. Тому стек розглядається як структура даних LIFO.

Що таке черга?

У черзі елементи додаються із задньої частини черги та видаляються з передньої частини черги. Оскільки елементи, які додаються спочатку, будуть видалені спочатку з черги, він підтримує порядок FIFO. Завдяки такому порядку додавання та видалення елементів черга представляє ідею лінії оформлення замовлення. Загальні операції, які підтримуються чергою, - це операції черги та виходу з черги. Операція черги додасть елемент в задній частині черги, тоді як операція з чергою видаляє елемент з передньої частини черги. Загалом, черги не обмежують кількість елементів, які можна додати до черги, крім обмежень пам'яті.

Яка різниця між стеком і чергою?

Незважаючи на те, що і стеки, і черги є видом упорядкованих списків, вони мають деякі важливі відмінності. У стеках додавання або видалення елементів може бути виконано лише з одного кінця, який називається верхній, тоді як у чергах додавання елементів відбувається з одного кінця, званого тилом, а видалення елементів відбувається з іншого кінця, який називається переднім. У стеку елементи, додані останніми до стеку, будуть видалені спочатку зі стека. Тому стек розглядається як структура даних LIFO. У чергах елементи, які додаються спочатку, будуть видалені спочатку з черги. Тому черга розглядається як структура даних FIFO.

Посилання:

Різниця між стеком і купами