[TIL]Day 3

1. Stack

라이브러리 이용

from pythonds.basic.stack import Stack
S = Stack()

값을 꺼내지 않고 값을 알고 싶을 때

S.peek()

스택을 활용한 후위 표기식의 계산
1. 피연산자를 만나면 스택에 넣고
2. 연산자를 만나면 2개를 뽑아서 나중에 뽑은애 연산자 처음 뽑은애 계산 후 다시 스택에 넣는다.

후위 표기식 변환을 위한 과정1 - 리스트에 넣기

def splitTokens(exprStr):
	tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
    	if c == ' ':
        	continue
        if c in '0123456789':
        	val = val * 10 + int(c)
            valProcessing = True
        else:
        	if valProcessing:
            	tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
    	tokens.append(val)
	return tokens

2. Queues

큐에서의 peek는 맨 앞에 원소를 보여줌

배열로 구현한 큐에서 dequeue의 시간복잡도는 O(n)
이유는 하나제거하고 뒤에 있는 애들을 앞으로 한칸씩 옮기기 때문
따라서 이중연결리스트로 구현하여 이 문제를 해결가능

라이브러리

from pythonds.basic.queue import Queue
Q = Queue()
dir(Q) #정의된 멤버 확인

큐의 활용

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
자료를 생성하는 작업이 여러곳에서 일어나는 경우
자료를 이용하는 작업이 여러곳에서 일어나는 경우
양쪽 모두 여러곳에서 일어나는 경우
자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

3. Trees

이진트리의 정의

모든 노드의 차수가 2이하인 트리
빈 노드도 2진트리이며 재귀적으로 정의 가능