Содержание

• Сравнительная таблица
• Определение стека
• пример
• Определение очереди
• пример
• Реализация стека
• Реализация очереди
• Операции над стеком
• Операции в очереди
• Приложения стека
• Приложения очереди
• Вывод

Стек и Очередь оба являются непримитивными структурами данных. Основные различия между стеком и очередью заключаются в том, что в стеке используется метод LIFO (последний пришел первым вышел) для доступа и добавления элементов данных, тогда как в очереди используется метод FIFO (первый пришел первым вышел) для доступа и добавления элементов данных.

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

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

1. Сравнительная таблица
2. Определение
3. Ключевые отличия
4. Реализация
5. операции
6. Приложения
7. Вывод

Сравнительная таблица

Основа для сравнения	стек	Очередь
Принцип работы	LIFO (последний пришел первым вышел)	FIFO (первый на первом)
Состав	Тот же конец используется для вставки и удаления элементов.	Один конец используется для вставки, то есть заднего конца, а другой конец используется для удаления элементов, то есть переднего конца.
Количество использованных указателей	Один	Два (в простом случае очереди)
Выполненные операции	Push и Pop	Ставить в очередь и оставлять в очередь
Экспертиза пустого состояния	Топ == -1	Фронт == -1 || Фронт == Тыл + 1
Экспертиза полного состояния	Топ == Макс - 1	Задний == Макс - 1
Варианты	У него нет вариантов.	У этого есть варианты как круговая очередь, приоритетная очередь, дважды законченная очередь.
Реализация	Simpler	Сравнительно сложный

Определение стека

Стек - это не примитивная линейная структура данных. Это упорядоченный список, в который добавляется новый элемент, а существующий элемент удаляется только с одного конца, называемого вершиной стека (TOS). Поскольку все удаление и вставка в стек выполняется с вершины стека, последний добавленный элемент будет первым, который будет удален из стека. По этой причине стек называется списком типа «последний пришел - первым обслужен» (LIFO).

Обратите внимание, что элемент, к которому часто обращаются в стеке, является самым верхним элементом, тогда как последний доступный элемент находится в нижней части стека.

пример

Некоторые из вас могут есть печенье (или Поппинс). Если вы предполагаете, порвана только одна сторона крышки, и печенье вынимается одна за другой. Это то, что называется хлопаньем, и аналогичным образом, если вы хотите сохранить печенье в течение некоторого времени позже, вы положите его обратно в пачку через тот же порванный конец, называемый толканием.

Определение очереди

Очередь с линейной структурой данных относится к категории непримитивного типа. Это коллекция элементов подобного типа. Добавление новых элементов происходит на одном конце, называемом задним концом. Точно так же удаление существующих элементов происходит на другом конце, называемом Front-end, и это логически тип списка «первым пришел - первым обслужен» (FIFO).

пример

В нашей повседневной жизни мы сталкиваемся со многими ситуациями, когда нам приходится ждать желаемого обслуживания, и мы вынуждены стоять в очереди на обслуживание своей очереди. Эту очередь ожидания можно рассматривать как очередь.

1. Стек следует за механизмом LIFO с другой стороны. Очередь следует за механизмом FIFO для добавления и удаления элементов.
2. В стеке один и тот же конец используется для вставки и удаления элементов. Напротив, два разных конца используются в очереди для вставки и удаления элементов.
3. Поскольку в стеке есть только один открытый конец, это является причиной использования только одного указателя для ссылки на вершину стека. Но очередь использует два указателя для ссылки на передний и задний конец очереди.
4. Стек выполняет две операции, известные как push и pop, а в очереди его называют enqueue и dequeue.
5. Реализация стека проще, тогда как реализация очереди сложна.
6. Очередь имеет варианты, такие как круговая очередь, приоритетная очередь, очередь с двойным окончанием и т. Д. В отличие от стека нет вариантов.

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

Стек может быть применен двумя способами:

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

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

Очередь может быть реализована двумя способами:

1. Статическая реализация: Если очередь реализована с использованием массивов, точное количество элементов, которые мы хотим сохранить в очереди, должно быть заранее определено, поскольку размер массива должен быть объявлен во время разработки или до начала обработки. В этом случае начало массива станет передней частью очереди, а последнее местоположение массива будет действовать в качестве задней части очереди. Следующее отношение дает всем элементам, существующим в очереди, при реализации с использованием массивов:
   спереди - сзади + 1
   Если задний <front>, то в очереди не будет элементов, или очередь всегда будет пустой.
2. Динамическая реализацияРеализация очередей с использованием указателей, основным недостатком которых является то, что узел в связанном представлении потребляет больше памяти, чем соответствующий элемент в представлении массива. Поскольку в каждом узле имеется по меньшей мере два поля, одно для поля данных, а другое для хранения адреса следующего узла, тогда как в связанном представлении присутствует только поле данных. Преимущество использования связанного представления становится очевидным, когда требуется вставить или удалить элемент в середине группы других элементов.

Операции над стеком

Основные операции, которые могут выполняться в стеке:

1. ОТ СЕБЯ: когда новый элемент добавляется к вершине стека, называется операцией PUSH. Нажатие элемента в стеке вызывает добавление элемента, так как новый элемент будет вставлен сверху. После каждой операции толчка верх увеличивается на единицу. Если массив заполнен и новый элемент не может быть добавлен, это называется условием STACK-FULL или STACK OVERFLOW. РАБОТА С НАЖИМОМ - функция в С:
   Учитывая стек объявлен как
   стек int, top = -1;
Пустой толчок ()
{
int item;
если (верх <4)
{
f («Введите число»);
scan ("% d", & item);
верх = верх + 1;
стек = элемент;
}
еще
{
f («стек заполнен»);
}
}
2. POP: Когда элемент удаляется из верхней части стека, он называется операцией POP. Стек уменьшается на единицу после каждой операции pop. Если в стеке не осталось элемента и выполняется всплывающее окно, это приведет к условию STACK UNDERFLOW, означающему, что ваш стек пуст. POP OPERATION - функции в C:
   Учитывая стек объявлен как
   стек int, top = -1;
void pop ()
{
int item;
if (top> = 4)
{
пункт = стек;
top = top - 1;
f («Удалено число =% d», элемент);
}
еще
{
f («Стек пуст»);
}
}

Операции в очереди

Основные операции, которые могут быть выполнены в очереди:

1. Ставить: Вставить элемент в очередь. Функция операции записи в C:
   Очередь объявлена ​​как
   int queue, Front = -1 и Rear = -1;
void add ()
{
int item;
если (сзади <4)
{
f («Введите число»);
scan ("% d", & item);
если (спереди == -1)
{
передний = 0;
тыл = 0;
}
еще
{
тыл = тыл + 1;
}
очередь = элемент;
}
еще
{
f («Очередь заполнена»);
}
}

2. Dequeue: Чтобы удалить элемент из очереди. Функция операции записи в C:
   Очередь объявлена ​​как
   int queue, Front = -1 и Rear = -1;
void delete ()
{
int item;
если (спереди! = -1)
{
пункт = очередь;
если (спереди == сзади)
{
фронт = -1;
тыл = -1;
}
еще
{
спереди = спереди + 1;
f («Удалено число =% d», элемент);
}
}
еще
{
f («очередь пуста»);
}
}

Приложения стека

• Разбор в компиляторе.
• Виртуальная машина Java.
• Отменить в текстовом редакторе.
• Кнопка «Назад» в веб-браузере.
• Язык PostScript для ers.
• Реализация вызовов функций в компиляторе.

Приложения очереди

• Буферы данных
• Асинхронная передача данных (файловый ввод-вывод, каналы, сокеты).
• Распределение запросов по общему ресурсу (например, процессор).
• Анализ трафика.
• Определите количество кассиров в супермаркете.

Вывод

Stack и Queue - это линейные структуры данных, отличающиеся определенными способами, такими как рабочий механизм, структура, реализация, варианты, но оба они используются для хранения элементов в списке и выполнения операций в списке, таких как добавление и удаление элементов. Хотя есть некоторые ограничения простой очереди, которая возмещается с использованием других типов очереди.