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

• 2019

Stack and Queue обидва є непримітивними структурами даних. Основними відмінностями між стеком і чергою є те, що стек використовує метод LIFO (останній у першому) для доступу та додавання елементів даних, тоді як Queue використовує метод FIFO (First in first out) для доступу та додавання елементів даних.

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

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

Діаграма порівняння

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

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

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

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

Приклад

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

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

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

Приклад

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

Ключові відмінності між стеком і чергою

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

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

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

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

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

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

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

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

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

1. PUSH : коли новий елемент додається до вершини стека, відомий як операція PUSH. Натискання елемента в стек викликає додавання елемента, оскільки новий елемент буде вставлений у верхній частині. Після кожної операції натискання верхня частина збільшується на одну. Якщо масив є повним і не можна додати новий елемент, він називається умовою STACK-FULL або STACK OVERFLOW. PUSH OPERATION - функція в C:
   Враховуючи, що стек оголошується як
   int stack [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
2. POP : коли елемент видаляється з верхньої частини стека, він називається операцією POP. Стек зменшується на одиницю після кожної операції. Якщо в стеку не залишилося жодного елемента, і виконується поп, то це призведе до стану STACK UNDERFLOW, що означає, що ваш стек Empty. ПОПЕРЕДЖЕННЯ POP - функції в C:
   Враховуючи, що стек оголошується як
   int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

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

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

1. Вставити: Вставити елемент в чергу.
   Черга оголошується як
   int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}

2. Dequeue : Для видалення елемента з черги.
   Черга оголошується як
   int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

Застосування Stack

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

Застосування черги

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

Висновок

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