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();
}
|