2.1.2. Стеки

Стек – це спеціальний вид списку, додавання вузлів у який і видалення вузлів з якого здійснюються тільки з одного кінця – вершини. Нові вузли записуються в структуру стека через вершину. У вершині виявляється останній записаний вузол. Видалення вузлів із стека здійснюється також через вершину, але у зворотному порядку, тобто реалізується принцип обслуговування «останнім прийшов, першим вийшов». Видалити перший записаний вузол можна тільки після того, як будуть видалені із стека всі інші вузли. Основними функціями для маніпуляцій із стеками є наступні:

push – додавання (проштовхування) нового вузла. Ця функція вставляє новий вузол у вершину стека й встановлює покажчик вершини на цей новий вузол.

pop – видалення (виштовхування) вузла. Ця функція видаляє вузол з вершини стека, повертає його значення й встановлює покажчик вершини на наступний вузол стека.

Розглянемо реалізацію стека на прикладі структури:

struct node {

int data;

node *nxt; //Покажчик на наступний вузол

};

У програмі також знадобиться змінна – покажчик на вершину стека:

node *top;

Функція додавання нового вузла:

void push() {

node *temp=new node; //Створити новий вузол

cout<<"Element>> ";

cin>> temp->data; //Записати дані в новий вузол

temp->nxt=top; //Поставити вузол перед вихідною вершиною

top=temp; //Зробити новий вузол вершиною

}

Функція видалення вузла із стека:

int pop() {

if (top==NULL) {//Якщо стек порожній

cout<<"Stack is empty!";

return NULL; }

else {

int item=top->data; //Записати дані із стека в змінну

node *temp=top; //Створити новий вузол у вершині стека

top=top->nxt; // Перемістити вершину на наступний вузол

delete temp; //Видалити вузол з пам'яті

return item;

}

}

Приведемо також функцію очищення стека clear, що видаляє всі вузли стека й звільняє пам'ять.

void clear() {

node *temp;

while(top != NULL) { //Цикл для кожного вузла стека

temp = top; // Перезапис вершини

top = top->nxt; // Перемістити вершину на наступний вузол

delete temp; // Видалити вершину

};

}

2.1.3. Черги

Ще одним спеціальним типом списку є черги. Новий вузол може бути вставлений тільки в «хвіст» черги, а вибирається вузол тільки з «голови» черги. Таким чином, за допомогою черги реалізується принцип обслуговування «першим прийшов, першим вийшов». Основними функціями для маніпуляцій із чергами є наступні:

enqueue() – додавання нового вузла. Ця функція вставляє вузол у кінець черги й установлює покажчик хвоста черги на цей новий вузол. Алгоритм додавання вузла трохи видозмінюється, якщо черга була порожня.

denqueue() – видалення вузла. Ця функція видаляє вузол з голови черги, повертає його значення й установлює покажчик голови черги на наступний вузол.

Розглянемо реалізацію черги на прикладі структури node (див. розд. «2.1.2. Стеки»). У програмі також потрібні будуть змінні:

node *front; // Покажчик на голову черги

node *back; // Покажчик на хвіст черги

int len=0; //Довжина черги

Функція додавання вузла в чергу:

void enqueue(){

int item;

cout<<">> "; cin>>item; //Введення даних у вузол

if(len != 0) {//Якщо черга не порожня

back->nxt = new node; //Створити новий вузол у хвості

back = back->nxt; //Зробити новий вузол хвостом черги

back->data = item; //Записати дані в створений вузол

back->nxt = NULL; //Установити покажчик на NULL

}

else {

back = new node; //Створити новий вузол

back->data = item; //Записати дані

back->nxt = NULL;

front = back; //Установити «голову» там же, де «хвіст»

}

len++; //Інкрементувати число вузлів

}

Функція видалення вузла із черги:

int dequeue() {

assert(!(front==NULL)); //Перервати, якщо черга порожня

int item = front->data; //Зберегти дані з першого вузла

node *temp = front; //Тимчасовий покажчик на голову черги

front = front->nxt; //Наступний вузол зробити головою черги

delete temp; //Видалити вихідний перший вузол

if(front == NULL) //Якщо черга порожня

back = NULL;

len-і; //Декрементувати число вузлів

return item; //Повернути значення першого вузла

}

Приведемо також функцію очищення черги:

void clear() {

node *temp;

while(front != NULL) { //Поки покажчик голови не дійде

//до хвоста

temp = front; // Тимчасовий покажчик на голову

front = front->nxt; //Перемістити голову на один вузол

delete temp; //Видалити вихідний перший вузол

};

}