Реализация очередей в массиве


$\scriptstyle{\blacktriangleright}$ 6.2.1. Реализовать операции с очередью ограниченной длины так, чтобы количество действий для каждой операции было ограничено константой, не зависящей от длины очереди.

 

Решение. Будем хранить элементы очереди в соседних элементах массива. Тогда очередь будет прирастать справа и убывать слева. Поскольку при этом она может дойти до края, свернем массив в окружность.

Введем массив 

        Содержание: array [0..n-1] of T
и переменные 
        Первый: 0..n-1,
        Длина : 0..n.
При этом элементами очереди будут

    Содержание [Первый], Содержание [Первый + 1],...,

Содержание [Первый+Длина-1],     

где сложение выполняется по модулю n. (Предупреждение. Если вместо этого ввести переменные Первый и Последний, значения которых -- вычеты по модулю n, то пустая очередь может быть спутана с очередью из n элементов.)


Операции выполняются так:


Сделать пустой: 

        Длина := 0;
        Первый := 0;

Добавить элемент: 

        {Длина < n}
        Содержание [(Первый + Длина) mod n] := элемент;
        Длина := Длина + 1;

Взять элемент: 

        {Длина > 0}
        элемент := Содержание [Первый];
        Первый := (Первый + 1) mod n;
        Длина := Длина - 1;

Пуста: 

        Длина = 0

Очередной: 

        Содержание [Первый]\


$\scriptstyle{\blacktriangleright}$ 6.2.2. (Сообщил А.Г. Кушниренко) Придумать способ моделирования очереди с помощью двух стеков (и фиксированного числа переменных типа T). При этом отработка n операций с очередью (начатых, когда очередь была пуста) должна требовать порядка n действий.

  

Решение. Инвариант: стеки, составленные концами, образуют очередь. (Перечисляя элементы одного стека вглубь и затем элементы второго наружу, мы перечисляем все элементы очереди от первого до последнего.) Ясно, что добавление сводится к добавлению к одному из стеков, а проверка пустоты -- к проверке пустоты обоих стеков. Если мы хотим взять элемент, есть два случая. Если стек, где находится начало очереди, не пуст, то берем из него элемент. Если он пуст, то предварительно переписываем в него все элементы второго стека, меняя порядок (это происходит само собой при перекладывании из стека в стек) и сводим дело к первому случаю. Хотя число действий на этом шаге и не ограничено константой, но требование задачи выполнено, так как каждый элемент очереди может участвовать в этом процессе не более одного раза.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 6.2.3. Деком называют структуру, сочетающую очередь и стек: класть и забирать элементы можно с обоих концов. Как реализовать дек ограниченного размера на базе массива так, чтобы каждая операция требовала ограниченного числа действий?$\scriptstyle\blacktriangleleft$

 


$\scriptstyle{\blacktriangleright}$ 6.2.4. (Сообщил А.Г. Кушниренко.) Имеется дек элементов типа T и конечное число переменных типа T и целого типа. В начальном состоянии в деке некоторое число элементов. Составить программу, после исполнения которой в деке остались бы те же самые элементы, а их число было бы в одной из целых переменных.

 

[Указание. (1) Элементы дека можно циклически переставлять, забирая с одного конца и помещая в другой. После этого, сделав столько же шагов в обратном направлении, можно вернуть все на место. (2) Как понять, прошли мы полный круг или не прошли? Если бы какой-то элемент заведомо отсутствовал в деке, то можно было бы его подсунуть и ждать вторичного появления. Но таких элементов нет. Вместо этого можно для данного n выполнить циклический сдвиг на n дважды, подсунув разные элементы, и посмотреть, появятся ли разные элементы через n шагов.]$\blacktriangleleft$


pvv
1/8/1999