В чем разница между стеком и очередью

Очередь и стек — Основы алгоритмов и структур данных

Мы привыкли записывать математические выражения, опираясь на приоритет операций и на скобки. Именно поэтому:

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

Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.

Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript.

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

Обычная запись — , обратная —
Обычная запись — , обратная —

Операторы в обратной записи не всегда должны быть в конце. Например,

можно записать так:

Эта запись читается слева направо и воспринимается так:

Число
Число
Операция сложения
Число
Число
Операция сложения
Операция умножения

Преимущество обратных выражений в том, что они не вызывают разночтения.

Чтобы разобраться на примере, дальше мы пошагово вычислим это выражение:

Шаг 1. Берем из стопки два верхних числа —

. Выполняем над ними первую операцию — сложение:

Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:

Шаг 3. Вспомним изначальное выражение:

Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:

Шаг 4. Проводим последнюю операцию и получаем результат:

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

В программировании такие стопки называются стеком — от английского stack, то есть стопка или кипа.

В стеке, как и в стопке, мы имеем дело только с верхней карточкой — вершиной. Задача, которую решает стек — запомнить промежуточный результат для будущих вычислений.

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

Реализация стека через массив

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

Разные реализации могут быть непохожи друг на друга, но мы всегда ожидаем найти основные методы — конечно, у разных структур они разные. У стека должны быть реализованы три обязательных метода:

Метод push() помещает элемент на вершину стека, как карточку наверх стопки
Метод pop() убирает элемент с вершины и возвращает его
Метод isEmpty() проверяет, пуст ли стек

В JavaScript методы push() и pop() уже присутствуют в массиве, поэтому мы можем использовать их как есть:

class Stack  items = []; push(value)  this.items.push(value); > pop()  return this.items.pop(); > isEmpty()  return this.items.length == 0; > >

class Stack: items = [] def push(self, value): self.items.append(value) def pop(self): return self.items.pop() def is_empty(self): return len(self.items) == 0

php class Stack  public $items = []; public function push($value)  array_push($this->items, $value); > public function pop()  return array_pop($this->items); > public function isEmpty()  return count($this->items) == 0; > >

class Stack  List items = new ArrayList<>(); public T> void push(T item)  items.add(item); > public T> T pop()  var lastElementIndex = items.size() - 1; var lastElement = (T) items.get(lastElementIndex); items.remove(lastElementIndex); return lastElement; > public boolean isEmpty()  return items.isEmpty(); > >

Метод isEmpty() возвращает true , потому что массив пуст — содержит

Воспользуемся нашим стеком, чтобы вычислить значение выражения

let stack = new Stack(); const expression = '3 2 + 4 5 + *'; const lexems = expression.split(' '); for (lexem of lexems)  let a; let b; switch (lexem)  case '+': b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case '-': b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case '*': b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case '/': b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(parseFloat(lexem)); > > console.log(stack.pop()); // 45

stack = Stack() expression = '3 2 + 4 5 + *' lexems = expression.split(' ') for lexem in lexems: # В Python версии 3.10 и выше возможно использовать конструкцию match/case, но в данном случае рассмотрим реализацию через if/else if lexem == '+': a = stack.pop() b = stack.pop() stack.push(a + b) elif lexem == '-': a = stack.pop() b = stack.pop() stack.push(a - b) elif lexem == '*': a = stack.pop() b = stack.pop() stack.push(a * b) elif lexem == '': a = stack.pop() b = stack.pop() stack.push(a / b) else: stack.push(float(lexem)) print(stack.pop()) # 45

php $stack = new Stack(); $expression = '3 2 + 4 5 + *'; $lexems = explode(' ', $expression); foreach ($lexems as $lexem)  $a; $b; switch ($lexem)  case '+': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a + $b); break; case '-': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a - $b); break; case '*': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a * $b); break; case '/': $b = $stack->pop(); $a = $stack->pop(); $stack->push($a / $b); break; default: $stack->push(floatval($lexem)); > > print_r($stack->pop()); // 45

var stack = new Stack(); var expression = "3 2 + 4 5 + *"; String[] lexems = expression.split(" "); for (String lexem : lexems)  float a; float b; switch (lexem)  case "+": b = stack.pop(); a = stack.pop(); stack.push(a + b); break; case "-": b = stack.pop(); a = stack.pop(); stack.push(a - b); break; case "*": b = stack.pop(); a = stack.pop(); stack.push(a * b); break; case "/": b = stack.pop(); a = stack.pop(); stack.push(a / b); break; default: stack.push(Float.parseFloat(lexem)); > > stack.pop(); // 45

Как видите, решение не очень сложное. Мы разбиваем строку с выражением на лексемы и обрабатываем каждую лексему в цикле.

Если лексема — это знак операции, то мы «снимаем» с вершины стека два числа, выполняем операцию и помещаем результат обратно на стек.

При выполнении операций важно обращать внимание на порядок чисел. Числа в стеке расположены в порядке, обратном тому, в котором мы их туда помещали. Поэтому сначала мы извлекаем второй операнд b , а потом первый a .

Порядок операндов не важен для таких операций, как сложение и умножение, потому что

. Но при делении это уже не так —

Помогите разобраться в разнице между очередями и стекам

Вопрос: Вроде-бы PriorityQueue и LinkedList ее реализации в коллекциях java. А другие есть? Или по другому: Можно ли сказать что любая коллекция которая дает возможность получить элементы в порядке их добавления это Queue , или только эти две? 2.

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

Вопрос: Вот это совсем не понятно это по типу как замкнутый двунаправленный связанный список? Что это? Не понятна идея и какую проблему она решает. 3.

И есть стек — тут можно получить только последний элемент.

Вопрос: Вроде у List есть реализация Stack она вроде как отражает эту идею. А еще есть реализации? А какую проблему этот механизм решает? Вот запутался немного, помогите разобраться что для чего нужно, и какие реализации имеет. Спасибо.

Отслеживать
задан 15 мар 2017 в 0:14
5,267 11 11 золотых знаков 56 56 серебряных знаков 115 115 бронзовых знаков

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

Очередь — это как конвейер. С одной стороны кладешь, с другой забираешь.

Стек — как обойма пистолета, что последним кладешь, то первым забираешь.

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

К спискам (в них можно получить любой элемент) никакого отношения не имеет, в очередях и стеках можно получить только либо первый положенный, либо последний. Также внести можно только либо в начало, либо в конец. Элементы, находящиеся внутри стека/очереди не доступны, пока не окажутся на вершине (элементы попавшие туда до них не будут извлечены). Так же от списков отличает то, что если положить в список первый элемент, то сколько его не получай потом, он будет первый. В очереди/стеке при извлечении мы движемся по поступавшим ранее и извлекая первый, получаем все (в порядке поступления)

Нужны эти инструменты как некий буфер для временного хранения, в основном. То есть у вас поступает какая то информация, вы ее складываете в этот стек/очередь, а потом обрабатываете, либо в порядке поступления первые первыми — очередь, либо последние первыми — стек.

Почитать с картинками можно статьи, вроде этой, здесь о самостоятельной реализации, но принцип хорошо описан «изнутри».

Структуры данных

(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:

push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)

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

Объявим структуру данных типа stack .

const int MAX_SIZE=1000;

struct stack int m_size; // Количество элементов в стеке
int m_elems[MAX_SIZE]; // Массив для хранения элементов

stack(); // Конструктор
~stack(); // Деструктор
void push(int d); // Добавить в стек новый элемент
int pop(); // Удалить из стека последний элемент
// и вернуть его значение
int back(); // Вернуть значение последнего элемента
int size(); // Вернуть количество элементов в стеке
void clear(); // Очистить стек
>;

Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0.. m_size-1 . Элементы, добавленные позже, получают большие номера.

Упражнение A — простой стек

Реализуйте структуру данных «стек», реализовав все указанные здесь методы. Напишите программу (функцию main ), содержащую описание стека и моделирующую работу стека. Функция main считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения одной команды программа должна вывести одну строчку. Возможные команды для программы:

push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение.
back Программа должна вывести значение последнего элемента, не удаляя его из стека.
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop_back и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Пример протокола работы программы

Ввод Вывод

push 2 ok
push 3 ok
push 5 ok
back 5
size 3
pop 5
size 2
push 7 ok
pop 7
clear ok
size 0
exit bye

Упражнение B — стек с обработкой ошибок

Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back и pop . Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop , при этом стек пуст, то программа должна вместо числового значения вывести строку error .

При этом должна быть реализована двойная защита: вызов методов forward и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_elems , а функция main должна выводить сообщение error , при считывании некорректной операции.

Пример протокола работы программы

Ввод Вывод

push 2 ok
back 2
pop 2
size 0
pop error
push 1 ok
size 1
exit bye

Упражнение C — стек без ограничения на размер

Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод push размер динамического массива, отведенного для хранения стека, должен увеличиваться.

Очередь

Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Описание структуры очередь:

const int MAX_SIZE=1000;

struct queue int m_size; // Количество элементов в очереди
int m_start; // Номер элемента, с которого начинается очередь
int m_elems[MAX_SIZE]; // Массив для хранения элементов

queue(); // Конструктор
~queue(); // Деструктор
void push(int d); // Добавить в очередь новый элемент
int pop(); // Удалить из очереди первый элемент
// и вернуть его значение
int front(); // Вернуть значение первого элемента
int size(); // Вернуть количество элементов в очереди
void clear(); // Очистить очередь
>;

Упражнение D — простая очередь

Реализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции back , которая заменена операцией front . Операции front и pop всегда корректны.

Упражнение E — очередь с обработкой ошибок

Аналогично заданию B, но для очереди. Операции front и pop могут быть некорректными, в этом случае необходимо вывести error .

Программа должна содержать «двойную защиту» от некорректных операций: как в функции main , так и в самих методах pop и front .

Упражнение F — очередь без ограничений на размер

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

Дек

Деком (англ. – аббревиатура от double-ended queue , двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)

Упражнение G — простой дек

Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front , pop_back , front , back всегда корректны.

Упражнение H — дек с обработкой ошибок

Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error .

Упражнение I — дек неограниченного размера

Аналогично заданиям C и F, но для дека. Необходимо увеличивать размер дека при увеличении числа элементов в нем. При выполнении некорректных операций необходимо вывести error .

Что такое стек и очередь?

Эти слова очень часто встречается в документации, прилагаемой к различным программным продуктам. Однако людям, далёким от программирования и имеющим гуманитарный склад ума, довольно сложно порой самостоятельно дойти до ответа на вопрос, что же скрывается за этими названиями. Техническим писателям, конечно, стоило бы объяснять подробнее подобные термины, но, увы, они себя редко этим утруждают. «Компьютерные вести» со своей традиционной рубрикой «F.A.Q.» спешат, как всегда, на помощь.

Начнём издалека — так, на мой взгляд, будет понятнее. В программировании очень часто приходится оперировать с коллекциями каких-либо объектов — фактически, почти всегда, когда объектов больше одного. Эти объекты могут иметь самую разную природу — ими могут быть файлы, записи в базе данных или даже отдельные буквы. В зависимости от того, как происходит добавление и извлечение элементов для этой коллекции, выделяют разные типы коллекций. Стеком называется такая коллекция объектов, из которой вынимается в первую очередь последний добавленный объект. Очередь же — это коллекция объектов, в которой, напротив, первыми извлекаются объекты, первыми в неё и добавленными.

Для обозначения очереди в программистском жаргоне есть специальный «умный» термин — FIFO. Это аббревиатура от английской фразы «first in, first out», т.е. «первый вошёл — первый вышел». Для обозначения стека используют другую аббревиатуру — LIFO, то есть, «last in, first out», или «последний вошёл — первый вышел». Простейший пример очереди в реальной жизни, в общем-то, найти несложно — это и есть очередь в кассу магазина. Пример стека — это стопка бумаги, в которой обязательно первым берётся именно тот лист, который был положен в неё последним.

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