Упражнение 4 - Стек, опашка

Стек

Стекът е структура от данни, представляваща свързан списък, в който добавянето и премахването става само от единия край. За стека важи правилото „последен влязъл, първи излязъл“ (LIFO). Във файла stack.h е реализиран класът Stack. Следващата програма демонстрира използването му:

stack.cpp

#include <iostream>
#include "stack.h"

using namespace std;

template <class T>
Stack<T> reverse(Stack<T> a) {
	T x;
	Stack<T> b;
	while(a.pop(x)) b.push(x);
	return b;
}

int main() {
	Stack<int> s1;					// тук се вика конструкторът по подразбиране
	s1.push(2); cout << "push 2\n";
	s1.push(4); cout << "push 4\n";
	s1.push(6); cout << "push 6\n";
	cout << "s1:";
	s1.print();
	cout << endl;

	cout << "Stack<int> s2(s1), s3;\ns3 = s1;\ns3.push(7);\n";
	Stack<int> s2(s1), s3;				// тук се вика копиращият конструктор
	s3 = s1;					// тук се вика операторът за присвояване
	s3.push(7);
	cout << "s1:" << s1 << endl;			// тук се вика операторът за извеждане
	cout << "s2:" << s2 << endl;
	cout << "s3:" << s3 << endl;
	
	int a;
	s1.pop(a);
	cout << "\ns1.pop(a), a: " << a;
	
	cout << "\ns3.writeFile\n";
	s3.writeToFile("test.mp3");
	cout << "s1.readFile\n";
	s1.readFile("test.mp3");
	cout << "s1:" << s1 << endl;
	
	cout << "s2 = s1 = s3\n"; s2 = s1 = s3;
	cout << "\ns1:" << s1;
	cout << "\ns2:" << s2;
	cout << "\ns3:" << s3;
	cout << "\ns2.push(15)\n"; s2.push(15);
	cout << "\ns1:" << s1;
	cout << "\ns2:" << s2;
	cout << "\ns3:" << s3;

	cout << "\ns1.pop(): " << s1.pop(); cout << "\ns1:" << s1 << "\n";
	cout << "\ns1.pop(): " << s1.pop(); cout << "\ns1:" << s1 << "\n";
	cout << "\ns1.pop(): " << s1.pop(); cout << "\ns1:" << s1 << "\n";
	cout << "\ns1.pop(): " << s1.pop(); cout << "\ns1:" << s1 << "\n";
// 	cout << "\ns1.pop(): " << s1.pop(); cout << "\ns1:" << s1 << "\n";

	cout << "s1 = reverse(s2);\n";
	s1 = reverse(s2);				// тук копиращият конструктор се вика 2 пъти
							// 1-во защото подаваме стек, като параметър
							// 2-ро защото функцията връща стек
							// накрая се вика операторът за присвояване
	cout << "s1:" << s1 << endl;
	cout << "s2:" << s2 << endl;

	return 0;
}

Схемата, по-долу, показва стъпките при вмъкването на елемент в стек (методът push).

Следващата схема показва стъпките при измъкването на елемент от стек (методът pop).

Задача: Да се въведе от клавиатурата редица от числа, след което да се изведе в обратен ред. Да се използва стек.

Опашка

Опашката представлява свързан списък, в който можем да добавяме елементи само в единия край и да премахваме само от другия. За нея важи правилото „първи влязъл, първи излязъл“ (FIFO). Във файла queue.h е реализиран класът Queue. Следващата програма демонстрира използването му:

queue.cpp

#include <iostream>
#include <fstream>
#include "queue.h"

using namespace std;

template <class T>
Queue<T> increase(Queue<T> a) {
	T x;
	Queue<T> b;
	while(a.pop(x)) b.push(x + 1);
	return b;
}

int main(){
	Queue<int> q1;					// тук се вика конструкторът по подразбиране
	q1.push(2); cout << "push 2\n";
	q1.push(4); cout << "push 4\n";
	q1.push(6); cout << "push 6\n";
	cout << "q1:" << q1;
	cout << endl;

	cout << "Queue<int> q2(q1), q3;\nq3 = q1;\nq3.push(7);\n";
	Queue<int> q2(q1), q3;				// тук се вика копиращият конструктор
	q3 = q1;					// тук се вика операторът за присвояване
	q3.push(7);
	cout << "q1:" << q1 << endl;			// тук се вика операторът за извеждане
	cout << "q2:" << q2 << endl;
	cout << "q3:" << q3 << endl;
	
	int a;
	q1.pop(a);
	cout << "\nq1.pop(a), a: " << a;
	
	cout << "\nq3.writeFile\n";
	q3.writeToFile("test.mp3");
	cout << "q1.readFile\n";
	q1.readFile("test.mp3");
	cout << "q1:" << q1 << endl;
	
	cout << "q2 = q1 = q3\n"; q2 = q1 = q3;
	cout << "\nq1:" << q1;
	cout << "\nq2:" << q2;
	cout << "\nq3:" << q3;
	cout << "\nq2.push(15)\n"; q2.push(15);
	cout << "\nq1:" << q1;
	cout << "\nq2:" << q2;
	cout << "\nq3:" << q3;
	
	cout << "\nq1.pop(): " << q1.pop(); cout << "\nq1:" << q1 << "\n";
	cout << "\nq1.pop(): " << q1.pop(); cout << "\nq1:" << q1 << "\n";
	cout << "\nq1.pop(): " << q1.pop(); cout << "\nq1:" << q1 << "\n";
	cout << "\nq1.pop(): " << q1.pop(); cout << "\nq1:" << q1 << "\n";
// 	cout << "\nq1.pop(): " << q1.pop(); cout << "\nq1:" << q1 << "\n";

	cout << "q1 = increase(q2);\n";
	q1 = increase(q2);				// тук копиращият конструктор се вика 2 пъти
							// 1-во защото го подаваме, като параметър
							// 2-ро защото функцията връща опашка
							// накрая се вика операторът за присвояване
	cout << "q1:" << q1 << endl;
	cout << "q2:" << q2 << endl;

	return 0;
}

Опашката има широко приложение. Примерно в един mail сървър има опашка, в която се пазят писмата, които трябва да бъдат изпратени. Писмото влязло първо в опашката се изпраща най-напред.

Освен стандартната опашка има още опашка с приоритети. При нея изваждането на елементите става в някакъв ред, в зависимост от приоритета им. Това може да се реализира, като поддържаме опашката сортирана - при всяко вмъкване търсим точното място на елемента и го поставяме там. Друг вариант е елементите да са подредени по реда си на влизане, а при изваждането да търсим този с най-голям приоритет и да извадим него.

Декът (deque) представлява опашка, в която могат да се добавят или премахват елементи от двата края. По-точно има два вида дек:
- с ограничен вход, при който елементите могат да се премахват и от двата края, но вмъкването им става само от единия;
- с ограничен изход, при който вмъкване може да се прави и в двата края, но премахването става само от единия.

Задачка от книгата на Амерал:
Да се напише програма с декларирана само една променлива от тип char. Програмата трябва да чете ред с текст, с произволна дължина и да го изписва в обратен ред. Може да се използва функцията cin.get(ch), която прочита един символ от клавиатурата и го поставя в ch.

Съвет: яисрукер етйавзлопзи.

За тренировка класовете Stack и Queue да се снабдят с допълнителни методи, като: метод показващ дали структурата е празна, методи за запис и четене в и от файл, методи за обръщане реда на елементите и др.

Пермутации

Може да си мислите за пермутацията, като за наредено множество. За множеството 1 2 3 са възможни следните подредби:

Ако приемем, че елементите на множеството ни са в масива „a“, за да намерим следващата пермутация:

1. Намираме най-големия индекс i, за който a[i] < a[i+1]. Ако няма такъв пермутацията е последната.
2. Намираме най-големия индекс j > i, за който a[j] > a[i]. Такъв съществува, щом сме стигнали до тази стъпка, защото ако не друг то i+1 е такъв.
3. Разменяме местата на a[i] и a[j].
4. Обръщаме редицата след i-я индекс в обратен ред.

Горният алгоритъм е от Wikipedia - Permutation
Ето програма на C++, която го реализира:

permutation.cpp

#include <iostream>

using namespace std;

// Намира следващата пермутация за масива 'a'. Ако има такава връща 1. В противен случай връща 0.
int nextPermutation(int a[], int n) {
	
	// 1. Намираме най-големия индекс i, за който a[i] < a[i+1]. Ако няма такъв пермутацията е последната.
	bool lastPermutation = true;
	int i;
	for(i = n-2; i >= 0; i--)
		if(a[i] < a[i+1]) {
			lastPermutation = false;
			break;
		}
	if(lastPermutation) return 0;			// Пермутацията е последната.


	// 2. Намираме най-големия индекс j > i, за който a[j] > a[i].
	// Такъв съществува, щом сме стигнали до тази стъпка, защото ако не друг то i+1 е такъв.
	int j;
	for(j = n-1; j > i; j--)
		if(a[j] > a[i]) break;


	// 3. Разменяме местата на a[i] и a[j].
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;


	// 4. Обръщаме редицата след i-я индекс в обратен ред.
	int left = i+1;
	int right = n-1;
	while(left < right) {
		temp = a[left];
		a[left++] = a[right];
		a[right--] = temp;
	}

	return 1;
}

int main() {
	int const n = 3;
	int a[n] = {1, 2, 3};

	for(int i = 0; i < n; i++) cout << a[i] << ' ';		// отпечатваме 1-вата пермутация
	cout << endl;

	while(nextPermutation(a, n)) {				// докато има следваща пермутация
		for(int i = 0; i < n; i++) cout << a[i] << ' ';	// я отпечатваме на екрана
		cout << endl;
	}

	return 0;
}

Комбинации

Комбинация от n елемента от k-и клас е подмножество от k елемента на друго множество от n елемента. Нека не забравяме, че множеството е съвкупност от различни обекти. Тогава всички възможни комбинации от 5 елемента от 3-и клас са:

1 4 2 е същото множество, като 1 2 4, затова не го записваме 2 пъти.

Ако искаме да генерираме комбинации от 5 елемента, 3-ти клас, можем да го направим със следните вложени цикли:

int n = 5, k = 3;
int a[k+1];
for(a[1] = 1; a[1] <= n - k + 1; a[1]++)
	for(a[2] = a[1]+1; a[2] <= n - k + 2; a[2]++)
		for(a[3] = a[2]+1; a[3] <= n - k + 3; a[3]++) {
			for(int i = 1; i <= k; i++) cout << a[i] << ' ';
			cout << endl;
		}

Това напомня за програмата nested_loops.cpp имитираща променлив брой вложени цикли. С този подход можем да генерираме и комбинации от n елемента, от k-ти клас:

combination_1.cpp

#include <iostream>

using namespace std;

int const n = 5, k = 3;
int a[k+1];

void printArray() {
	for(int i = 1; i <= k; i++)
		cout << a[i] << ' ';
	cout << endl;
}

void f(int r) {
	if(r == k+1) {
		printArray();
	} else {
		for(a[r] = a[r-1]+1; a[r] <= n - k + r; a[r]++)
			f(r + 1);
	}
}

int main() {

	a[0] = 0;	// комбинациите се разполагат в масива от позиция 1 до позиция 3

// 	for(a[1] = a[0]+1; a[1] <= n - k + 1; a[1]++)			// r = 1
// 		for(a[2] = a[1]+1; a[2] <= n - k + 2; a[2]++)		// r = 2
// 			for(a[3] = a[2]+1; a[3] <= n - k + 3; a[3]++)	// r = 3
// 				printArray();

	f(1);
}

В следващата програма комбинациите се генерират една по една, както пермутациите в permutation.cpp. Алгоритъмът от книгата на Амерал е следният:

1. Намираме най-големия индекс i, за който a[i] може да бъде увеличено. Ако няма такъв, комбинацията е последната.
2. Увеличаваме a[i].
3. На a[i+1], ... , a[k] даваме техните най-малки възможни стойности. Елементите на „a“ са в нарастващ ред.

combination_2.cpp

#include <iostream>

using namespace std;

// Намира следващата комбинация за масива 'a'. Ако има такава връща 1. В противен случай връща 0.
int nextCombination(int a[], int n, int k) {

	// 1. Намираме най-големия индекс i, за който a[i] може да бъде увеличено.
	// Ако няма такъв комбинацията е последната.
	bool lastCombination = true;
	int i;
	for(i = k; i > 0; i--)
		if(a[i] < n - k +i) {
			lastCombination = false;
			break;
		}
	if(lastCombination) return 0;				// Комбинацията е последната.

	// 2. Увеличаваме a[i]
	a[i]++;

	// 3. На a[i+1], ... , a[k] даваме техните най-малки възможни стойности.
	// Елементите на 'a' са в нарастващ ред.
	for(int j = i + 1; j <= k; j++)
		a[j] = a[j-1] + 1;

	return 1;
}

int main() {
	int const n = 5, k = 3;
	int a[k+1] = {0, 1, 2, 3};

	for(int i = 1; i <= k; i++) cout << a[i] << ' ';	// отпечатваме 1-вата комбинация
	cout << endl;

	while(nextCombination(a, n, k)) {			// докато има следваща комбинация
		for(int i = 1; i <= k; i++) cout << a[i] << ' ';// я отпечатваме на екрана
		cout << endl;
	}

	return 0;
}

Упражнение 4 - Стек и опашка

Стек

Опашка

Пермутации

Комбинации