Стек и Очередь, Почему?

Question

Почему и когда я должен использовать структуры данных стека или очереди вместо массивов / списков? Не могли бы вы показать пример для состояния, которое будет лучше, если вы будете использовать стек или очередь?

Answer 1

Вы были в кафетерии, верно? и видел стопку тарелок? Когда чистая тарелка добавляется в стопку, она ставится сверху. Когда пластина удалена, это удалено от вершины. Так что это называется «первым пришел-первым вышел» (LIFO). Компьютерный стек подобен этому, за исключением того, что он содержит числа, и вы можете сделать их из массива или списка, если хотите. (Если под стопкой тарелок есть пружина, они говорят, что вы «толкаете» одну сверху, а когда вы удаляете одну, вы «высовываете» ее. Вот откуда эти слова.)

В кафетерии зайдите обратно, где они моют посуду. У них есть конвейерная лента, куда они кладут тарелки для мытья с одного конца, а они выходят с другого конца в том же порядке. Это очередь или «первым пришел - первым обслужен» (FIFO). Вы также можете сделать один из них из массива или списка, если хотите.

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

Один из способов - пройти в глубину . Вы начинаете с ствола и идете к первой ветви, а затем идете к первой ветви этой ветви и так далее, пока не доберетесь до листа и распечатаете его. Но как вы можете вернуться к следующей ветке? Что ж, каждый раз, когда вы переходите по ветке, вы «выталкиваете» некоторую информацию из своего стека, а когда вы делаете резервную копию, вы «выталкиваете» ее обратно, и это говорит вам, какую ветку выбрать следующей. Вот как вы отслеживаете, какую ветку делать дальше в каждой точке.

Другой способ - это прогулка в ширину . Начиная со ствола, вы нумеруете все ветви со ствола и помещаете эти числа в очередь. Затем вы берете число с другого конца, переходите к этой ветви, и для каждой ветви, выходящей из it , вы снова нумеруете их (последовательно с первым) и помещаете их в очередь. Продолжая это делать, вы сначала посетите ветки, которые находятся на расстоянии 1 ветки от ствола. Затем вы собираетесь посетить все ветви, которые находятся на расстоянии 2 веток от ствола, и так далее. В конце концов вы доберетесь до листьев и сможете распечатать их.

Это две очень основные концепции в программировании.

Answer 2

Потому что они помогают управлять вашими данными более особым образом, чем массивы и списки.

Очередь «первым пришел, первым вышел» (FIFO)

Стек - последний пришел, первый вышел (LIFO)

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

Answer 3

1. Используйте очередь, когда хотите вывести вещи в том порядке, в котором вы их поместили.
2. Используйте стек, когда вы хотите получить вещи в обратном порядке, чем вы положили их.
3. Используйте список, когда вы хотите получить что-нибудь, независимо от того, когда вы его вставили (и когда вы не хотите, чтобы они автоматически удалялись).

Answer 4

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

Answer 5

Помимо принудительного использования, о котором уже упоминали другие, существует также проблема с производительностью. Когда вы хотите удалить что-либо из начала массива или списка (ArrayList), это обычно занимает O (n) времени, но для очереди это занимает O (1) времени. Это может иметь огромное значение, если есть много элементов.

Answer 6

Массивы / списки и стеки / очереди не являются взаимоисключающими понятиями. Фактически, любые стеки или реализации очередей, которые вы найдете, почти наверняка используют либо массивы, либо списки изнутри.

Структуры массивов и списков предоставляют описание того, как хранятся данные, что гарантирует сложность фундаментальных операций над структурами.

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

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

Answer 7

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

Answer 8

Стек и Очередь - это более продвинутые способы обработки коллекции, чем сам массив, который не устанавливает порядок поведения элементов внутри коллекции.

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

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

Answer 9

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

Answer 10

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

Вы можете «свернуть свое», если хотите, или воспользоваться уже реализованной абстракцией.