Теоретична частина. Стек (англ. Stack – стопка) – це структура даних, в якій новий елемент завжди записується в її початок (вершину) і черговий елемент

Стек (англ. Stack – стопка) – це структура даних, в якій новий елемент завжди записується в її початок (вершину) і черговий елемент, який читається, також завжди вибирається з її початку. У стеках використовується метод доступу до елементів LIFO (Last Input – First Output, "останнім прийшов – першим вийшов"). Найчастіше принцип роботи стека порівнюють зі стопкою тарілок: щоб взяти другу зверху, потрібно спочатку взяти верхню.

Стек – це список, у якого доступний один елемент (одна позиція). Цей елемент називається вершиною стека. Взяти елемент можна тільки з вершини стека, додати елемент можна тільки в вершину стека. Наприклад, якщо записані в стек числа 1, 2, 3, то при подальшому витяганні отримаємо 3,2,1.

Опис стека:

struct імя_типа {

інформаційне поле;

адресне поле;

};

де інформаційне поле – це поле будь-якого раніше оголошеного або стандартного типу;

адресне поле – це покажчик на об'єкт того ж типу, що й обумовлена структура, в нього записується адреса наступного елементу стека.

Наприклад:

struct list {

type pole1;

list *pole2;

} stack;

Стек як динамічну структуру даних легко організувати на основі лінійного списку.

Опис елементів стека аналогічно опису елементів лінійного односпрямованого списку. Тому оголосимо стек через оголошення лінійного односпрямованого списку:

struct Stack {

Single_List *Top;//вершина стека

};

..........

Stack *Top_Stack;//вказівник на вершину стека

Операції із стеком

Створення стеку:

void Make_Stack(int n, Stack* Top_Stack){

if (n > 0) {

int tmp;//додаткова змінна

cout << "Введіть значення ";

cin >> tmp; //введення значення інформаціоного поля

Push_Stack(tmp, Top_Stack);

Make_Stack(n-1,Top_Stack);

}

}

Друк стека:

void Print_Stack(Stack* Top_Stack){

Print_Single_List(Top_Stack->Top);

}

Добавлення елементу у вершину стека:

void Push_Stack(int NewElem, Stack* Top_Stack){

Top_Stack->Top =Insert_Item_Single_List(Top_Stack->Top,1,NewElem);

}

Вилучення елементу із вершини стеку:

int Pop_Stack(Stack* Top_Stack){

int NewElem = NULL;

if (Top_Stack->Top!= NULL) {

NewElem = Top_Stack->Top->Data;

Top_Stack->Top = Delete_Item_Single_List(Top_Stack->Top,0);

//видаляємо вершину

}

return NewElem;

}

Перевірка на порожність стеку:

bool Empty_Stack(Stack* Top_Stack){

return Empty_Single_List(Top_Stack->Top);

}

Очистка стеку:

void Clear_Stack(Stack* Top_Stack){

Delete_Single_List(Top_Stack->Top);

}

Черга – це структура даних, що представляє собою послідовність елементів, утворених в порядку їх надходження. Кожен новий елемент розміщується в кінці черги; елемент, що стоїть на початку черги, вибирається з неї першим. У черзі використовується принцип доступу до елементів FIFO (First Input – First Output, "перший прийшов – першим вийшов"). У черзі доступні два елементи (дві позиції): початок черги і кінець черги. Помістити елемент можна тільки в кінець черги, а взяти елемент тільки з її початку.

Опис черги:

struct імя_типа {

інформаційне поле;

адресне поле1;

адресне поле2;

};

Операції із чергою:

Створення черги:

void Make_Queue(int n, Queue* End_Queue){

Make_Double_List(n,&(End_Queue->Begin),NULL);

Double_List *ptr; //допоміжний вказівник

ptr = End_Queue->Begin;

while (ptr->Next!= NULL)

ptr = ptr->Next;

End_Queue->End = ptr;

}

Друк черги:

void Print_Queue(Queue* Begin_Queue){

Print_Double_List(Begin_Queue->Begin);

}

Добавлення елементу в кінець черги:

void Add_Item_Queue(int NewElem, Queue* End_Queue){

End_Queue->End = Insert_Item_Double_List(End_Queue->End,

0, NewElem)->Next;

}

Вилучення елементу з початку черги:

int Extract_Item_Queue(Queue* Begin_Queue){

int NewElem = NULL;

if (Begin_Queue->Begin!= NULL) {

NewElem = Begin_Queue->Begin->Data;

Begin_Queue->Begin=Delete_Item_Double_List(Begin_Queue->Begin,0);

//удаляем вершину

}

return NewElem;

}

Перевірка на порожність черги:

bool Empty_Queue(Queue* Begin_Queue){

return Empty_Double_List(Begin_Queue->Begin);

}

Очистка черги:

void Clear_Queue(Queue* Begin_Queue){

return Delete_Double_List(Begin_Queue->Begin);

}