1. Стеки, очереди и деки: их функциональная спецификация, логическое описание и физическое представление. Добавление и удаление элементов

 

Cтек

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).

Полезными могут быть также вспомогательные операции:

определение текущего числа элементов в стеке;

очистка стека;

неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций:

 x:=pop(stack);  push(stack,x);

Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

Для наглядности рассмотрим небольшой пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. 4 (а,б,с) изображены состояния стека:

а). пустого;

б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';

д, е). после последовательного удаления из стека элементов 'C' и 'B';

ж). после включения в стек элемента 'D'.

 

Description: C:\Users\Alla\Desktop\stack1.gif

 

Как видно из рис. С.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Пример реализации статического стека на основе одномерного массива


typedef struct

{

int sp;

int val[MAXN];

} stack;

void push(stack *s, int x)

{

s->val[s->sp++] = x;

}

 

int pop(stack *s)

{

return s->val[--s->sp];

}

 

Очередь FIFO

Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.

Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.

Реализация очереди (также статической)


 

typedef struct

{

int qh, qt;

int val[MAXN];

} queue;

void enq(queue *q, int x)

{

q->val[(q->qt++)%MAXN] = x;   //добавить эелемент в хвост

}

 

 

 

int deq(queue *q)

{

return q->val[(q->qh++)%MAXN];   //извлечь из головы

}

 

Дек

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Операции над деком:

включение элемента справа;

включение элемента слева;

исключение элемента справа;

исключение элемента слева;

определение размера;

очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

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

Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.


typedef struct

{

int dh, dt;

int val[MAXN];

} deque;

 

 

void push_front(deque *d, int x)

{

if (d->dh < 1) d->dh += MAXN;

d->val[(--d->dh)%MAXN] = x;

}

 

void push_back(deque *d, int x)

{

d->val[(d->dt++)%MAXN] = x;

}

 

int pop_front(deque *d)

{

return d->val[(d->dh++)%MAXN];

}

 

int pop_back(deque *d)

{

if (d->dt < 1) d->dt += MAXN;

return d->val[(--d->dt)%MAXN];

}

 

//Проверка на то, чтобы поля не становились отрицательными:

if (a.dt > a.dh)

dlen = (a.dt-a.dh)%MAXN;

else

dlen = MAXN - (a.dh-a.dt)%MAXN;

//(а – это дек)

 

 

ИЗ ЛЕКЦИЙ

2.1. Стек

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

Рис. 1.1. Цепное

представление стека.

            Например, стопка книг на столе является аналогом стека: взять можно только верхнюю книгу в стопке и положить новую – только сверху. Стек называют также списком типа LIFO (Last In, First Out, что означает: “последним пришел – первым ушел”).

            Идеальная последовательность пополнения стека удовлетворяет следующим условиям:

      - стек никогда не становится пустым;

      - элементы, находящиеся на дне стека, не остаются в стеке после предельной даты;

            - частота пополнения стека применительно к конкретной задаче не слишком велика.

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

            Существует соответствие между поведением стека и структурой выражения, где каждая закрывающаяся скобка соответствует всегда последней встретившейся открывающейся скобке, а также и между  организацией программы блочной структуры, где каждый END “закрывает” последний встретившийся BEGIN.

 

            Функциональная спецификация

            Тип СТЕКТ, или стек объектов типа Т , характеризуется следующими операциями:

создание: создание_стека - операция без параметров, создающая пустой стек;

доступ:           стек_пуст   – операция проверяет, является ли стек пустым;

            последний – операция возвращает последний добавленный элемент;

модификация:

            засылка – операция добавляет новый элемент к стеку;

            выемка – операция   создает   новый   стек  в  результате   извлечения  верхушки; свойства этой операции верны, если стек не пуст.

 

Логическое описание

            Часть стека без верхушки называют телом  стека.  Тело само является по существу, стеком: если снять со стека его верхушку, то тело превращается в стек. Поэтому  естественное логическое описание состоит в рассмотрении стека как соединение элемента типа Т, называемого “верхушкой”, и некоторого стека. Чтобы получить конечные структуры, вводят возможность пустого стека:

тип СТЕК т = (ПУСТО или НЕ_ПУСТОЙ_СТЕК т);

тип НЕ_ПУСТОЙ_СТЕК т = (верхушка: Т; тело: СТЕК т).

 

Физическое представление

            При цепном представлении каждый элемент стека должен содержать, по крайней мере, два поля: первое поле для хранения данных и второе – для указателя. Для простоты в дальнейшем будем считать, что данные имеют тип ЛИТЕРА.

            Пример. На рис. 1.2 представлены процедуры добавления элемента в стек и удаления элемента из стека.

 

{...}

type ptr=^node;

        node=record d:char; p:ptr  end;

var ch:char; top,k:ptr;

 

{...}

procedure AddFILO(var top:ptr; var ch:char);

 begin

         new(k); k^.d:=ch; k^.p:=top; top:=k

 end;    {*AddFILO*}

 

procedure DelFILO(var top:ptr);

 begin

         k:=top; top:=top^.p;      dispose(k)

 end;    {*DelFILO*}

            Рис. 1.2.

 

 

 

            2.2. Очередь. Дек

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

            Рис. 1.3. Цепное представление очереди.

 

Очередь называют списком FIFO (First In, First Out, что означает – “первым пришел – первым ушел”).

Функциональная спецификация

      Тип ОЧЕРЕДЬ Т, или очередь объектов типа Т , характеризуется следующими операциями:

создание:       создание_очереди – операция создает пустую очередь;

доступ:           очередь_пуста – проверка пустоты очереди;

            первый – доступ к самому  давнему    элементу   очереди (к голове),  если очередь не пуста;

 модификация:

            дополнение – прибавление нового элемента в хвост очереди;

            удаление – получение новой очереди  путем удаления элемента из головы очереди; свойства операции верны, если очередь не пуста.

 

Логическое описание

            Требование использовать ОЧЕРЕДЬ “с двух концов” приводит к следующему рекурсивному описанию:

тип ОЧЕРЕДЬт = (ПУСТО или НЕ_ПУСТАЯ_ОЧЕРЕДЬ т);

тип НЕ_ПУСТАЯ_ОЧЕРЕДЬт = (голова:Т;  тело: ОЧЕРЕДЬ т).

 

Физическое представление

            Пример. На рис. 1.4 представлены представлены процедуры добавления элемента в очередь и удаления элемента из очереди.

 

            {...}

type ptr=^node;

        node=record d:char; p:ptr end;

var ch:char; head,tail,k:ptr;

 

                 {...}

procedure AddFIFO(var tail:ptr; var ch:char);

 begin

         new(k); k^.d:=ch; k^.p:=nil; tail^.p:=k; tail:=k

 end;    {*AddFIFO*}

procedure DelFIFO(var head:ptr);

 begin

         k:=head; head:=head^.p; dispose(k)

 end;    {*DelFIFO*}

            Рис. 1.4.

 

 

           

Дек

 

Обобщением очереди является дек. Дек – это список, для которого включение и удаление элементов выполняется с любого края. Название этой структуры данных образовано.из первых букв английских слов Double Ehden  (двусторонняя запись). Работа с деком организуется аналогично работе с очередью с той лишь разницей что здесь выполняется четыре различных операции модификации: включение как в начало, так и в конец дека, удаление как из начала, так и из конца дека.