Stack +++
.pdf
31
Очередь - кольцевой массив
Выборка из очереди:
int Pop ( QUEUE &q, int n, int &x)
{ if(q.head == n) return 0; // empty
x = q.data[q.head];
q.head++;
if(q.head ==n) q.head = 0;
if (q.head ==q.free) q.head=n;
return q.free - q.head ;
}
В программе
QUEUE queue; queue.head = queuesize, queue.free=0;
32
Очередь - список
Структура узла:
struct QUEUE { int data;
QUEUE *next, *prev; // двусвязный список
};
В программе
QUEUE *head=0, *last=0;
33
Очередь – список
Добавление элемента
int Push (QUEUE & head, QUEUE &last, int x ) { QUEUE *q;
q=(QUEUE * ) malloc(sizeof(QUEUE)); // new
if(!q) return 0;
q->data = x; q->next = 0;
if (last) // last exist !=0
{last->next = q; q->prev = last; }
else // если в очереди ничего не было
{q->prev = 0; head=q; } return 1;
}
34
Очередь - список
Выборка элемента:
int Pop (QUEUE &head, QUEUE &last, int &x )
{ QUEUE *h=head; |
// запомнили |
if ( !head) return |
0; // список пуст |
x = head ->data; |
|
if(head->next != 0) // он был не последний
head = head->next; |
|
else |
// очередь опустела |
head=last=0; |
|
free(h); |
// освободить память |
return 1; |
// success |
}
35
Дек
Дек (deque = double ended queue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов.
|
6 |
4 |
2 |
1 |
3 |
5 |
Операции с деком: |
|
|
|
|
|
|
1) |
добавление элемента в начало (PushHead); |
|||||
2) |
удаление элемента с начала |
(PopHead); |
||||
3) |
добавление элемента в конец |
(PushTail); |
||||
4) |
удаление элемента с конца |
(PopTail). |
||||
Реализация:
1)кольцевой массив;
2)двусвязный список.