Представление очереди и стека односвязным списком
Наиболее простыми являются операции включения в начало и конец односвязного списка и исключение первого элемента. Если ограничиться таким набором операций, то при помощи односвязного списка легко можно моделировать стек и очередь:
-запись в стек моделируется записью в начало списка;
-извлечение из стека моделируется удалением из начала списка;
-запись в очередь моделируется включением в конец списка. Для того, чтобы не просматривать каждый раз весь список, в заголовок списка обычно добавляют указатель на последний элемент списка;
-извлечение из очереди моделируется удалением элемента, расположенного в начале списка.
В качестве примера рассмотрим функции включения и исключения элемента в очередь с заголовком в виде пары указателей на первый и последний элемент:
//------------------------------------------------------bk53-04.cpp
//----- Постановка элемента в конец очереди
// list *PH[2]; - заголовок очереди
void intoFIFO(list *ph [], int v)
{
list *p= new list; // создать элемент списка;
p->val = v; // и заполнить его
p->next = NULL; // новый элемент - последний
if (ph[0] == NULL) // включение в пустую
ph[0] = ph[1] = p; // очередь
else // включение за последним
{ // элементом
ph[1]->next = p; // следующий за последним = новый
ph[1] = p; // новый = последний
}
}
//----- Извлечение из очереди
int fromFIFO(list *ph [])
{ list *q;
if (ph[0] ==NULL) return -1; // очередь пуста
q = ph[0]; // исключение первого
ph[0] = q->next; // элемента
if (ph[0] ==NULL)
ph[1] = NULL; // элемент единственный
int v = q->val;
delete q;
return v;
}
