Информатика и технология программирования

Представление очереди и стека односвязным списком


Наиболее простыми являются операции включения в начало и конец односвязного списка и исключение первого элемента. Если ограничиться таким набором операций, то при помощи односвязного списка легко можно моделировать стек и очередь:



-запись в стек моделируется записью в начало списка;



-извлечение из стека моделируется удалением из начала списка;



-запись в очередь моделируется включением в конец списка. Для того, чтобы не просматривать каждый раз весь список, в заголовок списка обычно добавляют указатель на последний элемент списка;



-извлечение из очереди моделируется удалением элемента, расположенного в начале списка.

В качестве примера рассмотрим функции включения и исключения элемента в очередь с заголовком в виде пары указателей на первый и последний элемент:


//------------------------------------------------------bk53-04.cpp


//----- Постановка элемента в конец очереди


// list *PH[2]; - заголовок очереди


void intoFIFO(list *ph [], int v)
{
list *p= new list; // создать элемент списка;


p-&#62val = v; // и заполнить его


p-&#62next = NULL; // новый элемент - последний


if (ph[0] == NULL) // включение в пустую


ph[0] = ph[1] = p; // очередь


else // включение за последним


{ // элементом


ph[1]-&#62next = p; // следующий за последним = новый


ph[1] = p; // новый = последний


}
}
//----- Извлечение из очереди


int fromFIFO(list *ph [])
{ list *q;
if (ph[0] ==NULL) return -1; // очередь пуста


q = ph[0]; // исключение первого


ph[0] = q-&#62next; // элемента


if (ph[0] ==NULL)
ph[1] = NULL; // элемент единственный


int v = q-&#62val;
delete q;
return v;
}



Содержание раздела