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

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

2 Стек, очередь, дек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 Стек, очередь, дек3 Наглядная модель

4 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек6 СД PrefixPostfixFirstLastRestLeadNull deq stack queue Подструктуры Sequence (El)

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

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

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

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

11 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек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 Стек, очередь, дек19 Реализация стека и очереди Стек: Верхушка стека Начало: Конец: Очередь:

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

21 Стек, очередь, дек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 Стек, очередь, дек22 Два стека, ограниченных в совокупности, на базе одного вектора Mem: n321 Верх1 x x x x x x... x x x x x x Стек1 Стек2 Верх2

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

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

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

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