Summary Files Commits Branches @commit @diff @stats
path: root / Year 2 / Structures and data algorithms / 05-Seminar-02.11.2022 / exercises.cpp
blob: 0317cc305627ce2e9e4687ebe9b399567c2909f4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include "LinkedList.hpp"
#include <iostream>
#include <stack>
#include <queue>

// Ex1

template <class T>
void shuffle(LinkedList<T>& l) {
	auto fast = l.begin(), slow = l.begin(), end = l.end();
	while (fast != end) {
		++fast;
		if (fast != end) {
			++fast;
			++slow;
		}
	}
	int pops = 0;
	while (++slow != end) {
		l.pushFront(*slow);
		pops++;
	}
	while (pops-- > 0)
		l.popBack();
}

template <class T>
void print(LinkedList<T>& l) {
	for (const T& elem : l) {
		std::cout << elem << " ";
	}
	std::cout << std::endl;
}

void ex1() {
	LinkedList<int> l;
	l.pushBack(1);
	l.pushBack(2);
	l.pushBack(3);
	l.pushBack(4);
	l.pushBack(5);

	print(l);
	shuffle(l);
	print(l);
}

// Ex2

void print(LinkedList<std::stack<int>*>& l) {
	for (const std::stack<int>* elem : l) {
		if (!elem->empty())
			std::cout << elem->top() << " ";
	}
	std::cout << std::endl;
}

#define min(a,b) (a<b) ? a : b

void equalize(LinkedList<std::stack<int>*>& l) {
	std::queue<size_t> valueSize;
	std::queue<int> valueHolder;
	for (std::stack<int>* elem : l) {
		valueSize.push(elem->size());
		while (!elem->empty()) {
			valueHolder.push(elem->top());
			elem->pop();
		}
	}
	std::queue<int> leftovers;
	size_t amountPer = valueHolder.size() / l.size();
	for (std::stack<int>* elem : l) {
		size_t cpyOriginals = min(amountPer, valueSize.front());
		for (size_t i = 0; i < cpyOriginals; i++) {
			elem->push(valueHolder.front());
			valueHolder.pop();
		}
		for (int i = valueSize.front() - amountPer; i > 0; i--) {
			leftovers.push(valueHolder.front());
			valueHolder.pop();
		}
		valueSize.pop();
	}
	for (std::stack<int>* elem : l) {
		for (size_t i = amountPer - elem->size(); i > 0; i--) {
			elem->push(leftovers.front());
			leftovers.pop();
		}
	}
}

void ex2() {
	LinkedList<std::stack<int>*> l;
	l.pushBack(new std::stack<int>());
	l.back()->push(1);
	l.back()->push(2);
	l.back()->push(3);
	l.back()->push(4);
	l.back()->push(5);
	l.pushBack(new std::stack<int>());
	l.back()->push(6);
	l.back()->push(7);
	l.pushBack(new std::stack<int>());
	l.back()->push(8);
	l.back()->push(9);
	l.back()->push(10);
	l.back()->push(11);
	l.pushBack(new std::stack<int>());
	l.back()->push(12);

	print(l);
	equalize(l);
	print(l);
}

// Ex 3

// LinkedListNode<int>* partition(LinkedListNode<int>* head, int x) {
//
// }

int main() {
	ex2();
}