Основні теоретичні відомості
Стек – це частковий випадок односпрямованого списку, додавання елементів в який та виборка з якого виконуються з одного кінця, називаємого вершиною стека. Взяти елемент можна тільки з вершини стека, додати елемент можна тільки до вершини стека. При виборці елемент видаляється з стеку. Стек реалізує принцип обслуговування LIFO (last in – first out, останнім прийшов – першим пішов).
В динамічній пам’яті стек можна представити лінійним односпрямованим (перший елемент списку – вершина стека) та двоспрямованим списками. Щоб ініціалізувати стек достатньо покажчику на вершину стека задати значення NULL.
Основні операції над стеком: занести елемент у стек; вибрати елемент зі стеку; перевірка на порожність стеку; підрахувати кількість значень, що знаходяться у стеку.
Приклад 1. Програмна реалізація стеку у вигляді лінійного односпрямованого списку.
class Node
{ public:
char d; // дані
Node *next; // покажчик на наступний вузол
Node (char dat = 0) { d = dat; next = 0;} // конструктор
};
class Stack
{Node *top; // покажчик на вершину стека
public:
Stack() { top = 0;} // конструктор
~Stack(); // деструктор
void push(char d); // занесення елементу до стеку
void print(); // друк стеку
};
Розглянемо реалізацію методів класу. Метод push виділяє пам'ять під новий об’єкт типу Node та приєднує його до стеку, оновлюючи покажчики на його вершину:
void Stack::push(char d)
{
Node *pv = new Node(d); // виділення пам'яті під новий вузол
if(!top) { top = pv;} // формування вершини стеку
else // зв’язування нового вузла з попереднім:
{ pv->next= top;
top =pv;} // оновлення покажчика на вершину стеку
}
Метод друку стеку поелементно переглядає стек, переходячи по відповідним посиланням:
void Stack::print()
{ Node *pv = top;
cout << endl << " stack: ";
while(pv) { cout << pv->d << " ";
pv = pv->next; }
cout << endl;
}
Деструктор стеку звільняє пам'ять з-під усіх елементів стеку:
Stack::~Stack()
{ if(top)
{ Node *pv = top;
while(pv) {pv = pv->next;
delete top;
top = pv;}
}
}
Нижче наведений приклад програми, що використовує клас Stack. Програма формує стек рядку 'BETA' та друкує його на екран.
void main()
{
Stack S;
S.push('B');
S.push('E');
S.push('T');
S.push('A');
S.print();
getch();
}
Черга – це частковий випадок односпрямованого списку, додавання елементів в який виконується в один кінець, а виборка – з другого кінця. Розмістити елемент можна тільки в кінець черги, а взяти елемент тільки з її початку. При виборці елемент видаляється з черги. Черга реалізує принцип обслуговування FIFO (first in – first out, першим прийшов – першим пішов).
В динамічній пам’яті чергу можна представити лінійним односпрямованим списком з двома покажчиками (на початок та кінець черги) та двоспрямованим списком. Щоб ініціалізувати чергу достатньо покажчику на початок і/або на кінець черги присвоїти значення NULL. При виборі єдиного елемента з черги вона повинна виявитися порожньою.
Основні операції над чергою аналогічні операціям зі стеком (з урахуванням особливостей структури).
Приклад 2. Програмна реалізація черги у вигляді лінійного односпрямованого списку.
class Node
{public:
char d; // дані
Node *next; // покажчик на наступний вузол
Node (char dat = 0) { d = dat; next = 0;} // конструктор
};
class Queue
{ Node *pbeg, *pend; // покажчики на початок та кінець черги
public:
Queue() {pbeg = 0;} // конструктор
~Queue();// деструктор
void add(char d); // занесення елементу до черги
void print();// друк черги
};
Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об’єкт типу Node та приєднує його до черги, оновлюючи покажчики на її початок та кінець:
void Queue::add(char d)
{
Node *pv = new Node(d); // виділення пам'яті під новий вузол
if(!pbeg) {pbeg = pv; pend = pv;} // формування черги
else // зв’язування нового вузла з попереднім:
{pend->next=pv;
pend = pv;} // оновлення покажчика на кінець черги
}
Метод друку черги поелементно переглядає чергу, переходячи по відповідним посиланням:
void Queue::print()
{ Node *pv = pbeg;
cout << endl << " queue: ";
while(pv) {cout << pv->d << " ";
pv = pv->next; }
cout << endl;
}
Деструктор черги звільняє пам'ять з-під усіх елементів черги:
Queue::~Queue()
{ if(pbeg)
{ Node *pv = pbeg;
while(pv)
{ pv = pv->next;
delete pbeg;
pbeg = pv;
}
}
}
Нижче наведений приклад програми, що використовує клас Queue. Програма формує чергу рядку 'BETA' та друкує його на екран.
void main()
{
Queue Q;
Q.add('B');
Q.add('E');
Q.add('T');
Q.add('A');
Q.print();
getch();
}