Очередь и стек

Реализация многомерных массивов

Двумерные таблицы могут быть реализованы различным образом:

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

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

Реализация многомерных таблиц осуществляется аналогично.

Очередь – это последовательность элементов одного и того же типа, к которой добавление и удаление элементов происходит только с одного из концов.

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

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

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

Ограниченные очереди и стеки достаточно легко реализуются через вектор, неограниченные - через список.

Стеки широко используются в задачах синтаксического анализа. Также они используются при вызове подпрограмм для сохранения контента вызывающей программы.