순차적 자료구조 & 스택 (stack)

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록

https://www.youtube.com/watch?v=OzFXiukhv8o&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=8

 

순차적 자료구조 (Sequential data structures)

1. 배열, 리스트
- index로 임의의 원소에 접근
- 연산자 [ ]
- 삽입 (append, insert)
- 삭제 (pop, remove)

2. stack, queue, dequeue
- 제한된 접근(삽입, 삭제)만 허용
- 실제로 이런 자료구조가 많이 쓰임.

• stack : LIFO (Last In First Out) 밑에서부터 차곡차곡. push. 중간 삽입 불가.
• queue : FIFO (FIrst In First Out) 선착순. 차곡차곡 쌓이는 것은 똑같음. but 나갈 때는 밑에서부터 빠져나감.
• dequeue : stack + queue 스택과 큐의 모든 삽입과 삭제 구조를 다 제공함.

3. Linked List 연결 리스트
연속되지 않은 메모리 공간에 독립적으로 저장.
나의 다음 값의 주소를 저장. 마지막 값에는 null, none이 저장.

스택 Stack

삽입: push / 삭제: pop (값을 지운 후에 출력)
리스트를 스택 대용으로 쓰지 않는 이유?
스택에서는 푸쉬와 팝 두 가지만으로 연산이 가능하기 때문. 리스트와 혼동하여 스택의 값이 바뀌는 상황이 발생하지 않도록 하기 위함.
top: 스택 맨 위에 있는 값을 알려줌
len: length

S = Stack()

# Stack 구현

class Stack:
    def __init__(self):
        self.items = []   # 데이터 저장을 위한 리스트 준비

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()   # pop할 아이템이 없으면
        except IndexError:			  # IndexError 발생
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):				# len()로 호출하면 stack의 item 수 반환
        return len(self.items)

수행시간
push 함수: O(1)
pop 함수: O(1)
top 함수: O(1)
length 함수: O(1)

예제) 괄호 맞추기

(2 + 5) * 7 - ((3 - 1) / 2 + 7)
(()()) -> o
(()))( -> x 쌍은 세 쌍이지만 짝이 맞지 않음.

입력: 왼쪽, 오른쪽 괄호의 문자열
출력: 괄호쌍이 맞춰져있으면 True, 아니면 False

❓어떻게 풀까?
오른쪽으로 가면서 괄호 맞춰나가기.
자기의 짝이 나타날 때까지 스택에서 기다리기.
stack에 푸쉬된 채로 대기하다가 자기 짝이 나오면 팝
stack에는 아무것도 남지 않아야 함.

(()())
()) : pop을 실행했는데 스택에 아무것도 없는 경우 TypeError
()( : 다 끝냈는데 스택에 괄호가 남아있는 경우

for p in parseq:
    if p == '(':
        S.push(p)
    elif p == ')':
        S.pop()
    else:
        print("Not allowed Symbol")

if len(S) > 0:
    print("False")
else:
    print("True")

 

예제) 계산기 코드 작성

06.16 마저 영상 시청하고 추가하기
++ 06.16 update

입력: "2 + 3 * 5"
'2' '+' '3' '*' '5' 쪼개주어야 한다.
2 = 피연산자(operand)
+, * = 연산자(operator)

연산자별로 우선순위가 다름.

피연산자와 연산자는 토큰(token)

연산자의 구분

1. 이항연산자(binary operator): 2 + 3, 3 * 5
2. 연합연산자(unary operator): +3 - 6

2 + 3 * 5 와 같은 수식을 infix 수식이라 한다. (연산자가 피연산자 사이에 끼어 있는 구조)
infix 수식을 postfix 수식으로 변경: 2 3 5 * +

Q. postfix로 어떻게 바꾸나?

1. 우선순위에 따라 괄호 치기 ex) (2 + (3 * 5))
2. 연산자의 오른쪽괄호(')') 다음으로 연산자 이동 ex) (2 (3 5)*)+
3. 괄호 지우기 ex) 2 3 5 * +

(prefix도 존재)

3 * (2 + 5) * 4
위 식처럼 중간에 괄호가 있으면?
일단 infix를 postfix로 변경
기존에 있는 괄호는 그대로 두고 과정 진행: 3 2 5 + * 4 *

Q. 여기서 stack을 어떻게 이용하는가?
피연산자의 순서는 그대로
식에서 연산자가 나오는 순서대로 스택에 들어감
스택에 들어가기 전, 스택에 들어있는 연산자가 나보다 더 우선순위가 높은지 확인
우선순위가 높다면 팝을 수행하고 아니라면 나도 스택에 들어감
남은 연산자가 없으면 스택에서 순서대로 팝하여 리턴하면 postfix가 완성

괄호가 있는 식
(A + B) * C
** / 이후는 postfix의 상태를 표현한 것이다. 괄호는 postfix에 작성하지 않는다. 어차피 다 사라지니까
괄호도 일종의 연산자이기 때문에 스택에 들어감.
오른쪽 괄호(')')가 우선순위가 가장 높다. 왼쪽 괄호('(')는 괄호 안에 있는 연산자보다 우선순위가 낮음.
왼쪽 괄호가 스택에 먼저 들어감. / empty
더하기도 스택에 들어감 (왼쪽 괄호는 우선순위가 낮으니까 팝할 필요가 없으므로) / A
더하기는 오른쪽 괄호가 나올 때까지 스택에서 기다려야 한다. / A B
오른쪽 괄호 등장 / A B
오른쪽 괄호가 나왔다는 것은 자신의 짝인 왼쪽 괄호가 스택에 있다는 것을 의미함. / A B
그 사이에 있는 더하기는 연산 시 가장 먼저 수행되어야 한다. / A B
그러니 자신의 왼쪽 괄호가 나타날 때까지 팝 / A B +
곱하기 등장 / A B +
스택에는 아무것도 없는 상태, 비교 상대가 없으니 스택에 들어감 / A B + C
더 이상 남은 연산자가 없으므로 팝 / A B + C *

### pseudo code ###
# 리스트: outstack 출력 내용(postfix)이 들어감
# 스택: opstack (연산자가 오고 나가는 스택)

for each token in expr:
	if token == operand:
		outstack.append(token)
	if token == '(':
		opstack.push(token)
	if token == ')':
		opstack에 저장된 연산자를 계속 팝
		'('를 pop할 때까지 
		---> outstack에 append
	if token in '+*-/':
		opstack에 token보다 우선순위가 높은 연산자 모두 pop
		자신이 opstack에 push

opstack에 남은 연산자 모두 pop --> outstack에 집어넣음

postfix를 가지고 식 계산
피연산자 스택 마련
피연산자는 무조건 스택에 푸쉬
연산자라면 스택에 있는 탑 두 개 불러옴
a = S.pop() , b = S.pop()
연산을 수행한 후 결과값을 스택에 푸쉬, S.push(a token b)
끝나면 스택에 마지막으로 남은 최종값을 팝하여 리턴

infix 식을 postfix로 바꾸는 코드과 postfix,식 계산기 코드는 다른 글에 따로 써야겠다. 글이 너무 길어질 것 같음.