Стек против очереди
Стек - это упорядоченный список, в котором вставка и удаление элементов списка может выполняться только на одном конце, называемом вершиной. По этой причине стек считается структурой данных «последним пришел - первым вышел» (LIFO). Очередь также представляет собой упорядоченный список, в котором вставка элементов списка выполняется на одном конце, называемом задним, а удаление элементов выполняется на другом конце, называемом передним. Этот механизм вставки и удаления делает очередь структурой данных First in First Out (FIFO).
Что такое стек?
Как упоминалось ранее, стек - это структура данных, в которой элементы добавляются и удаляются только с одного конца, называемого вершиной. Стеки допускают только две основные операции, называемые push и pop. Операция push добавляет новый элемент на вершину стека. Операция pop удаляет элемент из вершины стека. Если стек уже заполнен, при выполнении операции push это считается переполнением стека. Если операция извлечения выполняется с уже пустым стеком, это считается потерей значимости стека. Из-за небольшого количества операций, которые могут быть выполнены со стеком, он считается ограниченной структурой данных. Кроме того, согласно тому, как определены операции push и pop, становится ясно, что элементы, которые были добавлены в стек последними, уходят из стека первыми. Поэтому стек считается структурой данных LIFO.
Что такое очередь?
В очереди элементы добавляются из конца очереди и удаляются из начала очереди. Поскольку элементы, добавленные первыми, будут удалены из очереди первыми, сохраняется порядок FIFO. Из-за такого порядка добавления и удаления элементов очередь представляет собой линию оформления заказа. Общие операции, поддерживаемые очередью, - это операции включения в очередь и удаления из очереди. Операция включения в очередь добавит элемент в конец очереди, а операция удаления из очереди удалит элемент из начала очереди. Как правило, очереди не имеют ограничений на количество элементов, которые могут быть добавлены в очередь, помимо ограничений памяти.
В чем разница между стеком и очередью?
Несмотря на то, что и стеки, и очереди являются разновидностью упорядоченных списков, у них есть некоторые важные отличия. В стеках добавление или удаление элементов может выполняться только с одного конца, называемого верхним, в то время как в очередях добавление элементов выполняется с одного конца, называемого задним, а удаление элементов выполняется с другого конца, называемого передним. В стеке элементы, которые добавляются в стек последними, будут удалены из стека первыми. Поэтому стек рассматривается как структура данных LIFO. В очередях элементы, добавленные первыми, будут первыми удалены из очереди. Поэтому очередь считается структурой данных FIFO.
Ссылка по теме:
Разница между стеком и кучей
