С другой стороны, в стеке открыт только один конец для перемещения и извлечения элементов данных. В очереди имеются открытые оба конца для постановки в очередь и удаления из очереди элементов данных.
Стек и очередь - это структуры данных, используемые для хранения элементов данных, и фактически они основаны на каком-то реальном эквиваленте. Например, стопка - это стопка компакт-дисков, где вы можете извлечь и вставить компакт-диск через верх стопки компакт-дисков. Аналогично, очередь представляет собой очередь для билетов в театр, где человек, стоящий на первом месте, т. Е. Сначала будет обслужен фронт очереди, а прибывающий новый человек появится в задней части очереди (задний конец очереди).
Сравнительная таблица
| Основа для сравнения | стек | Очередь |
|---|---|---|
| Принцип работы | LIFO (последний пришел первым вышел) | FIFO (первый на первом) |
| Состав | Тот же конец используется для вставки и удаления элементов. | Один конец используется для вставки, т. Е. Задний конец, а другой конец используется для удаления элементов, т. Е. Передний конец. |
| Количество использованных указателей | Один | Два (в простом случае очереди) |
| Выполненные операции | Push и Pop | Ставить в очередь и оставлять в очередь |
| Экспертиза пустого состояния | Топ == -1 | Фронт == -1 || Фронт == Тыл + 1 |
| Экспертиза полного состояния | Топ == Макс - 1 | Задний == Макс - 1 |
| Варианты | У него нет вариантов. | У этого есть варианты как круговая очередь, приоритетная очередь, дважды законченная очередь. |
| Реализация | Simpler | Сравнительно сложный |
Определение стека
Стек - это не примитивная линейная структура данных. Это упорядоченный список, в который добавляется новый элемент, а существующий элемент удаляется только с одного конца, называемого вершиной стека (TOS). Поскольку все удаление и вставка в стек выполняется с вершины стека, последний добавленный элемент будет первым, который будет удален из стека. По этой причине стек называется списком типа «последний пришел - первым обслужен» (LIFO).
Обратите внимание, что элемент, к которому часто обращаются в стеке, является самым верхним элементом, тогда как последний доступный элемент находится в нижней части стека.
пример
Некоторые из вас могут есть печенье (или Поппинс). Если вы предполагаете, порвана только одна сторона крышки, и печенье вынимается одна за другой. Это то, что называется хлопаньем, и аналогичным образом, если вы хотите сохранить печенье в течение некоторого времени позже, вы положите его обратно в пачку через тот же порванный конец, называемый толканием.
Определение очереди
Очередь с линейной структурой данных относится к категории непримитивного типа. Это коллекция элементов подобного типа. Добавление новых элементов происходит на одном конце, называемом задним концом. Точно так же удаление существующих элементов происходит на другом конце, называемом Front-end, и это логически тип списка «первым пришел - первым обслужен» (FIFO).
пример
В нашей повседневной жизни мы сталкиваемся со многими ситуациями, когда нам приходится ждать желаемого обслуживания, и мы вынуждены стоять в очереди на обслуживание своей очереди. Эту очередь ожидания можно рассматривать как очередь.
Ключевые различия между стеком и очередью
- Стек следует за механизмом LIFO с другой стороны. Очередь следует за механизмом FIFO для добавления и удаления элементов.
- В стеке один и тот же конец используется для вставки и удаления элементов. Напротив, два разных конца используются в очереди для вставки и удаления элементов.
- Поскольку в стеке есть только один открытый конец, это является причиной использования только одного указателя для ссылки на вершину стека. Но очередь использует два указателя для ссылки на передний и задний конец очереди.
- Стек выполняет две операции, известные как push и pop, а в очереди его называют enqueue и dequeue.
- Реализация стека проще, тогда как реализация очереди сложна.
- Очередь имеет варианты, такие как круговая очередь, приоритетная очередь, очередь с двойным окончанием и т. Д. В отличие от стека нет вариантов.
Реализация стека
Стек может быть применен двумя способами:
- Статическая реализация использует массивы для создания стека. Статическая реализация, хотя и является легким методом, но не гибким способом создания, так как объявление размера стека должно быть сделано во время разработки программы, после чего размер не может быть изменен. Кроме того, статическая реализация не очень эффективна в отношении использования памяти. Поскольку массив (для реализации стека) объявляется до начала операции (во время разработки программы). Теперь, если количество элементов, подлежащих сортировке, в стеке очень мало, статически выделенная память будет потрачена впустую. С другой стороны, если в стеке будет храниться больше элементов, мы не сможем изменить размер массива, чтобы увеличить его емкость, чтобы он мог вместить новые элементы.
- Динамическая реализация также называется представлением связанного списка и использует указатели для реализации стекового типа структуры данных.
Реализация очереди
Очередь может быть реализована двумя способами:
- Статическая реализация : если очередь реализована с использованием массивов, точное количество элементов, которые мы хотим сохранить в очереди, должно быть заранее определено, поскольку размер массива должен быть объявлен во время разработки или до начала обработки. В этом случае начало массива станет передней частью очереди, а последнее местоположение массива будет действовать в качестве задней части очереди. Следующее отношение дает всем элементам, существующим в очереди, при реализации с использованием массивов:
спереди - сзади + 1
Если задний <front>, то в очереди не будет элементов, или очередь всегда будет пустой. - Динамическая реализация . При реализации очередей с использованием указателей основным недостатком является то, что узел в связанном представлении потребляет больше памяти, чем соответствующий элемент в представлении массива. Поскольку в каждом узле имеется по меньшей мере два поля, одно для поля данных, а другое для хранения адреса следующего узла, тогда как в связанном представлении присутствует только поле данных. Преимущество использования связанного представления становится очевидным, когда требуется вставить или удалить элемент в середине группы других элементов.
Операции над стеком
Основные операции, которые могут выполняться в стеке:
- PUSH : когда новый элемент добавляется на вершину стека, называется операцией PUSH. Нажатие элемента в стеке вызывает добавление элемента, так как новый элемент будет вставлен сверху. После каждой операции толчка верх увеличивается на единицу. Если массив заполнен и новый элемент не может быть добавлен, это называется условием STACK-FULL или STACK OVERFLOW. РАБОТА С НАЖИМОМ - функция в С:
Учитывая стек объявлен как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");}} - POP : когда элемент удаляется из верхней части стека, он называется операцией POP. Стек уменьшается на единицу после каждой операции pop. Если в стеке не осталось элемента и выполняется всплывающее окно, это приведет к условию STACK UNDERFLOW, означающему, что ваш стек пуст. POP OPERATION - функции в 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");}}
Операции в очереди
Основные операции, которые могут быть выполнены в очереди:
- Постановка в очередь : для вставки элемента в очередь. Операция постановки в очередь в C:
Очередь объявлена как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") ;}} - Исключение : Для удаления элемента из очереди. Функция операции извлечения в C:
Очередь объявлена как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") ;}}
Приложения стека
- Разбор в компиляторе.
- Виртуальная машина Java.
- Отменить в текстовом редакторе.
- Кнопка «Назад» в веб-браузере.
- Язык PostScript для принтеров.
- Реализация вызовов функций в компиляторе.
Приложения очереди
- Буферы данных
- Асинхронная передача данных (файловый ввод-вывод, каналы, сокеты).
- Распределение запросов по общему ресурсу (принтер, процессор).
- Анализ трафика.
- Определите количество кассиров в супермаркете.
Заключение
Stack и Queue - это линейные структуры данных, отличающиеся определенными способами, такими как рабочий механизм, структура, реализация, варианты, но оба они используются для хранения элементов в списке и выполнения операций в списке, таких как добавление и удаление элементов. Хотя есть некоторые ограничения простой очереди, которая возмещается с использованием других типов очереди.
