Списки-8
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Двусвязный список имеет следующую структуру узла
```c
typedef struct node {
int value;
struct node *next, *prev;
} node;
```
На основе такого списка создается структура данных "дек"
(двойная очередь, в которую можно добавлять и убирать элементы с обоих сторон).
```c
typedef struct deque {
int size;
node *front, *back;
} deque;
```
Для работы с такой очередью нужно использовать функции:
```
void deque_init(deque* d) { d->size=0; d->front=d->back=NULL; } // инициализация
int deque_front(deque* d) { return d->front->value; } // первый элемент
int deque_back(deque* d) { return d->back->value; } // последний элемент
int deque_size(deque* d) { return d->size; } // размер
void deque_pushfront(deque* d, int val) // добавить значение в начало
{ node *n=malloc(sizeof(node)); // новый узел
n->value=val;
n->next=d->front;
n->prev=NULL;
d->size++;
if(d->front==NULL) {
d->front=d->back=n; // оба на новый узел
}
else {
d->front->prev=n;
d->front=n;
}
}
void deque_popfront(deque* d) // удалить значение в начале
{
node *n=d->front;
d->front=n->next;
free(n);
d->size--;
if(d->size==0)
d->front=d->back=NULL;
if(d->front)
d->front->prev=NULL;
}
void deque_pushback(deque* d, int val); // добавить значение в конец
void deque_popback(deque* d); // удалить значение в конце
// эти 2 функции вы должны написать самостоятельно
```
Пример использования
```c
#include <stdio.h>
#include <stdlib.h>
// определение node, deque и функций
...
int main()
{
deque d;
deque_init(&d);
deque_pushfront(&d,1);
deque_pushfront(&d,2);
deque_pushback(&d,3);
// 2 1 3
printf("%d\n",deque_front(&d)); // 2
deque_popback(&d);
printf("%d\n",deque_back(&d)); // 1
}
```
В качестве решения необходимо отправлять файл, содержащий только функции deque_pushback и deque_popback!
Решение этой задачи можно использовать при решении задачи "Склад Оби-Вана Кеноби".
Начало
Учебные задачи
Учебные задачи: списки