STACK

• 말 그대로 쌓는 것이다. Fisrt Come last Out의 개념이다. 음식점에 tray 선반들이 쌓여있는 개념이다.

#include <bits/stdc++.h>
using namespace std;

int Stack[100], ind;

void push (int x) {
    ++ind;
    Stack[ind] = x;
}

bool isEmpty() {
    if (ind >= 1) return false;
            else  return true;
}

void pop () {
    Stack[ind] = 0;
    --ind;
}

int top () {
    return Stack[ind];
}
int main()
{
    ind = 0;

    push(1);
    push(2);

    if (! isEmpty()) cout<<top();

    pop();
    pop();

    return 0;
}

Application of STACK

• 주로 블랜캣이 제대로 사용이 되고 있는지 아래와 같은 Application에 쓰인다.

#include <bits/stdc++.h>
using namespace std;

char input[1000]; // 1 byte
int Stack[1000], ind; // 4 bits

void push(int x)
{
    Stack[++ind] = x;
}

bool Empthy()
{
    if (ind > 0)
    {
        return false;
    }
    else
    {
        return true;
    }
}

bool verify(char input[])
{
    ind = 0;

    int n = strlen(input); // how many character is in

    for(int i=0; i<n; ++i)
    {
        if (input[i] == '(') push(1);
        if (input[i] == '[') push(2);
        if (input[i] == '{') push(3);

        if (input[i] == ')')
        {
            //if the stack is empty, or the last parentheis is different
            // than the onew we cloased, then the input is wrong
            if(Empthy() || Stack[ind] != 1)
                return false;
            else
                Stack[ind] = 0;
                --ind;
        }
        if (input[i] == ']')
        {
            //if the stack is empty, or the last parentheis is different
            // than the onew we cloased, then the input is wrong
            if(Empthy() || Stack[ind] != 2)
                return false;
            else
                Stack[ind] = 0;
                --ind;
        }
        if (input[i] == '}')
        {
            //if the stack is empty, or the last parentheis is different
            // than the onew we cloased, then the input is wrong
            if(Empthy() || Stack[ind] != 3)
                return false;
            else
                Stack[ind] = 0;
                --ind;
        }
    }

    if (ind == 0 )
        return true; // if the stack is empty, then the input is ok
    else
        return false;
}

int main()
{
    cin>>input;

    cout<<verify(input);

    return 0;
}

Introduction

• We can improve linked lists by making them doubly linked as well as created a tail pointer

Why is it Important?

• Trees are some of the most used data structures in computer science. They link information together in a relational way. You can use them to sort, to store information, to make inferences, and so much more. They are even used in databases to help index (find) the data in the database.

Lesson Notes

Trees

• Trees are known as a hierarchical data structure. Instead of pointing from one piece of data to the next, a tree has many different paths that you can take from each node. This creates a system of parents, and children.

• Parents are the nodes that are directly above another node, while children are ones that are directly below. For example, node 23 is a child of node 17, and node 17 is therefore the parent of node 23. However, the relationship is only a direct relationship. So, node 67 is not a child of node 23, even though it’s one layer lower.

• The layers of the tree are also important. They are known as the height of tree. Trees are also typically one directional, so you go from parent, to child, to child, to child, etc. You don’t typically go back up the tree for any purpose, except maybe a printing of the tree.

• You also have nodes called “leaves”. These are the nodes without any children, meaning they are at the end of the tree structure. Once you reach them, you cannot go any further in the tree.

Tree Structures

• Trees can have a variety of structures. They can have a set number of children or have an infinite amount. It all comes down to how you want to use them. A special type of tree however is known as the Binary Search Tree (BST).

Binary Search Tree

• A binary search tree is a tree with these rules:
  • Each node can only have at most two children
  • All right children must be greater than
  • All left children must be less than or equal to

• Through these rules we create a tree which can actually be used to search for things. Because we know the above rules, we can actually traverse the tree to find a number. The above picture is a binary search tree.

• Let’s see if 19 is in the tree. We take the root node (the one at the very top) 50, and ask, is 19 greater or less than this node of 50? Well, it’s less. So we look at the left child. 50->17. We then ask the same question, is 19 greater or less than 17? It’s greater, so we take the right child. 50- >17->23. Now is 19 greater or less than 23? It’s less than. We take the left child, and there we have it, the number is in the tree.

• If the number were for example, 22, we would do the same procedure, and find out that when we tried to look at the right child of 19, there is nothing there. We would then return that no, 22 is not in the tree.

• So with this ability to search the tree with only touching a few elements, we get some great time efficiencies with this.

• (This assumes random order of inserting. If you insert a series of consecutive numbers, you will grow the tree in a straight line, making all operations the same as a list, so O(n). There are more advanced trees known as red-black trees and AVL trees that make sure this never happens. But they are quite complex)

• Search: O(log n) – We only have to touch log elements (the height of the tree) to figure out if the element is in the list or not.

• Insert: O(log n) – Same with inserting in to the tree. We ask the same questions as above, and find the empty place in the tree, and insert there.

• Delete O(log n) – Same as the rest, we can delete by just asking the same questions.

Quiz

Applications

#include <bits/stdc++.h>

using namespace std;

ifstream f("data.in");
ofstream g("data.out");

int A[101], X, n; // supposed that we have numbers from 0-100

int maximum;

int main()
{
    f>>n; //number of elements
    for (int i=1; i<=n; ++i)
    {
        f>>X; // a New number
        ++A[X]; // increasing the appearance array

        maximum = max(maximum, X);
    }

    for (int i=0; i<=maximum; ++i)
    {
        if(A[i]>0){
            for (int j=1; j <= A[i]; ++j)
                cout<<i<<" ";
        }
    }
}

• data 셋중에 숫자가 겹치는 것들을 heap을 이용하여서 counting.

• 제일 많은 max값을 구한 것을 꺼내서, cout.

Introduction

• Sometimes the order of data within data structures is important. Certain sorting algorithms adhere to this importance, while others don’t. If a data structure takes order in to account(视为), we call it stable, if it doesn’t, we call it not stable or non-stable.

Why is it Important?

• It is important to understand what stability is. There are a lot of cases where stability matters, and understanding which sorting algorithms will get you a stable or non-stable result is important

Lesson Notes

• Say we have a data set that contains groups of information. It looks like this:

{ (Bob, A) (Chris, B) (Kathy, A) (Phillis, B) }

• This algorithm is already sorted in to alphabetic order. Now, let’s say we want to sort this algorithm based on the letters on the back end, so A’s come before B’s.

• If we use a non-stable sorting algorithm, we could very well get a result that looks like this:

{ (Chris, A) (Phillis, A) (Kathy, B) (Bob, B) }

• If you notice, the A’s and B’s have been sorted, however the order of the names wasn’t respected (Kathy now comes before Bob). Because of the non-stable nature of the sorting algorithm, we lost the alphabetical grouping of the names.

• This is situation where a stable sorting algorithm would be important. If we applied a stable sorting algorithm to this group, we would instead get:

{ (Chris, A) (Phillis, A) (Bob, B) (Kathy, B) }

• Now, not only are the names sorted by A’s and B’s, but they are also sorted with respect to the order they came in, which was alphabetical.

Sorting Algorithms

• Bubble Sort: Stable – This algorithm is stable because it just swaps the largest value up the structure to the top. If two objects are the same, no swap takes place. This means equal values that were to the left will stay to the left.
  • (2a 1 2b) -> (1 2a 2b) (The 2a will never swap with the 2b because swaps don’t take place when two values are equal)
• Selection Sort: Nonstable – By default selection sort isn’t stable. This is because it takes a number and swaps it to the left “sorted” side. This gives the possibility that a number can be swapped behind another equal number.
  • (2a 2b 1) -> (1 2b 2a) (The 2a was swapped with the lowest number 1 which was on the right side of 2b. The swap takes place, and the order is not preserved)

• Insertion Sort: Stable – Insertion sort uses a similar swapping mechanism as Bubble sort. It starts from the right while swapping, but never swaps equal values, meaning there is never a chance for elements positions to be flipped.

• Quick Sort: Nonstable – Quick sort uses a splitting mechanism to order to sort. If this “pivot” is a number which has a duplicate, there is a good chance the order will be broken.
  • (2a 2b 1) -> (1 2b 2a) (In this scenario, 2b was chosen as the pivot, anything less than it went to the left, and anything greater than or equal went to the right. 2a is equal so it went to the right, breaking the stability of the algorithm)
• Merge Sort: Stable – Merge Sort splits up the data and recombines it in a way that grabs the smallest element and sticks it back in to the array. It however adheres to the order of values, giving preference to values that are in the left subarray to maintain order.

Quiz