СПИСКИ МАГАЗИННОГО ТИПА. Замечание! Очередь также называют циклической памятью или списком типа FIFO (First In - First Out - первым включается - первым исключается). Замечание! Существуют и другие названия стека: магазин, список ти

СПИСКИ МАГАЗИННОГО ТИПА

Определение: Список магазинного типа – это линейный список, все звенья которого вставляются и удаляются только с одного или обоих концов списка. Виды списков магазинного типа:

· Очередь (FIFO);

· Cтек (LIFO);

· Дек (DEQ).

Определение: Очередь – это линейный список, в котором все включения элементов производятся на одном конце списка, а все исключения происходят на другом его конце.

Замечание! Очередь также называют циклической памятью или списком типа FIFO ("First In - First Out" - "первым включается - первым исключается")

Определение: Стек - это линейный список, в котором все включения и исключения элементов производятся в одном конце списка.

Замечание! Существуют и другие названия стека: магазин, список типа LIFO ("Last In - First Out" - "последним включается - первым исключается"); "пуш-даун" список ("push-down"), реверсивная память, гнездовая память.

Замечание! Понятие стек было введено А.М.Тьюрингом в 1947 г. и названо им реверсивной памятью (оно использовалось для связи подпрограмм).

Определение: Дек ("Double-Ended Queue" - "двухсторонняя очередь") – это линейный список, в котором все включения и исключения элементов производятся на обоих концах списка.

Замечание! Термин "дек" был введен E.J.Schweppe (Основатель компании J. Schweppes & Со и торговой марки прохладительных напитков Schweppes)

Рассмотрим основные методы по работе с очередью:

struct node

{

int value;

node *next;

};

class List {

private:

node *qs,*qe; // Queue start и Queue End

int SaveValue;

public:

List () {qs=qe=NULL;}

void CreateQ ();

void ShowQ ();

void AddMemberQ (int);

int SetSaveValue () { return SaveValue; }

void DelMemberQ ();

void FreeQ();

};

void List::CreateQ ()

//Построение очереди на базе однонаправленного списка

//без заглавного звена.

//qs - указатель на начало очереди.

//qe - указатель на конец очереди.

{

node *r;

int el;

cout<<"Вводите элементы очереди:\n";

cin>>el;

if (el!=0)

{

r = new (node);

(*r).value = el; (*r).next = NULL;

qs = r; qe = r; cin>>el;

while (el!=0)

{

r = new (node);

(*r).value = el; (*r).next = NULL;

(*qe).next = r; qe = r; cin>>el;

}

else

{r = NULL; qs = r; qe = r;}

}

void List::ShowQ ()

//Вывод содержимого очереди.

//qs - указатель на начало очереди.

//qe - указатель на конец очереди.

{

node *r;

cout<<"Очередь: "; r = qs;

while (r!=NULL)

{

cout<<(*r).value<<" "; r = (*r).next;

}

cout<<endl;

}

void List::AddMemberQ (int el)

//Добавление звена с информационным полем el к очереди,

//определенной указателями qs и qe.

{

node *r;

r = new (node);

(*r).value = el; (*r).next = NULL;

if (qs!=NULL)

{

(*qe).next = r; qe = r;

}

else

{qs = r; qe = r;}

}

void List::DelMemberQ ()

//Удаление звена из очереди, определенной указателями

//qs и qe, с помещением его информационного поля в

//параметр SaveValue.

{

node *q;

if (qs==NULL)

cout<<"Удалить нельзя, так как очередь пуста!\n";

else

{

SaveValue = (*qs).value; q = qs;

qs = (*qs).next; delete q;

}

void List::FreeQ()

//Возврат выделенной памяти в "кучу".

{

node *q;

q=qs;

if (qs!=NULL)

{

while (qs!=qe)

{

qs=(*q).next;

delete q; q=qs; }

delete qs;

qs=qe=NULL;

}

Классы стека и дека, рассмотрим на следующем занятии.

ЗАДАНИЕ:

1) Осуществить изучение материала путем реализации приведенных примеров кода.

2) Ответить на следующие вопросы:

a) Что такое стек, дек, очередь.

b) Самостоятельно изобразить схему работы дека по примеру выше приведённых схем работы очереди и стека.

Задача: Карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт – проигрывает.

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту.

Игрок, который забирает себе карты, сначала кладет под низ своей колоды свою карту, затем карту оппонента.

Напишите программу, которая моделирует данную игру и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.

Входные данные:

Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — значения карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

Выходные данные:

Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша, а также состояние колоды победившего игрока.

Примеры

Входные данные

1 3 5 7 9

2 4 6 8 0

Выходные данные

second 5

2 1 4 3 6 5 8 7 0 9

ВАЖНО! Колоды игроков хранятся в динамической структуре очередь!!!!

Источники:

1) [ЭЛЕКТРОННЫЙ РЕСУРС]: Национальная библиотека им. Н. Э. Баумана Bauman National Library; режим доступа: https://ru.bmstu.wiki/FIFO_(First_In_First_Out).

2) [ЭЛЕКТРОННЫЙ РЕСУРС]: Кафедра ПОАС КГУ; режим доступа: http://it.kgsu.ru/).

3) [ЭЛЕКТРОННЫЙ РЕСУРС]: Задачи на очередь;режим доступа: https://informatics.mccme.ru/mod/statements/print3.php?id=20210