стек

Стек у С++ реалізований у вигляді контейнера (його потрібно підключити #include <stack> ). Для нього передбачені такі функції:

stack < a > b - створити стек типу a з іменем b;

b.push (x) -- додати у стек b елемент x (відповідного типу);

b.pop () - видалити верхній елемент стеку;

b.top () -- показати значення верхнього елемента стеку;

b.size () - повернути кількість елементів у стеку;

b.empty () - true, якщо стек порожній, інакше -- false.

Приклад програми роботи зі стеком:

stack < int > st;             // створення стеку типу integer в c++

st.push (1);                  // [1]

st.push (2);                  // [1][2]

st.push (3);                  // [1][2][3]

cout << st.top () << "\n";    // [1][2]->[3]<-, виводимо "3"

st.push (4);                  // [1][2][3][4]

cout << st.top () << "\n";    // [1][2][3]->[4]<-, виводимо "4"

st.pop ();                    // [1][2][3]

st.pop ();                    // [1][2]

st.pop ();                    // [1]

cout << st.top () << "\n";    // ->[1]<-, виводимо "1"



Суть стандартних функцій роботи зі стеком ілюструє наступний код (стек при цьому зберігається у масиві)

Задача 1. З клавіатури вводяться текстові рядки. Якщо зчитано слово, то записати його у стек. Якщо зчитано "-”, то видалити зі стеку останній елемент. Якщо зчитано "*", то надрукувати стек

Задача 2. Перевірка правильності розстановки дужок одного типу ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Тестові дані до задачі 2

Задача 3. Перевірка правильності розстановки дужок різних типів ( [ ) ] - помилка

Тестові дані до задачі 3

Розв'язки  задач:
# include 
# include 
#include  
using namespace std;
 
int main ()
{
	setlocale(LC_ALL, "Ukrainian");
	stack < string > st;  // створення стеку типу string 
	string a;			// створення змінної для введення з клавіатури
	cin >> a;           // введення рядка з клавіатури 
	while (a!="*")		// поки введений рядок не рівний "*"
	{
	if (a !="-")		// якщо введений рядок не рівний "-"
		st.push (a);    // записати у стек введений рядок
	else				// інакше
		st.pop();		// видалити зі стеку останній елемент
	cin >> a;			// введення нового рядка з клавіатури 
	}
	while (st.empty() !=true) // поки стек не порожній
	{
		cout << st.top () << "\n";	// друкувати верхній символ стеку
		st.pop();					// видалити зі стеку останній елемент
	}

    system ("pause"); 
    return 0;
}

Задача 2
# include 
# include 
#include  
using namespace std;
 
int main ()
{
	setlocale(LC_ALL, "Ukrainian");
	stack < char > st;  // створення стеку типу char 
	string a;			// створення змінної для введення з клавіатури
	cin >> a;           // введення рядка з клавіатури 
	int symb=0;			// номер символа, який розглядається 
	bool pok=false;		// показник видалення з порожнього стека = false
	while (a[symb]<=a.length())		// поки не дійдемо до останнього символа 
	{
	if (a[symb]=='(')		// якщо поточний символ = '('
		st.push(a[symb]);	// записати символ у стек 
	if (a[symb]==')')		// якщо поточний символ = ')'
		if (st.empty() != true)	// стек не порожній
			st.pop();		// видалити символ зі стеку
		else				// інакше
			{
				pok=true;	// показник стає true
				break;		// достроковий вихід з циклу break
			}
	symb=symb+1;			// переходимо до наступного символу
	}
	if ((pok==true) || (st.empty() != true))	// якщо показник true або стек не порожній (залишились дужки)
		cout <<"Hi" << "\n";	// надрукувати Ні
	else						// інакше
		cout <<"Tak" << "\n";	// надрукувати Так
	

    system ("pause"); 
    return 0;
}
Last modified: Wednesday, 22 October 2014, 7:00 AM