Использование стека и очереди?

Question

Я читаю структуры данных и вижу стек и очередь, но у меня недостаточно примеров в компьютерных системах, в веб-разработке или в конкретных проблемах, где я должен использовать стек, очередь или дерево и т. Д.

Answer 1

Стеки используются большинством (всех?) Языков программирования для отслеживания состояния программы при вызове подпрограмм.

Объяснение : код вашей программыхранится в основной памяти.CPU имеет указатель инструкций, который всегда указывает на следующую инструкцию, которая будет выполнена.Когда инструкция выполнена, этот указатель увеличивается на единицу, чтобы указывать на следующую инструкцию.

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

Это также причина, по которой чрезмерная рекурсия может привести к переполнению стека.Слишком много вложенных вызовов приводит к тому, что в стек помещается много адресов возврата, но ни один из них не удаляется.

Подробнее о Википедия .

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

Answer 2

Очереди обычны везде, где нужно что-то обрабатывать по принципу «первым пришел - первым обслужен».Сетевые пакеты, запросы ввода / вывода и т. Д.

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

Answer 3

Queue - First In First Out, используется для последовательной обработки данных.Может использоваться для обработки задач в порядке их постановки в очередь.Стек - это противоположность очереди - наиболее часто используемый пример - очередь «первым пришел - первым обслужен».

Answer 4

В стеке удаление и вставка выполняются на одном конце.Так оно называется «Последний вошел - первый вышел».В стеке используется только один указатель, называемый TOP. Нет потерь пространства памяти

В очереди удаление и вставка выполняются на двух концах.Итак, это называется First In First Out.В очереди два указателя, называемые FRONT и REAR.Wastage пространства памяти.