Билет 9. Стеки

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

Стеки организованы по принципу LIFO- «Последним пришел – первым вышел».

Операции на стеками:

• push(x) – «втолкнуть» элемент в список

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

• x=pop(x) – взять элемент из списка

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

Стеки используются для сохранения локальных переменных. адреса возврата и т.д.

Реализация стека:

• линейный список, сложность операций О(1)

• Массив

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.

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

Билет 10.Очереди

Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.

Организуются по принципу FIFO «Первым пришел – первым вышел». Данная структура не имеет фиксированного размера. Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Операции:

• put(x); - поставить элемент в очередь

Занесение элемента в очередь реализуется как добавлению элемента в конец списка.

• x=get(); - взять элемент из очереди

Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка.

Реализация очереди:

• Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка изn всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

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