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