스택(Stacks)

김서연·2024년 3월 29일
스택자료구조

자료구조 & 알고리즘

목록 보기
8/15

1 스택이란

  • 자료(data element)를 보관할 수 있는 (선형) 구조
  • 단, 넣을 때는 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있다
    • push, pop
  • 후입선물(LIFO - Last-in First-Out)

2 스택의 동작

  1. 초기 상태: 비어 있는 스택(empty stack)
    • S = Stack()
  2. 데이터 원소 A를 스택에 추가
    • S.push(A)
  3. 데이터 원소 B를 스택에 추가
    • S.push(B)
  4. 데이터 원소 꺼내기
    • r1 = S.pop()
  5. 데이터 원소 또 꺼내기
    • r2 = S.pop()

3 스택에서 발생하는 오류

  • 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 → 스택 언더플로우(stack underflow)
  • 꽉 찬 스택에 데이터 원소를 넣으려 할 때 → 스택 오버플로우(stack overflow)

4 스택 자료구조 구현

  1. 배열(array)을 이용하여 구현
    1. python 리스트와 메소드들을 이용
  2. 연결 리스트(linked list)를 이용하여 구현
    1. 지난 강의에서 마련한 양방향 연결리스트 이용
  3. 파이썬 라이브러리로 구현
    1. from pythonds.basic.stack import Stack

5 연산 정의

  • size(): 현재 스택에 들어 있는 데이터 원소의 수를 구한다
  • isEmpty(): 현재 스택이 비어있는지를 판단
  • push(x): 데이터 원소 x를 스택에 추가
  • pop(): 스택의 맨 위에 저장된 데이터 원소를 제거 (또한, 반환)
  • peek(): 스택의 맨 위에 저장된 데이터 원소를 반환 (제거하지 않음)

6 배열로 구현한 스택

class ArrayStack:

	def __init__(self):
		self.data = []

	def size(self):
		return len(self.data)

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		self.data.append(item)

	def pop(self):
		return self.data.pop()

	def peek(self):
		return self.data[-1]

7 연결 리스트로 구현한 스택

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data

8 스택의 응용(1) - 수식의 괄호 유효성 검사

  • 올바른 수식
    • (A + B)
    • {(A + B) * C)}
    • [(A + B) * (C + D)]
  • 올바르지 않은 수식
    • (A + B
    • A + B)
    • {A (B C})
    • [(A + B) * (C + D)}

9 스택의 응용(2) - 수식의 후위 표기법

  • 중위 표기법(infix notation): 연산자가 피연산자들의 사이에 위치
    • (A + B) * (C + D)
    • 괄호 > *, / > + - 의 우선순위를 갖는다
  • 후위 표기법(postfix notation): 연산자가 피연산자들의 뒤에 위치
    • A B + C D + *
    • 앞에 나오는 연산자부터 차례대로 계산
    • 괄호를 사용할 필요가 없다

9.1 변환 예시

  • A B + C → A B C +
  • A + B C → A B C +
  • A + B + C → A B + C +
  • (A + B) C → A B + C
  • A (B + C) → A B C +
  • (A + (B - C)) D → A B C - + D
  • A (B - (C + D)) → A B C D + -

9.2 알고리즘의 설계

  1. 연산자의 우선순위 설계
  2. 중위 표현식을 왼쪽부터 한 글자씩 읽어서
    1. 피연산자면 그냥 출력
    2. 여는 괄호면 스택에 push
    3. 닫는 괄호면 매칭되는 여는 괄호가 나올 때까지 pop, 출력
    4. 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력
  3. 스택에 남아 있는 연산자는 모두 pop, 출력
  • 힌트(*)
    • 스택의 peek()
    • while not op.Stack.isEmpty()
      • 남아 있는 연산자 모두 pop하는 순환문

왜인지 특정 케이스를 통과 못하는 중…

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    opStack = ArrayStack()
    answer = ''

    for c in S:
        # 여는 괄호일 때 -> push
        if c == '(':
            opStack.push(c)

        # 닫는 괄호일 때 -> (가 top에 올 때까지 pop
        elif c == ')':
            while opStack.peek() != '(':
                answer += opStack.pop()
            # '(' pop
            opStack.pop()

        # 피연산자일 때 -> 출력
        elif c not in prec.keys():
            answer += c

        # 연산자일 때, 우선순위가 top이 높을 경우 pop, c push
        elif not (opStack.isEmpty()) and prec[opStack.peek()] >= prec[c]:
            answer += opStack.pop()
            opStack.push(c)

        # 그 외 -> push()
        else:
            opStack.push(c)
    
    # 남은 연산자 pop
    while not opStack.isEmpty():
        answer += opStack.pop()

    return answer

10 스택의 응용(3) - 후위 표기 수식 계산

  • A B + C D + → (A + B) (C + D)

10.1 알고리즘의 설계

  • 후위 표현식을 왼쪽부터 한 글자씩 읽어서
    • 피연산자이면 스택에 push
    • 연산자를 만나면 스택에서 pop → (1), 또 pop → (2) (2) 연산 (1) 을 계산 후 결과를 스택에 push
  • 수식의 끝에 도달하면 스택에서 pop → 계산 결과 출력
class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-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

def infixToPostfix(tokenList):
    prec = {
        '*': 3,
        '/': 3,
        '+': 2,
        '-': 2,
        '(': 1,
    }

    opStack = ArrayStack()
    postfixList = []

    for c in tokenList:
        # 여는 괄호일 때 -> push
        if c == '(':
            opStack.push(c)

        # 닫는 괄호일 때 -> (가 top에 올 때까지 pop
        elif c == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            # '(' pop
            opStack.pop()

        # 피연산자일 때 -> 출력
        elif c not in prec.keys():
            postfixList.append(c)

        # 연산자일 때, 우선순위가 top이 높을 경우 pop, c push
        elif not (opStack.isEmpty()) and prec[opStack.peek()] >= prec[c]:
            postfixList.append(opStack.pop())
            opStack.push(c)

        # 그 외 -> push()
        else:
            opStack.push(c)
    
    # 남은 연산자 pop
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return postfixList

# 후위 표현식 계산
def postfixEval(tokenList):
    stack = ArrayStack()
    
    for c in tokenList:
        # 피연산자(int)면 push
        if type(c) == int:
            stack.push(c)
        else:
            a, b = stack.pop(), stack.pop()
            
            if c == '+':
                stack.push(b+a)
            elif c == '-':
                stack.push(b-a)
            elif c == '*':
                stack.push(b*a)
            else:
                stack.push(b/a)
            
    return stack.pop()
        

def solution(expr):
    tokens = splitTokens(expr)
    postfix = infixToPostfix(tokens)
    val = postfixEval(postfix)
    return val
profile
김서연
가보자고! 🔥
이전 포스트

양방향 연결 리스트(Doubly Linked Lists)

다음 포스트

큐(Queues)

0개의 댓글