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

Front-end-Job-Interview-Questions

Ответы на вопросы на должность Frontend разработчика.

Project maintained by FedorovAlexander Hosted on GitHub Pages — Theme by mattgraham

Что такое цикл событий (event loop)? В чём разница между стеком вызовов (call stack) и очередью событий (task queue)?

Цикл событий — это однопоточный цикл, который контролирует стек вызовов и проверяет, есть ли какая-либо работа, которую необходимо выполнить в очереди задач. Если стек вызовов пуст и в очереди задач есть callback-функции, то функция удаляется из очереди и помещается с стек вызовов для выполнения.

Stack — “первым пришел, последним вышел” или “последним пришел, первым вышел”, что то же самое.
Queue — “первым пришел, первым ушел”.

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

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

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

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

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

Простейшие структуры данных: стек, очередь, дек

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

По определению, структура данных — способ представления данных в памяти, позволяющий эффективно выполнять с ними определённый набор операций. Например, простой массив лучше всего подходит для частого обращения к элементам по индексам и их изменению. А удаление элемента из середины массива работает за \(O(N)\). Если вам для решения задачи нужно часто удалять элементы, то придётся воспользоваться другой структурой данной. Например, бинарное дерево ( std::set ) позволяет делать это за \(O(\log N)\), но не поддерживает работу с индексами, только поочерёдный обход всех элементов и поиск по значению (тоже за \(O(\log N)\)).

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

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

Стек

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

Добавить элемент в стек (Сложность: \(O(1)\))
Извлечь элемент из стека (Сложность: \(O(1)\))
Проверить, пуст ли стек (Сложность: \(O(1)\))

Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.

Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

struct stack  int a[1000]; int head = -1; //Индекс крайнего элемента. void push(int x)  head++; a[head] = x; > int pop()  if (head != -1)  head--; return a[head + 1]; > else  //Ошибка, попытка извлечь элемент из пустого стека. > > bool is_empty()  return head == -1; > >;

Как видите, для реализации стека хватает одного массива и одного указателя, обозначающего крайний элемент.

Очередь

Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.

Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

struct queue  int a[1000]; //Для более лаконичной реализации работы, мы будем //хранить указатель не на последний элемент, а //на следующий за ним (несуществующий). //Это, в частности, позволит нам проверять очередь на пустоту //простым условием head == tail int head = 0; //Индекс первого элемента. int tail = 0; //Индекс элемента, следующего за последним. void push(int x)  a[tail] = x; tail++; > int pop()  if (head != tail)  head++; return a[head - 1]; > else  //Ошибка, попытка извлечь элемент из пустой очереди. > > bool is_empty()  return head == tail; > >;

При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.

Дек

Структура, объединяющая стек и очередь, называется дек (англ. deque - сокращение от double-ended queue, очередь с двумя концами). Как можно догадаться, она поддерживает уже знакомый набор операций:

Добавить элемент в начало дека (Сложность: \(O(1)\))
Извлечь элемент из начала дека (Сложность: \(O(1)\))
Добавить элемент в конец дека (Сложность: \(O(1)\))
Извлечь элемент из конца дека (Сложность: \(O(1)\))
Проверить, пуст ли дек (Сложность: \(O(1)\))

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

struct deque  int a[2000]; //Используя такие начальные значения индексов, у нас //будет свободная память как слева, так и справа. int head = 1000; //Индекс первого элемента. int tail = 1000; //Индекс элемента, следующего за последним. void push_front(int x)  head--; a[head] = x; > void push_back(int x)  a[tail] = x; tail++; > int pop_front()  if (head != tail)  head++; return a[head - 1]; > else  //Ошибка, попытка извлечь элемент из пустого дека. > > int pop_back()  if (head != tail)  tail--; return a[tail]; > else  //Ошибка, попытка извлечь элемент из пустого дека. > > bool is_empty()  return head == tail; > >;

Стек, очередь и дек в стандартной библиотеке C++

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

stackint> s; //создание стека s.push(5); //добавление элемента cout  <s.top(); //обращение к верхнему элементу if (!s.empty())  //проверка на пустоту s.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) > queueint> q; //создание очереди q.push(5); //добавление элемента cout  <q.front()  <' '  <q.back(); //обращение к первому и последнему элементам if (!q.empty())  //проверка на пустоту q.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) >

С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за \(O(1)\). Он поддерживает все операции, поддерживаемые классом std::vector , в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.

Более сложные структуры данных

Приведённый выше материал мог вызвать у вас лёгкое недоумение и сомнения в целесообразности всех этих ограничений на обычные массивы. На самом деле, стек, очередь и дек являются лишь простейшими примерами структур данных, не предоставляющими выгоды в скорости выполнения операций. Серьёзным структурам данных посвящены отдельные темы. Стек, очередь и дек призваны проиллюстрировать, что главными характеристиками структуры данных являются набор поддерживаемых операций и скорость их выполнения.

brestprog

Олимпиадное программирование в Бресте и Беларуси

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

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

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

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

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

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

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

3 ответа 3

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

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

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

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

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

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

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