Post-class 02/16

1 files changed, 358 insertions, 0 deletions

diff --git a/02-16.md b/02-16.md
new file mode 100644
index 0000000..67b9bad
--- /dev/null
+++ b/02-16.md
@@ -0,0 +1,358 @@
+[\<- 02/11](02-11.md)
+
+---
+
+# STL Vectors vs. STL Lists
+
+## Containers
+
+- STL includes three similar container classes
+	- **Vectors**: uses a dynamic array
+	- **Lists**: uses a doubly linked list
+	- **Deques**: uses a third mechanism that we will see in the future
+
+## Vectors
+
+```
+template <class T, class Alloc = allocator<T>>
+class vector;
+```
+
+- `T`:
+	- Type of the elements
+	- Aliased as member type `vector::value_type`
+- `Alloc`:
+	- Type of the allocator object used to define the storage model
+	- Allocators:
+		- Are an important component of the C++ Standard Library
+		- A common trait among STL containers is their ability to change size during the execution of the program
+		- To achieve this, some form of dynamic memory allocation is usually required
+		- Allocators handle all the requests for allocation and deallocation of memory for a given container
+
+### Vectors vs. Arrays
+
+- **Similar to arrays:**
+	- vectors use contiguous storage locations for their elements
+	- Elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays
+- **Unlike arrays:**
+	- vector size can change dynamically
+	- vectors use a dynamically allocated array to store their elements
+		- vectors do not reallocate each time an element is added to the container
+		- vector containers may allocate some extra storage to accommodate for possible growth
+	- vectors provide efficient element access (just like arrays) and relatively efficient adding or removing elements from its end
+
+### Vector Iterator
+
+```
+std::vector::begin
+iterator begin();
+const_iterator begin() const;
+```
+
+- Returns an integer pointing to the first element in the vector
+- If the container is empty, the returned iterator value should not be dereferenced
+
+```
+std::vector::end;
+iterator end();
+const_iterator end() const;
+```
+
+- Returns an iterator referring to the past-the-end element in the vector container
+
+### Vector::push_back
+
+```
+void push_back(const value_type& val);
+```
+
+- Adds a new element **at the end of the vector**
+- This effectively increases the container size by one, which causes an **automatic reallocation** of the allocated storage space **if - and only if - the new vector size surpasses the current vector capacity**
+
+![diagram](02-16_1.png)
+
+### Example 1
+
+```
+#include <iostream>
+#include <vector>
+
+int main(){
+	std::vector<int> myvector;
+	for(int i=1; i <= 5; i++) myvector.push_back(i);
+
+	std::cout << "myvector contains:";
+	for(std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it){
+		std::cout << ' ' << *it;
+	}
+
+	std::cout << '\n';
+	return 0;
+}
+```
+
+### Quiz
+
+- Write a function that asks for a group of numbers and outputs the numbers
+	- In original order
+	- In reverse order
+
+### Reverse Algorithm Example
+
+```
+#include <iostream>  //std::cout
+#include <algorithm> //std::reverse
+#include <vector>    //std::vector
+
+int main(){
+	std::vector<int> myvector
+
+	//set some values
+	for(int i = 1; i < 10; ++i) myvector.push_back(i); //1, 2, 3, 4, 5, 6, 7, 8, 9
+	std::reverse(myvector.begin(), myvector.end()); //9, 8, 7, 6, 5, 4, 3, 2, 1
+
+	//print out content
+	std::cout << "myvector contains:";
+	for(std::vector<int>::iterator it=myvector.begin(); it != myvector.end(); ++it){
+		std::cout << ' ' << *it;
+	}
+
+	std::cout << '\n';
+	return 0;
+}
+```
+
+```
+template <class BidirectionalIterator>
+void reverse(BidirectionalIterator first, BidirectionalIterator last){
+	while((first != last) && (first != --last)){
+		std::iter_swap(first, last);
+		++first;
+	}
+}
+```
+
+### Example 2
+
+```
+void pop_back();
+```
+
+- **Removes the last element in the vector**, effectively reducing the container size by one
+
+```
+#include <iostream>
+#include <vector>
+
+int main(){
+	std::vector<int> myvector;
+	int sum(0);
+	myvector.push_back(100);
+	myvector.push_back(200);
+	myvector.push_back(300);
+
+	while(!myvector.empty()){
+		sum += myvector.back();
+		myvector.pop_back();
+	}
+
+	std::cout << "The elements of myvector add up to " << sum << '\n';
+	return 0;
+}
+
+//Output
+The elements of myvector add up to 600
+```
+
+---
+
+# Using a Stack
+
+- Chapter 7 introduces the **stack** data type
+- Several example applications of stacks are given in that chapter
+- Another use: **backtracking to solve the N-Queens problem**
+
+## The N-Queens Problem
+
+- Suppose you have 8 chess queens and a chess board
+- Can the queens be placed on the board so that no two queens are attacking each other?
+
+### How the program works
+
+- The program uses a stack to keep track of where each queen is placed
+- Each time the program decides to place a queen on the board, the position of the new queen is stored in a record which is placed in the stack
+- We also have an integer variable to keep track of how many rows have been filed so far
+
+![example diagram](02-16_2.png)
+
+- Each time we try to place a new queen in the next row, we start by placing the queen in the first column...
+- If there is a conflict with another queen, then we shift the new queen to the next column
+- If another conflict occurs, the queen is shifted rightward again
+
+![example diagram](02-16_3.png)
+
+- When there are no conflicts, we stop and add one to the value of filled
+
+- Let's look at the third row. The first position we try has a conflict...
+	- so we shift to column 2. But another conflict arises...
+	- and we shift to the third column. Yet another conflict arises
+	- and we shift to column 4. There's still a conflict, so we try to shift rightward again
+		- But there's nowhere else to go
+- When we run out of room in a row:
+	- pop the stack, reduce `filled` by 1 and continue working on the previous row
+	- Now we continue working on row 2, shifting the queen to the right
+	- This position has no conflicts, so we can increase `filled` by 1, and move to row 3
+
+![example diagram](02-16_4.png)
+
+- In row 3, we start again at the first column
+
+### Pseudocode for N-Queens
+
+- Initialize a stack where we can keep track of our decisions
+- Place the first queen, pushing its position onto the stack and setting `filled` to 0
+- repeat these steps
+	- if there are no conflicts with the queens...
+		- Increase filled by 1. If filled is now N, then the algorithm is done. Otherwise, move to the next row and place a queen in the first column
+	- else if there is a conflict and there is room to shift the current queen rightward...
+		- Move the current queen rightward, adjusting the record on top of the stack to indicate the new position
+	- else if there is a conflict and there is no room to shift the current queen rightward...
+		- Backtrack~ Keep popping the stack, and reducing filled by 1, until you reach a row where the queen can be shifted rightward. Shift this queen right
+
+## Stack Description
+
+- Entries in a stack are ordered: There is one that can be accessed first (the one on top), one that can be accessed second (just below the top), ...
+- **We do not require that the entries can be compared using the `<` operator**
+- Stack entries must be removed in the reverse order
+	- Because of this property a stack is called a **Last-In/First-Out** data structure (LIFO)
+- Adding an entry to stack is called a **push** operation, and removing an entry from a stack is called a **pop** operation
+
+## Array Implementation of the Stack
+
+- Our stack template class definition uses two private member variables:
+	- A partially-filled array, called `data`, that can hold up to `CAPACITY` items
+	- A single member variable, `used`, that indicates how much partially-filled array is currently being used
+		- `data[0]` is at "the bottom" of the stack
+		- `data[used-1]` is at "the top" of the stack
+		- If the value of used is zero, this will indicate an empty stack
+- **Invariant of the `stack` Class** (Array Version)
+	- The number of items in the stack is stored in the member variable `used`
+	- The items in the stack are stored in a partially filled array called `data`, with the bottom of the stack at `data[0]`, the next entry at `data[1]`, and so on to the top of the stack at `data[used-1]`
+
+### Array Implementation
+
+```
+#ifndef SCU_COEN79_STACK1_H
+#define SCU_COEN79_STACK1_H
+#include <cstdlib> //Provides size_t
+
+namespace scu_coen79_7A{
+	template <class Item>
+	class stack{
+		public:
+			typedef std::size_t size_type;
+			typedef Item value_type;
+			static const size_type CAPACITY = 30;
+
+			//CONSTRUCTOR
+			stack() {used = 0;};
+
+			//MODIFICATION MEMBER FUNCTIONS
+			void push(const Item& entry);
+			void pop();
+
+			//CONSTANT MEMBER FUNCTIONS
+			bool empty() const {return (used == 0);};
+			size_type size() const {return used};
+			Item top() const;
+
+		private:
+			Item data[CAPACITY];
+			size_type used;
+	};
+}
+```
+
+## Stack as Dynamic Structure
+
+- Size can grow and shrink during execution
+- **The head of the linked list serves as the top of the stack**
+- Invariant of the Stack Class (Linked-List Version):
+	- The items in the stack are stored in a linked list, with the top of the stack stored at the head node, down to the bottom of the stack at the tail node
+	- The member variable `top_ptr` is the head pointer of the linked list of items
+
+## The Standard Library Stack Class
+
+- The C++ Standard Template Library (STL) has a stack class
+- Stack is specified as a template class
+- The most important member functions are:
+	- `push`: to add an entry to the top of the stack
+	- `pop`: to remove the top entry
+	- `top`: to get the item at the top of the stack without removing it
+- There are no functions that allow a program to access entries other than the top entry
+- **Stack underflow**: If a program attempts to pop an item off an empty stack
+	- To help you avoid a stack underflow, the class provides a member function to test whether a stack is empty
+- **Stack overflow**: If a program attempts to push an item onto a full stack
+
+```
+template <class T, class Container = deque<T>> class stack;
+```
+
+- **stacks** are implemented as *container adaptors*
+- **Container adaptors** are classes that use an encapsulated object of a specific container class as its *underlying container*, providing a specific set of member functions to access its elements
+- The container shall support the following operations:
+	- `empty`
+	- `size`
+	- `top` (or `back`)
+	- `push_back`
+	- `pop_back`
+- The standard container classes **vector**, **deque**, and **list** fulfill these requirements
+
+```
+#include <iostream> //std::cout
+#include <stack>    //std::stack
+
+int main(){
+	std::stack<int> mystack;
+	mystack.push(1);
+	mystack.push(2);
+	mystack.top() += 10;
+	std::cout << "mystack.top() is now " << mystack.top() << '\n';
+	return 0;
+}
+
+//Output
+mystack.top() is now 12
+```
+
+### STL Stack Implementation
+
+```
+template<class T, class C = deque<T>>
+class std::stack{
+	protected: C c;
+	public:
+		typedef typename C::value_type value_type;
+		typedef typename C::size_type size_type;
+		typedef C container_type;
+		explicit stack(const C& a = C()) : c(a){} //Inherit the constructor
+		bool empty() const {return c.empty();};
+		size_type size() const {return c.size();};
+		value_type& top() const {return c.back();};
+		const value_type& top() const {return c.back();};
+		void push(const value_type& n) {c.push_back(n);};
+		void pop() {c.pop_back();};
+};
+```
+
+## Summary
+
+- A stack is a Last-In/First-Out (**LIFO**) data structure
+- The accessible end of the stack is called the **top**
+- Adding an entry to a stack is called a **push** operation
+- Removing an entry from a stack is called a **pop** operation
+- Attempting to push an entry onto a full stack is an error known as a **stack overflow**
+- Attempting to pop an entry off an empty stack is an error known as a **stack underflow**
+- A stack can be implemented as a **partially filled array** or a **linked list**
+- Stacks have many uses in computer science
+	- The **evaluation and translation of arithmetic expressions** are two common uses