Основні теоретичні відомості

Стек – це частковий випадок односпрямованого списку, додавання елементів в який та виборка з якого виконуються з одного кінця, називаємого вершиною стека. Взяти елемент можна тільки з вершини стека, додати елемент можна тільки до вершини стека. При виборці елемент видаляється з стеку. Стек реалізує принцип обслуговування 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();

}