Стек. Реализация при помощи списков и операции над ними

Министерство по развитию информационных технологий и коммуникаций
Республики Узбекистан
Ташкентский университет информационных технологий имени
Мухаммада ал-Хоразмий
Самостоятельная работа

По Структуре данных и алгоритмы
На тему: Стек. Реализация при помощи списков и операции над ними

Выполнил : студент 3 курса группы 047-20
Факультет : Телекоммуникационные технологи
Кадиров С.С
Проверил : Ибрагимов Ж.О
Ташкент 2022
Содержание

1. Стек.

1.Дисциплина обслуживания

2.Виды операции в стеке

2. Реализация при помощи списков и операции над ними

1. Связный список

2. Односвязный список

3. Двусвязный список

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

Дисциплина обслуживания — это совокупность правил (упорядочение и алгоритм) обслуживания элементов динамической структуры данных. В стеке реализуется дисциплина обслуживания LIFO: LAST - последний INPUT - вошел FIRST - первый OUTPUT – вышел


Операции для работы со стеком Над стеком реализованы следующие операции:
• инициализация стека init(s), где s — стек • помещение элемента в стек push (s, i), где s — стек, i — помещаемый элемент; • удаление элемента из стека i=pop(s); • определение верхнего элемента без его удаления i=stkTop(s), которая эквивалентна операциям i=pop (s); push (s, i); • получение вершины стека (количества элементов) i=gettop(s), где s — стек • печать стека stkPrint(s), где s — стек • определение пустоты стека isempty(s) возвращает true если стек пустой и false в противном случае.
Способы реализации стека Существует несколько способов реализации стека:
• с помощью одномерного массива; • с помощью связанного списка; • с помощью класса объектно-ориентированного программирования. Пример реализации стека Стек можно реализовать в виде следующей структуры:
#define NMAX 100 struct stack { float elem[NMAX]; int top; }; NMAX — максимальное количество элементов в стеке; elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека; top — индекс элемента, находящегося в вершине стека.
Инициализация стека Индекс элемента, находящегося в вершине стека, равен 0.
void init(struct stack *stk) { stk->top = 0; }
Помещение элемента в стек
(push) void push(struct stack *stk, float f) { if(stk->top < NMAX) { stk->elem[stk->top] = f; stk->top++; } else printf("Стек полон, количество элементов: %d !\n", stk->top); }

Удаление элемента из стека

(pop) float pop(struct stack *stk) { float elem; if((stk->top) > 0) { stk->top--; elem = stk->elem[stk->top]; return(elem); } else { printf("Стек пуст!\n"); return(0); }
Извлечение вершины стека
float pop(struct stack *stk) { float elem; if((stk->top) > 0) { stk->top--; elem = stk->elem[stk->top]; return(elem); } else { printf("Стек пуст!\n"); return(0); } }
Получение верхнего элемента стека без его удаления
int gettop(struct stack *stk) { return(stk->top);} Определение пустоты стека int isempty(struct stack *stk) { if((stk->top) == 0) return(1); else return(0); }
Вывод элементов стека
void stkPrint(struct stack *stk) { int i; i=stk->top; if(isempty(stk)==1) return; do { i--; printf("%f\n", stk->elem[i]); }while(i>0); }
Вывод элементов стека
void stkPrint(struct stack *stk) { int i; i=stk->top; if(isempty(stk)==1) return; do { i--; printf("%f\n", stk->elem[i]); }while(i>0); }
Вывод элементов стека
void stkPrint(struct stack *stk) { int i; i=stk->top; if(isempty(stk)==1) return; do { i--; printf("%f\n", stk->elem[i]); }while(i>0); }
Список
Структура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг с другом посредством указателей, называется связным списком. Каждый элемент связного списка содержит поле с данными, а также указатель (ссылку) на следующий и/или предыдущий элемент. Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности. Причем это не потребует реорганизации структуры, которая бы потребовалась в массиве. Минусом связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список - структура последовательно доступа, в то время как массив - произвольного. Последний недостаток снижает эффективность ряда операций. По типу связности выделяют односвязные, двусвязные, XOR-связные, кольцевые и некоторые другие списки. Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.
Односвязный список
На изображении каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list - заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки - поле next (далее за ссылки будет отвечать и поле prev). Признаком отсутствия указателя является поле nil. Односвязный список не самый удобный тип связного списка, т. к. из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель на предыдущий, то такой список называется двусвязным. Та особенность двусвязного списка, что каждый элемент имеет две ссылки: на следующий и на предыдущий элемент, позволяет двигаться как в его конец, так и в начало. Операции добавления и удаления здесь наиболее эффективны, чем в односвязном списке, поскольку всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент. Но добавление и удаление элемента в двусвязном списке, требует изменения большого количества ссылок, чем этого потребовал бы односвязный список.
Двусвязный список
список очередь массив программа
Возможность двигаться как вперед, так и назад полезна для выполнения некоторых операций, но дополнительные указатели требуют задействования большего количества памяти, чем таковой необходимо в односвязном списке. Когда количество памяти, по каким-либо причинам, ограничено, тогда альтернативой двусвязному списку может послужить XOR-связный список. Последний использует логическую операцию XOR (исключающее «ИЛИ», строгая дизъюнкция), которая для двух переменных возвращает истину лишь при условии, что истинно только одно из них, а второе, соответственно, ложно. Таблица истинности операции:

В качестве переменных a и b у нас выступают адреса (на следующий и предыдущий элемент), над которыми выполняется операция XOR, возвращающая реальный адрес следующего элемента.

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