210826_#1-Stack, Queue

210826_#1-Stack, Queue

---

1. 스택(Stack)의 특징

---

1. 삽입과 삭제가 같은 쪽에서 이루어지는 구조다.
2. 나중에 입력된 데이터가 먼저 출력하는 메모리 사용법이다(Lifo - last in first out)
3. 데이터가 저장될 때 입력된 데이터의 위치를 스택 포인터가 가리키고 있다.
4. 데이터가 입력될 때 포인터는 1씩 증가하며, 스택 크기보다 큰 값을 갖게 되면 데이터를 더 이상 기억할 수 없다->Overflow

---

• stack 활용

1.함수를 호출하여 복귀할때 사용
2.깊이 우선 탐색(DFS)에서 사용
3.재귀적 함수를 호출할대 사용
4.인터럽트 수행 시 현재 수행중인 프로세스의 복귀 주소를 저장할때 사용

5

5.수식을 우선적으로 연산하기 위한 방법으로 사용

1.    (4 + 5) * 2 - 3
2.    (4 5 +) * 2 - 3
3.    (4 5 + 2 * )-3
4. --> 4 5 + 2 * 3 -


def Calculate(tokens):
    stack = []
    for token in tokens:
        if token == "+":
            stack.append(stack.pop() + stack.pop())
        elif token == "-":
            stack.append(-(stack.pop()- stack.pop()))
        elif token == "*":
            stack.append(stack.pop() * stack.pop())
        elif token == "%":
            rv = stack.pop()
            stack.append(stack.pop()/rv)
        else:
            stack.append(int(token))
    return stack.pop()
print(Calculate(["4","5","+","2","*","3","-"]))

2. 큐(Queue)의 특징

---

1. 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제
2. 가장 먼저 삽입된 데이터가 가장 먼제 삭제(FIFO : First In First-Out)구죠
3. 데이터가 저장될때 삽입 포인터(Rear)가 가리키고 출력된 데이터는 삭제 포인터(front)가 가리킨다.

• 데이터가 입력된다면 REAR+1, 데이터가 삭제될 때마다 front+1
• 삽입 데이터는 데이터가 입력될 때마다 1씩 증가하며 메모리 크기보다 큰 값을 갖게되면 데이터를 더 이상 기억할 수 없는 오버플로우(Overflow) 상태가 됨
• 스택활용

1.스풀이나 입출력 버퍼에 적합
2.은행에서 번호표 서비스
3.키보드 입력시 바로CPU저장 X -> 버퍼 대기후 전달
4. 동영상 실시간으로 받아보는 스트리밍 서비스에서 사용