[SDP/HEP] Added preparation for "homework" during class

3 files changed, 147 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp
new file mode 100644
index 0000000..db87f96
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp
@@ -0,0 +1,53 @@
+#ifndef STACK_DYNAMICSEQ
+#define STACK_DYNAMICSEQ
+
+template <class T>
+class Stack {
+	struct Node {
+		T value;
+		Node* next;
+
+		Node(const T& v, Node* n) : value(v), next(n) {}
+	};
+
+	Node* topNode;
+
+public:
+	Stack();
+	~Stack();
+	Stack(Stack& other) = delete;
+	Stack& operator=(const Stack& other) = delete;
+
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+Stack<T>::Stack() : topNode() {}
+
+template <class T>
+Stack<T>::~Stack() {
+	while (topNode != nullptr)
+		pop();
+}
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	topNode = new Node(v, topNode);
+}
+
+template <class T>
+void Stack<T>::pop() {
+	Node* old = topNode;
+	topNode = topNode->next;
+	delete old;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return topNode->value;
+}
+
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp
new file mode 100644
index 0000000..7f794e7
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp
@@ -0,0 +1,62 @@
+#ifndef STACK_DYNAMIC
+#define STACK_DYNAMIC
+
+template <class T>
+class Stack {
+	T* vals;
+	unsigned topInd;
+	unsigned size;
+
+	void resize();
+
+public:
+	Stack();
+	~Stack();
+	Stack(Stack& other) = delete;
+	Stack& operator=(const Stack& other) = delete;
+
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+void Stack<T>::resize() {
+	unsigned newSize = size << 1;
+	T* newVals = new T[newSize];
+	for (unsigned i = 0; i < size; i++)
+		newVals[i] = vals[i];
+	delete vals;
+	vals = newVals;
+	size = newSize;
+}
+
+template <class T>
+Stack<T>::Stack() {
+	vals = new T[1]; // for testing purposes its 1
+}
+
+template <class T>
+Stack<T>::~Stack() {
+	delete[] vals;
+}
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	if (topInd == size)
+		resize();
+
+	vals[topInd++] = v;
+}
+
+template <class T>
+void Stack<T>::pop() {
+	topInd--;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return vals[topInd - 1];
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp
new file mode 100644
index 0000000..91fdb65
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp
@@ -0,0 +1,32 @@
+#ifndef STACK_STATIC
+#define STACK_STATIC
+
+#define STACK_SIZE 1024
+
+template <class T>
+class Stack {
+	T vals[STACK_SIZE];
+	unsigned topPos = 0;
+
+public:
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	vals[topPos++] = v;
+}
+
+template <class T>
+void Stack<T>::pop() {
+	topPos--;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return vals[topPos - 1];
+}
+
+#endif