Iv. Динамические структуры данных

struct Node { 
int data; 
Node *next, *prev; 
}; 
typedef Node *PNode; 

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
17
Чтобы не работать с отдельными указателями на хвост и голову списка, объявим структу-
ру, в которой будет храниться вся информация об очереди: 
struct Queue { 
PNode head, tail;
}; 
В самом начале надо записать в обе ссылки NULL. Заметим, что такая же структура использова-
лась и для стека. Более того, функция для получения первого элемента очереди (Pop) совпадает 
с функцией снятия элемента с вершины стека (напишите ее в качестве упражнения). 
 Добавление элемента в конец очереди 
Фактически это добавление нового элемента в конец двусвязного списка. В параметрах 
процедуры указывается не новый узел, а только данные для этого узла, то есть целое число. 
Память под новый узел выделяется в процедуре, то есть, скрыта от нас и снижает вероятность 
ошибки. 
void PushTail ( Queue &Q, int x ) 
{ 
PNode NewNode; 
NewNode = new Node;
// создать новый узел 
NewNode->data = x;
// заполнить узел данными
NewNode->prev = Q.Tail; 
NewNode->next = NULL; 
if ( Q.tail )
// добавить узел в конец списка 
Q.tail->next = NewNode; 
Q.tail = NewNode; 
if ( ! Q.head ) Q.head = Q.tail; 
} 
 
Дек 
Дек (deque)
 - 
это упорядоченный набор элементов, в котором добавление новых и удаление 
существующих элементов допустимо с любого конца.
 
Дек может быть реализован на основе массива или двусвязного списка. Для дека разрешены 
четыре операции:
1) добавление элемента в начало; 
2) добавление элемента в конец; 
3) удаление элемента с начала; 
4) удаление элемента с конца. 
Их можно реализовать, используя написанные выше процедуры для стека и очереди. 

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
18