Стек, очередь, дек1 Структуры и алгоритмы обработки данных, 1 Лекция 4 Линейные СД Стек, очередь, дек

Стек, очередь, дек2 Абстракция (модель) последовательности Функции над последовательностями: First, Last, Rest, Lead, Prefix, Postfix Тип последовательности Sequence (El) w = [ x 1, x 2,..., x n ] из элементов x i типа El Для непустых последовательностей (w ): First: Sequence (El) El; First (w) = x 1 ; Last: Sequence (El) El; Last (w) = x n ; Rest: Sequence (El) Sequence (El); Rest (w) = [ x 2,..., x n ]; Lead: Sequence (El) Sequence (El); Lead (w) = [ x 1, x 2,...,x n 1 ].

Стек, очередь, дек3 Наглядная модель

Стек, очередь, дек4 Функции Prefix и Postfix определены для любых последовательностей: Prefix: El Sequence (El) Sequence (El); Postfix: Sequence (El) El Sequence (El); Prefix (x 0, w) = [ x 0, x 1, x 2,..., x n ]; Postfix (w, x) = [ x 1, x 2,..., x n, x ]. Функции First, Rest, Last, Lead селекторы, а функции Prefix и Postfix конструкторы типа Sequence (El) Абстракция (модель) последовательности

Стек, очередь, дек5 Подструктуры Sequence (El) стек (или магазин) Stack First, Rest, Prefix Last, Lead, Postfix очередь (англ. queue) First, Rest, Postfix Last, Lead, Prefix дек (от англ. deq = double-ended-queue, «очередь с двумя концами») First, Rest, Last, Lead, Postfix, Prefix

Стек, очередь, дек6 СД PrefixPostfixFirstLastRestLeadNull deq stack queue Подструктуры Sequence (El)

Стек, очередь, дек7 «Железнодорожные разъезды». Дек First Postfix Last Prefix 123nn – 1 1

Стек, очередь, дек8 «Железнодорожные разъезды». Стек Prefix First Last Postfix

Стек, очередь, дек9 «Железнодорожные разъезды». Очередь First Postfix Prefix Last

Стек, очередь, дек10 Стек (Stack) Синонимы: First = Top, Rest = Pop, Prefix = Push Top верхушка стека, Pop {up} вытолкнуть (вверх), Push {down} – втолкнуть, вжать (вниз)).

Стек, очередь, дек11 Функциональная спецификация (Non_null_stack - множество непустых стеков): 1) Create: Stack (α); 2) Null: Stack (α) Boolean; 3) Top: Non_null_stack (α) α; 4) Pop: Non_null_stack (α) Stack (α); 5) Push: α Stack (α) Stack (α) Формальная спецификация стека из элементов типа α (Stack of α Stack (α)).

Стек, очередь, дек12 Аксиомы (для p: α; s: Stack (α); t: Non_null_stack (α)): A1) Null (Create) = true; A2) Null (Push (p, s)) = false; A3) Top (Push (p, s)) = p; A4) Pop (Push (p, s)) = s; A5) Push (Top (s), Pop (s)) = s. Абстрактный тип Stack (α) фактически (с точностью до обозначений и несущественных деталей) совпадает с типом L_list (α).

Стек, очередь, дек13 Пример 1.s := Push (a, s); 2.s := Push (b, s); 3.s := Pop (s); 4.s := Push (d, s); 5.s := Pop (s); 6.e := Top (s); Top (Pop (Push (d, Pop (Push (b, Push (a, s)))))) = =Top (Pop (Push (d, Push (a, s)))) = =Top (Push (a, s)) = a a b d Top s

Стек, очередь, дек14 Можно определить функцию (процедуру) Pop2, совмещающую результат действия функций Top и Pop: Pop2: Non_null_stack (α) α Stack (α). procedure Pop2 (out p: α; in-out s: Stack (α)); begin p := Top (s);s := Pop (s) end

Стек, очередь, дек15 Procedure Push2 (a: El; var s: Stack); {добавить элемент a в стек s} Procedure Pop2 (var a: El; var s: Stack;); {вытолкнуть элемент из стека s и сохранить его в a} Пусть задано состояние двух стеков s1 = [1] и s2 = [2, 3, 4]. Тогда после выполнения действий While not Null (s2) do begin Pop2 (a, s2); Push2 (a, s1); end состояние стеков есть s1 = [???] и s2 = [???]. s1 = [4, 3, 2, 1] и s2 = [ ]

Стек, очередь, дек16 Функциональная спецификация очереди из элементов типа α (Queue of α Queue (α)) 1) Create: Queue (α); 2) Null: Queue (α) Boolean; 3) First: Non_null_queue (α) α; 4) Rest: Non_null_queue (α) Queue (α); 5) Postfix: Queue (α) α Queue (α)

Стек, очередь, дек17 Аксиомы для очереди ( p: α; q: Queue (α)): A1) Null (Create) = true; A2) Null (Postfix (q, p)) = false; A3) First (Postfix (q, p)) = if Null (q) then p else First (q); A4) Rest (Postfix (q, p)) = if Null (q) then Create else Postfix (Rest (q), p). q p

Стек, очередь, дек18 Пример Функция сцепления двух очередей q1 и q2: Concat (q1, q2) if Null (q1) then q2 else if Null (q2) then q1 else {not Null (q1) & not Null (q2)} Concat (Postfix (q1, First (q2)), Rest (q2)) q1q1q2q2

Стек, очередь, дек19 Реализация стека и очереди Стек: Верхушка стека Начало: Конец: Очередь:

Стек, очередь, дек20 Реализация стека и очереди Mem: n321 Верх x x x x x x... Непрерывная реализация ограниченного стека на базе вектора Для представления стека используется: одномерный массив (вектор) Mem: array [1..n] of α переменная Верх: 1..n

Стек, очередь, дек21 Непрерывная реализация ограниченного стека на базе вектора Для пустого стека Верх = 0. Для целиком заполненного стека Верх = n. Вершина стека доступна как Mem [Верх]. Операция Pop реализуется как Верх:= Верх 1. Операция Push (p, s) как begin Верх:= Верх + 1; Mem [Верх]: = p end при 0 Верх < n. Mem: n321 Верх x x x x x x...

Стек, очередь, дек22 Два стека, ограниченных в совокупности, на базе одного вектора Mem: n321 Верх1 x x x x x x... x x x x x x Стек1 Стек2 Верх2

Стек, очередь, дек23 Непрерывная реализация ограниченной очереди на базе вектора Вектор Mem [1..n] Переменные Начало, Конец: 1..n, идентифицирующие начало и конец очереди Mem: n321 Начало x x x x x x x x Конец

Стек, очередь, дек24 Ситуация, когда последовательность элементов очереди по мере их добавления может выходить за границу вектора, продолжаясь с его начала (вектор имитирует здесь так называемый кольцевой буфер). Непрерывная реализация ограниченной очереди на базе вектора Mem: n321 Конец x x x x x x x x x x x Начало

Стек, очередь, дек25 Двух переменных Начало и Конец недостаточно, чтобы различить в данном представлении два следующих состояния очереди: 1) Начало = Конец + 1 и очередь пуста (рис. а); 2) Начало = Конец + 1 и очередь полна (рис. б). Непрерывная реализация ограниченной очереди на базе вектора Mem: n321 Начало Конец НачалоКонец Mem: n321 x x x x x x x x x x x x x x x x x x x x а б

Стек, очередь, дек26 Простое решение проблемы: введение дополнительной переменной, идентифицирующей состояние очереди, а именно переменной Длина: 0..n. Длина = текущее количество элементов в очереди. Для пустой очереди Длина = 0. Для полной очереди Длина = n. Непрерывная реализация ограниченной очереди на базе вектора

Стек, очередь, дек27 КОНЕЦ ЛЕКЦИИ