# Chapter 5 Stack
## What is stack?
Stack is a FILO linear data structure.
which means we can only access the top of elements.
## ADT stack basic operations
push(): insert an element at the top of the stack.
pop(): remove the element on the top of the stack.
peek(): to see the element on the top of the stack.
isEmpty(): check if the stack is empty.
## Implementation of ADT stack
* By using linked-list
* By using array
* By using vectors or others implemented structure.

## Implementation : CYCU DS1 ex3

class stack{
private:
 struct node{
    string data;
	node* next;
	node* last;
 }; // Doubly linked list

 node* tail = nullptr;
 node* top = nullptr;
public:
 void empty(){
    while(!isEmpty()) pop();
 } // empty() 
 void push(string data){
	node* temp = new node;
	temp->data = data;
	temp->next = top;
	temp->last = nullptr;
	if(top != nullptr) top->last = temp;
	top = temp;
	if(top->next == nullptr) tail = top;
 } // push()

 void pop(){
  node* temp;
  if(top == nullptr) return;
  if(top->next != nullptr) top->next->last = nullptr;
  temp = top;
  top = top->next;
  delete temp;
 } // pop()

 string peek(){
  if(top != nullptr) return top->data;
  return "";
 } // peek()

 bool isEmpty(){
  if(top == nullptr) return true;
  return false;
 } // isEmpty()

 void printAll(){
  node* temp = tail;
  cout << "Postfix expression: " << temp->data ;
  temp = temp->last;
  while(temp != nullptr) {
   cout << ", " << temp->data;
   temp = temp->last;
  } // while
  cout << endl;
 } // PrintAll()

 string get(int index){
  node* temp = tail;
  while(index-- > 0){
    temp = temp->last;
	if(temp == nullptr)
	return "";
  } // while
			
  return temp->data; 
 } // get()
}linkedlist;

Comparison
1. array-based(fixed-size) stack can get full.
2. pointer-based stack is more efficent.
3. reusing implemented class might save programming time.

## applications
1.deal with postfix and prefix expressions
2.backtracking
3.reverse data
4.process function calls in programs
# Chapter 6 Queue
## What is Queue?
Queue is a FIFO(LILO) linear data structure.
which means we can only access the front of elements.
## ADT stack basic operations
enqueue(): insert an element at the front of the Queue.
dequeue(): remove the element at the front of the Queue.
getFront(): to see the element at the front of the Queue.
isEmpty(): check if the Queue is empty.
## Implementation of ADT queue
* By using linked-list
* By using array
* By using vectors or others implemented structure.

## Implementation : CYCU DS1 ex4
> https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

#ifndef _JobQueue_HPP
#define _JobQueue_HPP
class JobQueue {
 vector<jobType> data;
 int qMax; // max size of queue
 //*********************************************************/
 // The above are private data members
 //*********************************************************/
public:
 int avail; // the time when cook is available
 //*********************************************************/
 // The above are public data members
 //*********************************************************/
 JobQueue():qMax(0), avail(0) {qMax=0;} // constructor of no-space queue
 JobQueue(int maxS): avail(0) {qMax = maxS;}// constructor of an empty queue
 int size() const { return data.size(); } // get the current queue length
 bool isEmpty() const { return data.empty();} // check whether it is empty
 bool isFull() const { return (data.size() >= qMax); } // check whether it is full
 void enQueue(jobType input){ data.push_back(input);} // append a new element
 jobType getFront(){return data.front();} // get the first element
 void Pop(){data.erase(data.begin());} // drop the first element
 //*********************************************************/
 // The above are public methods.
 //*********************************************************/
}; // end JobQueue
#endif //_JobQueue_HPP

>https://www.geeksforgeeks.org/array-implementation-of-queue-simple/
https://alrightchiu.github.io/SecondRound/queue-introjian-jie-bing-yi-linked-listshi-zuo.html

Comparison
1. array-based(fixed-size) stack can get full.
2. pointer-based stack is more efficent.
3. reusing implemented class might save programming time.

## applications
1.Breadth-First Search and Level-Order Traversal from tree
2.proccesing scheduling in operating system

# Chapter 7 Algorithm efficency
## How can we measure algorithm efficency?
one simple way is to count how many operations it needs in order to find the answer across different input sizes.
furthermore, we use Big O to express time complexity.
### cases
* base case: The best case is which requires the least number of operations.
* worse case: The worse case is which requires the max number of operations.
* average case: The average case is the middle number of operating time.
## Efficency of sorting algorithm

### bubble sort 
### insertion sort 
### merge sort 
### radix sort 
)
### quick sort 
### shell sort ![]
## Implementation : CYCU DS1ex5

#include <iostream> // iostream
#include <fstream> // filestream
#include <sstream> // stringstream
#include <string> // string
#include <vector> // vector
#include <ctime> // clock_t
using namespace std;

struct school{
 string gNO;
 string sNO;
 string data;
};
int strcmp(string a, string b){
  if(a.size()>b.size()) return 1;
  if(b.size()>a.size()) return -1;
  if(a > b) return 1;
  if(b > a) return -1;
  return 0;
} // strcmp()
// above is gloabal function and struct//

template <typename T> class Sort{
private:
vector<T> lines;
string fName;
string currentLine;
clock_t sortTime;
fstream ifs;
// The above are private data members //
void reset(){vector<T>().swap(lines);fName.clear();currentLine.clear();ifs.close();} // initialize
void dataInput(){
 string skip;
 for(int i=0;i<3;++i){getline(ifs,skip);} // skip first 3 lines
 while(getline(ifs,currentLine)){
  school currentData;
  currentData.data = currentLine;
  stringstream ss(currentLine);
  getline(ss, currentData.sNO, '\t');
  for(int i=0;i<7;++i)getline(ss, skip, '\t');
  getline(ss, currentData.gNO, '\t');
  lines.push_back(currentData);
  // input data to struct
 } // while()
} // datainput()
void save(string type, vector<T> data){
  type.append(fName);
  // create name of newfile //
  type.append(".txt");
  ofstream ofs(type);
  for(int i=0;i<data.size();++i)ofs<<data[i].data<<endl;
  // save sorted data into new file //
  ofs.close();
} // save()
bool isGreater(T a,T b){
  if(strcmp(a.gNO,b.gNO) > 0) return true;
  if(strcmp(a.gNO,b.gNO) == 0 && strcmp(a.sNO,b.sNO) > 0) return true;
  return false;
} // cmp()
void quicksort(vector<T> & data,int pivot,int right){
 if(pivot < right){
  int i=pivot; // left agent
  int j=right+1; // right agent
  while(true){
    while(i+1 < data.size() && isGreater(data[++i],data[pivot])); 
    // Visit from the most left to the right until found a value greater than pivot //
    while(j>0 && isGreater(data[pivot],data[--j]));
    // Visit from the most right to the left until found a value smaller than pivot //
    if(i>=j)break; // Ends loop if two agents met.
    swap(data[i],data[j]); // if left and right agent didn't meet, swap them //
  } // while()
  swap(data[pivot],data[j]); // find the exact position of data[pivot]!
  quicksort(data,pivot,j-1); // recursive: greater part
  quicksort(data,j+1,right); // recursive: smaller part
 } // if()
} // quicksort()
void merge(vector<T> & vec,int first,int mid,int end){
  vector<T> leftvec(vec.begin()+first, vec.begin()+mid+1);
  vector<T> rightvec(vec.begin()+mid+1, vec.begin()+end+1);
  // split 2 vectors
  rightvec.push_back({});
  leftvec.push_back({});
  // add empty element (to compare)
	int left=0,right=0;
	for(int i=first;i<=end;i++){
	 if(isGreater(rightvec[right],leftvec[left])) vec[i]=rightvec[right++];
   else vec[i]=leftvec[left++];
   // put them into right position
	} // for()
} // merge()
void mergesort(vector<T> & data,int left,int right){
  if(left<right){
   int mid = (right+left)/2;
   mergesort(data,left,mid); // recursive: left part
   mergesort(data,mid+1,right); // recursive: Right part
   merge(data,left,mid,right); // merge
  } // if
} // mergesort()
template<int x>void LSDFDigit(int max_length, vector<school> vec[x][x], vector<school> data){
  for(int i=0;i<data.size();i++)vec[0][data[i].gNO[data[i].gNO.size()-1]-'0'].push_back(data[i]);
} // LSDfirstDigit()
template<int x>void LSDODigit(int i, vector<school> vec[x][x]){
  for(int j=0;j<10;j++){
    // read data from last bucket 
    for(int k=0;k<vec[i-1][j].size();k++)
    if(vec[i-1][j][k].gNO.size()<=i)vec[i][0].push_back(vec[i-1][j][k]);
    else {
      int n = vec[i-1][j][k].gNO[vec[i-1][j][k].gNO.size()-i-1]-'0';
      vec[i][n].push_back(vec[i-1][j][k]);
    } // else
  } // for()
} // LSDotherDigit()
void radixAscen(vector<school> & data){
  // get the max_length of gNO
  int max_length = 0;
  for(int i=0;i<data.size();i++) 
   if(data[i].gNO.size()>max_length)max_length = data[i].gNO.size();
  // find max_length
  vector<school> vec[max_length][10];
  LSDFDigit(max_length,vec,data);
  for(int i=1;i<max_length;i++)
   LSDODigit(i,vec);
  // radix sort
  data.clear(); // clear proto data
  for(int i=9;i>=0;i--)
   for(int j=vec[max_length-1][i].size()-1;j>=0;j--)
    data.push_back(vec[max_length-1][i][j]);
  // reverse vector to decending
} // radixAscen()
// The above are private methods //
public:
Sort():currentLine(""),fName(""),sortTime(0){} // constructor
bool read(){
  string fileID;
  while(true){
  cout << endl << "Input a file number (e.g., 501, 502, 503, ...[0]Quit): ";
  cin >> fileID;
  if(fileID.compare("0")==0)break;
  fName.clear();
  fName.append("input");
  fName.append(fileID);
  fName.append(".txt");
  // create name of file //
  ifs.open(fName); 
  if(ifs.is_open()){ 
   dataInput(); // input data to vector
   fName = fileID;
   return true;
  } // if(ifs.is_open())
  cout << endl << "### input" << fileID << ".txt does not exist! ###" << endl;
  } // while()
  return false;
} // read()
void ssort(){
  vector<T> sorted = lines;
  clock_t start = clock();
  for(int i=0;i<sorted.size()-1;++i){
    int max=i; // assume the first element is the biggest
    for(int j=i+1;j<sorted.size();++j){
     if(isGreater(sorted[j],sorted[max]))max=j; // compare 2 elements
    } // visit all remained elements to find biggest
    if(max!=i)swap(sorted[max],sorted[i]); // swap 2 elements if they are not the same
  } // every loop secure the biggest in remains
  sortTime = clock();
  cout << endl << "selection sort: " << sortTime-start << " ms";
  save("select_sort",sorted);
} // selection sort
void bsort(){
  vector<T> sorted = lines;
  clock_t start = clock(); 
  for(int i=0;i<sorted.size()-1;++i){
    for(int j=0;j<sorted.size()-1;++j){
      if(isGreater(sorted[j+1],sorted[j]))swap(sorted[j],sorted[j+1]); // compare 2 elements 
    } // compare each element with its next element if necessary swap them
  } // every loop secure the smallest in remains
  sortTime = clock();
  cout << " bubble sort: " << sortTime-start << " ms" << endl;
  save("bubble_sort",sorted);
} // bubble sort
void msort(){
  vector<T> sorted = lines;
  clock_t start = clock();
  mergesort(sorted,0,sorted.size()-1);
  sortTime = clock();
  cout << "merge sort: " << sortTime-start << " ms";
  save("merge_sort",sorted);
} // merge sort
void qsort(){
  vector<T> sorted = lines;
  clock_t start = clock();
  quicksort(sorted,0,sorted.size()-1);
  sortTime = clock();
  cout << " quick sort: " << sortTime-start << " ms" << endl;
  save("quick_sort",sorted);
} // quick sort
void rsort(){
  vector<T> sorted = lines;
  clock_t start = clock();
  radixAscen(sorted);
  sortTime = clock();
  cout << "radix sort: " << sortTime-start << " ms" << endl;
  save("radix_sort",sorted);
} // radix sort
~Sort(){reset();} // destructor
// The above are public methods //
};
#endif // _DS5SORT_HPP_

>Ref:
>https://runestone.academy/ns/books/published/cppds/Sort/TheShellSort.html
>https://levelup.gitconnected.com/sorting-algorithms-selection-sort-bubble-sort-merge-sort-and-quicksort-75479f8f80b1
>https://www.alphacodingskills.com/python/pages/python-program-for-radix-sort.php
# Chapter 8 Tree
## teminology

## recursive traversal

## non-recursive traversal