Please download to get full document.

View again

of 43
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Стеки и очереди. Лекция 3. Курносов Михаил Георгиевич

Category:

Taxes & Accounting

Publish on:

Views: 0 | Pages: 43

Extension: PDF | Download: 0

Share
Related documents
Description
Лекция 3 Стеки и очереди Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатики Стек
Transcript
Лекция 3 Стеки и очереди Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатики Стек (Stack) Стек (Stack) структура данных для хранения элементов Дисциплина доступа к элементам: последним пришел первым вышел (Last In First Out, LIFO) Элементы помещаются и извлекаются с головы стека (top) D Push Pop D Top D C B A 2 Подходы к реализации стека 1. На основе связных списков (linked lists) Длина стека ограничена объемом доступной памяти 2. На основе статических массивов Длина стека фиксирована (задана его максимальная длина количество элементов в массиве) 4 Реализация стека на основе связных списков Элементы стека хранятся в односвязном списке (singly linked list) Добавление элемент и удаление выполняется за время O(1) Stack: Size Top Данные Next Данные Next Данные Next NULL 5 Реализация стека на основе связных списков #include stdio.h #include stdlib.h #include llist.h /* см. лекцию 3 */ struct stack struct listnode *top; /* Верхушка стека */ int size; ; 6 Реализация стека на основе связных списков /* * Фрагмент файла llist.c */ struct listnode int value; /* Данные стека */ ; struct listnode *next; 7 Реализация стека на основе связных списков /* stack_create: Creates an empty stack */ struct stack *stack_create() struct stack *s = malloc(sizeof(*s)); if (s!= NULL) s- size = 0; s- top = NULL; return s; T Create = O(1) 8 Реализация стека на основе связных списков /* stack_free: Removes stack */ void stack_free(struct stack *s) while (s- size 0) stack_pop(s); /* Delete All items */ free(s); T Free = O(n) Stack: Size Top Данные Next Данные Next Данные Next NULL 9 Реализация стека на основе связных списков /* stack_size: Returns size of a stack */ int stack_size(struct stack *s) return s- size; T Size = O(1) 10 Реализация стека на основе связных списков int main() struct stack *s; s = stack_create(); printf( stack size: %d\n , stack_size(s)); stack_free(s); return 0; 11 Реализация стека на основе связных списков /* stack_push: Pushes item to the stack */ int stack_push(struct stack *s, int value) s- top = list_addfront(s- top, value); if (s- top == NULL) fprintf(stderr, stack: Stack overflow\n ); return -1; s- size++; return 0; T Push = O(1) 12 Реализация стека на основе связных списков /* stack_pop: Pops item from the stack */ int stack_pop(struct stack *s) struct listnode *next; int value; if (s- top == NULL) fprintf(stderr, stack: Stack underflow\n ); return -1; next = s- top- next; value = s- top- value; free(s- top); s- top = next; s- size--; return value; T Pop = O(1) 13 Реализация стека на основе связных списков int main() struct stack *s; int i, val; s = stack_create(); for (i = 1; i = 10; i++) stack_push(s, i); for (i = 1; i = 11; i++) val = stack_pop(s); printf( pop: %d\n , val); stack_free(s); pop: 10 pop: 9 pop: 8 pop: 7 pop: 6 pop: 5 pop: 4 pop: 3 pop: 2 pop: 1 pop: -1 return 0; 14 Реализация стека на основе массива Элементы стека хранятся в массиве фиксированной длины L Добавление элемент и удаление выполняется за время O(1) L 1 Top 2 C 1 B 0 A 15 Реализация стека на основе массива #include stdio.h #include stdlib.h struct stack int *v; int top; int size; int maxsize; ; 16 Реализация стека на основе массива /* stack_create: Creates an empty stack */ struct stack *stack_create(int maxsize) struct stack *s = malloc(sizeof(*s)); if (s!= NULL) s- v = malloc(sizeof(int) * maxsize); if (s- v == NULL) free(s); return NULL; s- size = 0; s- top = 0; s- maxsize = maxsize; return s; T Create = O(1) 17 Реализация стека на основе массива /* stack_free: Removes stack */ void stack_free(struct stack *s) free(s- v); free(s); T Free = O(1) /* stack_size: Returns size of a stack */ int stack_size(struct stack *s) return s- size; T Size = O(1) 18 Реализация стека на основе массива /* stack_push: Pushes item to the stack */ int stack_push(struct stack *s, int value) if (s- top s- maxsize) s- v[s- top++] = value; s- size++; else fprintf(stderr, stack: Stack overflow\n ); return -1; return 0; T Push = O(1) 19 Реализация стека на основе массива /* stack_pop: Pops item from the stack */ int stack_pop(struct stack *s) if (s- top == 0) fprintf(stderr, stack: Stack underflow\n ); return -1; s- size--; return s- v[--s- top]; T Pop = O(1) 20 Очередь (Queue) Очередь (Queue) структура данных для хранения элементов (контейнер) Дисциплина доступа к элементам: первым пришел первым вышел (First In First Out, FIFO) Элементы добавляются в хвост (tail), извлекаются с головы (head) Кит Back (tail, rear) Front (head) Enqueue Слон Жираф Волк Заяц Dequeue Рысь 21 Очередь (Queue) Очереди широко используется в алгоритмах обработки данных: очереди печати буфер ввода с клавиатуры алгоритмы работы с графами 22 Очередь (Queue) Операция Enqueue(q, x) Dequeue(q) Size(q) Clear(q) Описание Добавляет элемент x в очередь q Извлекает элемент из очереди q Возвращает количество элементов в очереди q Очищает очередь q 23 Подходы к реализации очереди 1. На основе связных списков Длина очереди ограничена лишь объемом доступной памяти 2. На основе статических массивов Длина очереди фиксирована (задана максимальная длина) 24 Реализация очереди на основе связных списков Элементы очереди хранятся в односвязном списке (singly linked list) Для быстрого (за время O(1)) добавления и извлечения элементов из списка поддерживается указатель на последний элемент (tail) Новые элементы добавляются в конец списка Queue: Size Head Tail Данные Next Данные Next Данные Next NULL 25 Реализация очереди на основе связных списков Преимущества: длина очереди ограничена лишь объемом доступной памяти Недостатки (по сравнению с реализацией на основе массивов): работа с очередью немного медленнее, требуется больше памяти для хранения одного элемента Queue: Size Head Tail Данные Next Данные Next Данные Next NULL 26 Реализация очереди на основе связных списков #include stdio.h #include stdlib.h #include llist.h struct queue struct listnode *head; struct listnode *tail; int size; ; 27 Реализация очереди на основе связных списков /* queue_create: Creates an empty queue */ struct queue *queue_create() struct queue *q = malloc(sizeof(*q)); if (q!= NULL) q- size = 0; q- head = NULL; q- tail = NULL; return q; T Create = O(1) 28 Реализация очереди на основе связных списков /* queue_free: Removes queue */ void queue_free(struct queue *q) while (q- size 0) queue_dequeue(q); free(q); T Free = O(n) 29 Реализация очереди на основе связных списков /* queue_size: Returns size of a queue */ int queue_size(struct queue *q) return q- size; int main() struct queue *q; q = queue_create(); T Size = O(1) queue_free(q); return 0; 30 Реализация очереди на основе связных списков /* queue_enqueue: Add item to the queue */ void queue_enqueue(struct queue *q, int value) struct listnode *oldtail = q- tail; /* Create new node */ q- tail = list_createnode(value); if (q- head == NULL) /* List is empty */ q- head = q- tail; else /* Add new node to the end of list */ oldtail- next = q- tail; q- size++; T Enqueue = O(1) 31 Реализация очереди на основе связных списков int main() struct queue *q; int i; q = queue_create(); for (i = 1; i = 10; i++) queue_enqueue(q, i); printf( queue size: %d\n , queue_size(q)); queue_free(q); return 0; 32 Реализация очереди на основе связных списков /* queue_dequeue: Gets item from the queue */ int queue_dequeue(struct queue *q) int value; struct listnode *p; if (q- size == 0) return -1; /* Delete first node */ value = q- head- value; p = q- head- next; free(q- head); q- head = p; q- size--; return value; T Dequeue = O(1) 33 Реализация очереди на основе связных списков int main() struct queue *q; int i, j; q = queue_create(); /*... */ for (i = 1; i = 11; i++) j = queue_dequeue(q); printf( %d: next element: %d\n , i, j); queue_free(q); return 0; 34 Реализация очереди на основе циклических массивов Элементы очереди хранятся в массиве фиксированной длины [0..L 1] Массив логически представляется в виде кольца (circular buffer) В пустой очереди Tail = 0, Head = L L 1 L X Tail Head 35 Реализация очереди на основе циклических массивов При добавлении элемента в очередь значение Tail циклически увеличивается на 1 (сдвигается на следующую свободную позицию) Если Head = Tail + 1, то очередь переполнена! Enqueue(1): L 1 L 1 X Tail Head 36 Реализация очереди на основе циклических массивов При удалении возвращается элемент с номером Head % L Значение Head циклически увеличивается на 1 (указывает на следующий элемент очереди) L 1 L 1 X Tail Head Dequeue(): L 1 L X Head Tail 37 Реализация очереди на основе циклических массивов #include stdio.h #include stdlib.h struct queue int *v; int head; int tail; int size; int maxsize; ; 38 Реализация очереди на основе циклических массивов /* queue_create: Creates an empty queue */ struct queue *queue_create(int maxsize) struct queue *q = malloc(sizeof(*q)); if (q!= NULL) q- v = malloc(sizeof(int) * (maxsize + 1)); if (q- v == NULL) free(q); return NULL; q- maxsize = maxsize; q- size = 0; q- head = maxsize + 1; q- tail = 0; return q; T Create = O(1) 39 Реализация очереди на основе циклических массивов /* queue_free: Removes queue */ void queue_free(struct queue *q) free(q- v); free(q); /* queue_size: Returns size of a queue */ int queue_size(struct queue *q) return q- size; 40 Реализация очереди на основе циклических массивов /* queue_enqueue: Add item to the queue */ int queue_enqueue(struct queue *q, int value) if (q- head == q- tail + 1) fprintf(stderr, queue: Queue overflow\n ); return -1; q- v[q- tail++] = value; q- tail = q- tail % (q- maxsize + 1); q- size++; return 0; T Enqueue = O(1) 41 Реализация очереди на основе циклических массивов /* queue_dequeue: Gets item from the queue */ int queue_dequeue(struct queue *q) if (q- head % (q- maxsize + 1) == q- tail) /* Queue is empty */ fprintf(stderr, queue: Queue is empty\n ); return -1; q- head = q- head % (q- maxsize + 1); q- size--; return q- v[q- head++]; T Dequeue = O(1) 42 Реализация очереди на основе циклических массивов int main() struct queue *q; int i, val; q = queue_create(10); val = queue_dequeue(q); for (i = 1; i = 11; i++) queue_enqueue(q, i); for (i = 1; i = 5; i++) val = queue_dequeue(q); queue_free(q); return 0; 43 Домашнее чтение Найти и прочитать о двухсторонней очереди (дек, deque double ended queue) 44
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks