Слайд 2
![Очереди Очередь – динамическая структура данных с упорядоченным доступом к](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-1.jpg)
Очереди
Очередь – динамическая структура данных с упорядоченным доступом к элементам, функционирующая
по принципу FIFO.
First
In
First
Out
Слайд 3
![Последовательное хранение Типы и переменные typedef struct{ TYPE *list; int size,count,head,tail; } QUEUE;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-2.jpg)
Последовательное хранение
Типы и переменные
typedef struct{
TYPE *list;
int size,count,head,tail;
} QUEUE;
Слайд 4
![Создание очереди int Create(QUEUE *queue,int sz) { queue->list = (TYPE*)calloc(sz,sizeof(TYPE));](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-3.jpg)
Создание очереди
int Create(QUEUE *queue,int sz)
{
queue->list = (TYPE*)calloc(sz,sizeof(TYPE));
if(!queue->list) return 0;
queue->size = sz;
queue->count = queue->head = queue->tail = 0;
return 1;
}
Слайд 5
![Удаление очереди void Clear(QUEUE *queue) { if(queue->list) free(queue->list); queue->list =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-4.jpg)
Удаление очереди
void Clear(QUEUE *queue)
{
if(queue->list) free(queue->list);
queue->list = NULL;
queue->size =
queue->count = 0;
queue->head = queue->tail = 0;
}
Слайд 6
![Помещение элемента в очередь int Put(QUEUE *queue, TYPE val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-5.jpg)
Помещение элемента в очередь
int Put(QUEUE *queue, TYPE val)
{
if(queue->count == queue->size)
return 0;
queue->list[queue->tail++] = val;
if(queue->tail == queue->size) queue->tail = 0;
queue->count++;
return 1;
}
Слайд 7
![Изъятие элемента из очереди int Get(QUEUE *queue, TYPE *val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-6.jpg)
Изъятие элемента из очереди
int Get(QUEUE *queue, TYPE *val)
{
if(queue->count == 0)
return 0;
*val = queue->list[queue->head++];
if(queue->head == queue->size) queue->head = 0;
queue->count--;
return 1;
}
Слайд 8
![Пример Реализовать программу, которая в интерактивном режиме запрашивает у пользователя](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-7.jpg)
Пример
Реализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и
выполняет ее.
Команды:
exit – завершение программы,
put N – помещение N в очередь,
get – изъять элемент из очереди и вывести его значение на экран.
Дополнительно программа должна выводить сообщения о невозможности выполнения операции
Слайд 9
![Программа int main(int argc, char *argv[]) { QUEUE q; Create(&q,20);](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-8.jpg)
Программа
int main(int argc, char *argv[])
{
QUEUE q;
Create(&q,20);
while(1){
char cmd[21];
int value;
printf(">: "); gets(cmd);
if(strncmp(cmd,"exit",4)==0) break;
if(strncmp(cmd,"put",3)==0){
char *tail = NULL;
value = strtol(&cmd[3],&tail,10);
if(strlen(tail)==0){
if(!Put(&q,value)) puts("Очередь заполнена!");
} else puts("Некорректная команда");
}else if(strcmp(cmd,"get")==0){
if(Get(&q,&value)) printf("%d\n",value);
else puts("Очередь пуста!");
} else puts("Неизвестная команда!");
}
Clear(&q);
return 0;
}
Слайд 10
![Связанное хранение Типы и переменные: typedef struct _ELEMENT{ TYPE value;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-9.jpg)
Связанное хранение
Типы и переменные:
typedef struct _ELEMENT{
TYPE value;
struct _ELEMENT *next;
}
ELEMENT;
typedef struct{
ELEMENT *head, *tail;
}QUEUE;
Слайд 11
![Создание и удаление очереди void Create(QUEUE *queue) { queue->head =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-10.jpg)
Создание и удаление очереди
void Create(QUEUE *queue)
{
queue->head = queue->tail = NULL;
}
void
Clear(QUEUE *queue)
{
while(queue->head){
ELEMENT *tmp = queue->head;
queue->head = tmp->next;
free(tmp);
}
queue->tail = NULL;
}
Слайд 12
![Помещение элемента в очередь int Put(QUEUE *queue, TYPE val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-11.jpg)
Помещение элемента в очередь
int Put(QUEUE *queue, TYPE val)
{
ELEMENT *tmp =
(ELEMENT*)malloc(sizeof(ELEMENT));
if(!tmp) return 0;
tmp->next = NULL;
tmp->value = val;
if(queue->tail) queue->tail->next = tmp;
queue->tail = tmp;
if(!queue->head) queue->head = queue->tail;
return 1;
}
Слайд 13
![Изъятие элемента из очереди int Get(QUEUE *queue, TYPE *val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-12.jpg)
Изъятие элемента из очереди
int Get(QUEUE *queue, TYPE *val)
{
if(!queue->head) return 0;
ELEMENT *tmp = queue->head;
queue->head = tmp->next;
*val = tmp->value;
free(tmp);
if(!queue->head) queue->tail = NULL;
return 1;
}
Слайд 14
![Стек Стек – динамическая структура данных c упорядоченным доступом к](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-13.jpg)
Стек
Стек – динамическая структура данных c упорядоченным доступом к элементам, функционирующая
по принципу LIFO.
Last
In
First
Out
Слайд 15
![Последовательное хранение Типы и переменные: typedef struct{ TYPE *list; int size,head; } STACK;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-14.jpg)
Последовательное хранение
Типы и переменные:
typedef struct{
TYPE *list;
int size,head;
} STACK;
Слайд 16
![Создание стека int Create(STACK *stack, int sz) { stack->list =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-15.jpg)
Создание стека
int Create(STACK *stack, int sz)
{
stack->list = (TYPE*)calloc(sz,sizeof(TYPE));
if(!stack->list) return
0;
stack->head = -1;
stack->size = sz;
return 1;
}
Слайд 17
![Удаление стека void Clear(STACK *stack) { if(stack->list) free(stack->list); stack->list =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-16.jpg)
Удаление стека
void Clear(STACK *stack)
{
if(stack->list) free(stack->list);
stack->list = NULL;
stack->head =
0;
stack->size = 0;
}
Слайд 18
![Помещение элемента в стек int Push(STACK *stack, TYPE val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-17.jpg)
Помещение элемента в стек
int Push(STACK *stack, TYPE val)
{
if(stack->head == stack->size-1)
return 0;
stack->list[++stack->head] = val;
return 1;
}
Слайд 19
![Изъятие элемента из стека int Pop(STACK *stack, TYPE *val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-18.jpg)
Изъятие элемента из стека
int Pop(STACK *stack, TYPE *val)
{
if(stack->head == -1)
return 0;
*val = stack->list[stack->head--];
return 1;
}
Слайд 20
![Пример Реализовать программу, которая в интерактивном режиме запрашивает у пользователя](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-19.jpg)
Пример
Реализовать программу, которая в интерактивном режиме запрашивает у пользователя команду и
выполняет ее.
Команды:
exit – завершение программы,
push N – помещение N в стек,
pop – изъять элемент из стека и вывести его значение на экран.
Дополнительно программа должна выводить сообщения о невозможности выполнения операции
Слайд 21
![Программа int main(int argc, char *argv[]) { STACK q; Create(&q,20);](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-20.jpg)
Программа
int main(int argc, char *argv[])
{
STACK q;
Create(&q,20);
while(1){
char cmd[21];
int value;
printf(">: "); gets(cmd);
if(strncmp(cmd,"exit",4)==0) break;
if(strncmp(cmd,"push",4)==0){
char *tail = NULL;
value = strtol(&cmd[4],&tail,10);
if(strlen(tail)==0){
if(!Push(&q,value)) puts("Стек заполнен!");
} else puts("Некорректная команда");
}else if(strcmp(cmd,"get")==0){
if(Pop(&q,&value)) printf("%d\n",value);
else puts("Стек пуст!");
} else puts("Неизвестная команда!");
}
Clear(&q);
return 0;
}
Слайд 22
![Связанное хранение Типы и переменные: typedef struct _ELEMENT{ TYPE value;](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-21.jpg)
Связанное хранение
Типы и переменные:
typedef struct _ELEMENT{
TYPE value;
struct _ELEMENT *next;
}
ELEMENT;
typedef ELEMENT* STACK;
Слайд 23
![Создание и удаление стека void Create(STACK *stack) { *stack =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-22.jpg)
Создание и удаление стека
void Create(STACK *stack)
{
*stack = NULL;
}
void Clear(STACK *stack)
{
while(*stack){
ELEMENT *tmp = *stack;
*stack = tmp->next;
free(tmp);
}
}
Слайд 24
![Помещение элемента в стек int Push(STACK *stack, TYPE val) {](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/146072/slide-23.jpg)
Помещение элемента в стек
int Push(STACK *stack, TYPE val)
{
ELEMENT *tmp =
(ELEMENT*)malloc(sizeof(ELEMENT));
if(!tmp) return 0;
tmp->next = *stack;
tmp->value = val;
*stack = tmp;
return 1;
}