Int pop (Node **top)

{

int temp = (*top)->d;

Node *pv = *top;

*top = (*top)->p;

delete pv;

return temp;

}

Результат роботи програми:

5 4 3 2 1

8.3. Черга

Черга реалізує принцип обслуговування FIFO (first in – first out, першим прийшов, – першим пішов). Приклад черги – черга людей в магазині. Нижче приведена програма, яка формує чергу з п'яти цілих чисел і виводить її на екран. Функція поміщення елементу в кінець черги називається add, а вибірки – del. Вказівка на початок черги називається pbeg, вказівка на кінець – pend.

#include <iostream>

using namespace std;

struct Node

{

int d;

Node *p;

};

Node * first(int d);

void add(Node **pend, int d);

int del(Node **pbeg);

Void main()

{

Node *pbeg = first(l);

Node *pend = pbeg;

for (int i = 2; i<6; i++) add(&pend, i);

while (pbeg)

cout << del(&pbeg) << " ";

}

// Початкове формування черги

Node* first(int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = 0;

return pv;

}

// Додавання в кінець

Void add(Node **pend, int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = 0;

(*pend)->p = pv;

*pend = pv;

}

// Вибірка

Int del(Node **pbeg)

{

int temp = (*pbeg)->d;

Node *pv = *pbeg;

*pbeg = (*pbeg)->p;

delete pv;

return temp;

}

Результат роботи програми:

12 3 4 5

8.4. Лінійний список

Найпростіший спосіб зв'язати безліч елементів – зробити так, щоб кожен елемент містив посилання на наступний. Такий список називається однонаправленим (однозв’язним). Якщо додати в кожен елемент друге посилання – на попередній елемент, вийде двонаправлений список (двозв’язний), якщо останній елемент зв'язати вказівкою з першим, вийде кільцевий список.

Кожен елемент списку містить ключ, що ідентифікує цей елемент. Ключ зазвичай буває або цілим числом, або рядком і є частиною поля даних. У якості ключа в процесі роботи із списком можуть виступати різні частини поля даних. Наприклад, якщо створюється лінійний список із записів, які містять прізвище, рік народження, стаж роботи та стать, будь-яка частина запису може виступати як ключ: при впорядковувань списку за алфавітом ключем буде прізвище, а при пошуку, наприклад, ветеранів праці ключем буде стаж. Ключі різних елементів списку можуть збігатися.

Над списками можна виконувати наступні операції:

• початкове формування списку (створення першого елементу);

• додавання елементу в кінець списку;

• читання елементу із заданим ключем;

• вставка елементу в задане місце списку (до або після елементу із заданим ключем);

• видалення елементу із заданим ключем;

• впорядковування списку по ключу.

Розглянемо двонаправлений лінійний список. Для формування списку і роботи з ним потрібно мати принаймні одну вказівку – на початок списку. Зручно завести ще одну вказівку – на кінець списку. Для простоти допустимо, що список складається з цілих чисел, тобто опис елементу списку виглядає таким чином:

struct Node

{

int d;

Node *next;

Node *prev;

};

Нижче приведена програма, яка формує список з 5 чисел, додає число в список, видаляє число із списку і виводить список на екран. Вказівка на початок списку позначена pbeg, на кінець списку – pend, допоміжні вказівки – pv та ркеу.

#include <iostream>

using namespace std;

struct Node

{

int d;

Node *next;

Node *prev;

};

Node* first(int d);

void add(Node **pend, int d);

Node* find(Node * const pbeg, int i);

bool remove(Node **pbeg, Node **pend, int key);

Node* insert(Node * const pbeg, Node **pend,int key,int d);