Зміст

• Порівняльна діаграма
• Визначення стека
• Приклад
• Визначення черги
• Приклад
• Реалізація стека
• Реалізація черги
• Операції на стеці
• Операції в черзі
• Застосування стека
• Додатки черги
• Висновок

І стек, і черга - це непримітивні структури даних. Основні відмінності між стеком та чергою полягають у тому, що стек використовує метод LIFO (останній у першому виході) для доступу та додавання елементів даних, тоді як черга використовує метод FIFO (Перший у першому вихідному) для доступу та додавання елементів даних.

Стек має лише один кінець, відкритий для виштовхування та висунення елементів даних, з іншого боку Черга має обидва кінці відкритих для присвоєння та видалення елементів даних.

Стек і черга - це структури даних, що використовуються для зберігання елементів даних і фактично засновані на деякому еквіваленті реального світу. Наприклад, стек - це стек компакт-дисків, з якого можна дістати та помістити компакт-диск через верхню частину стека компакт-дисків. Аналогічно, черга - це черга на квитки в Театр, де людина, що стоїть на першому місці, тобто передня частина черги буде подана спочатку, а нова особа, яка приїжджає, з’явиться в задній частині черги (задній кінець черги).

1. Порівняльна діаграма
2. Визначення
3. Ключові відмінності
4. Впровадження
5. Операції
6. Програми
7. Висновок

Порівняльна діаграма

Основа для порівняння	Стек	Чергу
Принцип роботи	LIFO (Останній у першому виході)	FIFO (перший у першому виході)
Будова	Цей же кінець використовується для вставки та видалення елементів.	Один кінець використовується для вставки, тобто задній кінець, а інший кінець використовується для видалення елементів, тобто передній.
Кількість використаних покажчиків	Один	Два (у простому випадку черги)
Проведені операції	Push and Pop	Анкей і декуе
Обстеження порожнього стану	Вгору == -1	Фронт == -1 || Спереду == Задня + 1
Обстеження повного стану	Вгору == Макс - 1	Задній == Макс - 1
Варіанти	У нього немає варіантів.	Він має такі варіанти, як кругова черга, черговість з пріоритетом, черга з подвійним завершенням.
Впровадження	Простіше	Порівняно складний

Визначення стека

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

Зауважте, що елемент, до якого часто звертаються в стеку, є найвищим елементом, тоді як останній доступний елемент знаходиться в нижній частині стека.

Приклад

Деякі з вас можуть їсти печиво (або Поппін). Якщо ви припускаєте, порвана лише одна сторона обкладинки, а печиво виймається по черзі. Це називається вискакуванням, і так само, якщо ви хочете зберегти печиво на деякий час пізніше, ви покладете їх назад в пакет через той же порваний кінець, що називається штовханням.

Визначення черги

Черга - це лінійна структура даних, що надходить до категорії непомітивного типу. Це сукупність елементів подібного типу. Додавання нових елементів відбувається на одному кінці, званому задньому кінці. Аналогічно, видалення існуючих елементів відбувається на іншому кінці, званому Front-end, і логічно це тип списку First in first out (FIFO).

Приклад

У нашому щоденному житті ми стикаємося з багатьма ситуаціями, коли нам доводиться чекати бажаної послуги, і там нам доводиться потрапляти в чергу очікування, щоб ми отримали обслуговування. Цю чергу очікування можна вважати чергою.

1. Стек слідує за механізмом LIFO, з іншого боку Черга слідує за механізмом FIFO для додавання та видалення елементів.
2. У стеці той самий кінець використовується для вставки та видалення елементів. Навпаки, два різні кінці використовуються у черзі для вставки та видалення елементів.
3. Оскільки стек має лише один відкритий кінець, це є причиною використання лише одного вказівника для позначення верхньої частини стека. Але черга використовує два вказівники для позначення переднього та заднього кінця черги.
4. Стек виконує дві операції, відомі як push і pop, тоді як у черзі його відомі як enqueue та dequeue.
5. Реалізація стека простіша, тоді як реалізація черги складна.
6. У черзі є такі варіанти, як кругова черга, черга з пріоритетом, черга з подвійним завершенням тощо. На відміну від цього, стек не має варіантів.

Реалізація стека

Стек можна застосувати двома способами:

1. Статична реалізація використовує масиви для створення стека. Статична реалізація хоч і не є простою технікою, але не є гнучким способом створення, оскільки оголошення розміру стека потрібно робити під час розробки програми, після чого розмір не може змінюватись. Крім того, статична реалізація не дуже ефективна щодо використання пам'яті. Оскільки масив (для реалізації стека) оголошується до початку операції (на час проектування програми). Тепер, якщо кількість елементів для сортування буде дуже меншою у стеці, статично виділена пам'ять буде витрачена. З іншого боку, якщо в стеці буде збережена більша кількість елементів, ми не зможемо змінити розмір масиву, щоб збільшити його ємність, щоб він міг вміщувати нові елементи.
2. Динамічна реалізація також називається пов'язаним представленням списку і використовує покажчики для реалізації типу стека структури даних.

Реалізація черги

Черга може бути реалізована двома способами:

1. Статична реалізація: Якщо черга реалізована за допомогою масивів, точну кількість елементів, які ми хочемо зберегти у черзі, слід заздалегідь забезпечити, оскільки розмір масиву повинен бути оголошений під час проектування або до початку обробки. У цьому випадку початок масиву стане лицьовою стороною черги, а останнє місце розташування масиву буде виконувати функції тилу черги. Наступне співвідношення дає всі елементи існування в черзі при реалізації з використанням масивів:
   спереду - ззаду + 1
   Якщо "ззаду <спереду", то в черзі не буде жодного елемента, а черга завжди буде порожньою.
2. Динамічна реалізація: Реалізуючи черги за допомогою покажчиків, головним недоліком є ​​те, що вузол у зв'язаному поданні витрачає більше місця в пам'яті, ніж відповідний елемент у представленні масиву. Оскільки у кожному вузлі є щонайменше два поля, одне для поля даних, а інше для зберігання адреси наступного вузла, тоді як у зв'язаному поданні є лише поле даних. Заслуга використання пов'язаного представлення стає очевидною, коли потрібно вставити або видалити елемент посередині групи інших елементів.

Операції на стеці

Основними операціями, які можна керувати на стеці, є такі:

1. ПОРУШИТИ: коли новий елемент додається у верхню частину стека, називається операцією PUSH. Натискання елемента на стек викликає додавання елемента, оскільки новий елемент буде вставлений вгорі. Після кожної операції натискання верх збільшується на одиницю. Якщо масив заповнений, і новий елемент не може бути доданий, він називається STACK-FULL умовою або STACK OVERFLOW. PUSH OPERATION - функція в C:
   Зважаючи на стек, оголошено як
   int stack, top = -1;
недійсний поштовх ()
{
предмет int;
якщо (верх <4)
{
f ("Введіть число");
сканування ("% d", & елемент);
верх = верх + 1;
стек = предмет;
}
ще
{
f ("Стек заповнений");
}
}
2. POP: Коли елемент видаляється з верхньої частини стека, він відомий як операція POP. Стік зменшується на одиницю, після кожної поп-операції. Якщо в стеку не залишилося жодного елемента, і спливаюче вікно виконується, тоді це призведе до умови STACK UNDERFLOW, що означає, що ваш стек порожній. POP OPERATION - функції в C:
   Зважаючи на стек, оголошено як
   int stack, top = -1;
недійсний поп ()
{
предмет int;
якщо (вгорі> = 4)
{
item = стек;
верх = верх - 1;
f ("Кількість видалених =% d", пункт);
}
ще
{
f ("Стек порожній");
}
}

Операції в черзі

Основними операціями, які можна виконати в черзі, є:

1. Записка: Щоб вставити елемент у чергу.Запуск операційної функції в C:
   Черга оголошена як
   int черга, спереду = -1 і ззаду = -1;
недійсне додавання ()
{
предмет int;
якщо (ззаду <4)
{
f ("Введіть число");
сканування ("% d", & елемент);
якщо (спереду == -1)
{
передня = 0;
тил = 0;
}
ще
{
задній = задній + 1;
}
черга = предмет;
}
ще
{
f ("Черга повна");
}
}

2. Dequeue: Для видалення елемента з черги. Функція операції в C:
   Черга оголошена як
   int черга, спереду = -1 і ззаду = -1;
недійсне видалення ()
{
предмет int;
якщо (спереду! = -1)
{
item = черга;
якщо (спереду == ззаду)
{
передня = -1;
тил = -1;
}
ще
{
спереду = спереду + 1;
f ("Кількість видалених =% d", пункт);
}
}
ще
{
f ("Черга порожня");
}
}

Застосування стека

• Розбір в компіляторі.
• Віртуальна машина Java.
• Скасувати в текстовому редакторі.
• Кнопка "Назад" у веб-браузері.
• Мова PostScript для ers.
• Реалізація викликів функцій у компіляторі.

Додатки черги

• Буфери даних
• Асинхронна передача даних (IO файлів, труби, сокети).
• Виділення запитів на спільному ресурсі (er, процесор).
• Аналіз руху.
• Визначте кількість касирів у супермаркеті.

Висновок

Стек і черга - це лінійні структури даних, які відрізняються певними способами, як робочий механізм, структура, реалізація, варіанти, але обидва використовуються для зберігання елементів у списку та виконання операцій зі списку, таких як додавання та видалення елементів. Хоча існують деякі обмеження простої черги, яку відновлюють за допомогою інших типів черги.