스택

스택

스택의 특징

출처

스택인 후입선출 (Last-In, First-Out, LIFO) 구조의 자료형이다. 쉽게 설명하자면, 버0킹 브랜드의 스태커버거를 생각하면 된다. 패티가 4장 쌓여있고 뺴려면 위에것부터 뺄 수 있는것처럼, 컴퓨터의 스택 역시 이러한 구조이다.

스택의 삽입 삭제는 상단으로만 할 수 있고, 중간의 작업들은 건드릴 수가 없다.

스택은 주로 인터넷에서 이전패이지로 돌아가능 기능, 혹은 문서작업에서 ctrl+z로 되돌리는 기능, 혹은 컴퓨터 내부에서 함수를 처리할 떄 순서를 저장하는 기능등에 사용된다.

이 밖에도 IDE에서의 괄호 유효성 검사, 혹은 DFS 미로찾기 등에도 사용된다.

스택함수의 구현

• 앞으로 모든 구현은 class를 통해서 한다

class Stack:
    def __init__(self):
        self.top = []

    def isEmpty(self):
        return len(self.top) == 0

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

    def clear(self):
        self.top = []

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

    def pop(self):
        if not self.isEmpty():
            return self.top.pop(-1)

    def peek(self):
        if not self.isEmpty():
            return self.top[-1]

    def display(self):
        res = []
        while not self.isEmpty():
            res.append(self.pop())
        print(res)

스택의 경우 비어있는 상태에서 삭제, 혹은 peek 연산을 수행하려하면 error 가 출력되게 된다. 따라서 이러한 문제를 방지하고자, 해당 연산을 할 떄는 self.isEmpty() 검사를 통해서 비어있는지 아닌지를 확인하고 연산을 수행하게 만들어준다. 이 밖에는 코드를 보면 이해할 수 있는 문제이다.

스택의 활용 : 실전편

괄호 검사 알고리즘

IDE에서 개발을 하다보면 가끔 괄호를 닫는것을 빼먹어서 오류가 출력되는 경우가 있는데, 최신 IDE에서는 이러한 오류들도 다 표시를 해준다.
이러한 괄호의 적합성 검사는 바로 Stack을 이용해서 수행한다.

def checkBracket(st):
    stack = []
    for ch in st:
        if ch in ('(', '[', '{'):
            stack.append(ch)
        elif ch in (')', ']', '}'):
            if len(stack) == 0:
                return False
            else:
                left = stack.pop()
                if (ch == ')' and left != '(') or (ch == ']' and left != '[') or (ch == '}' and left != '{'):
                    return False
    return len(stack) == 0

str = '()()([])'
print(checkBracket(str))

다음과 같은 코드를 이용해서 구현하게 된다.

원리는 다음과 같다.
1. 문자열을 받고 그 문자열을 하나식 검사하면서 stack에 저장한다

1-1 만약 문자열이 "( { [" 같이 시작하는 괄호인 경우 저장을 한다. 하지만 만약 반대되는 괄호 ") } ]"라면 2차 검사를 시작한다.

1-2 스택이 비어있는 상태에서 ") } ]" 가 들어왔다면, 성립할 수 가 없다. 따라서 False. 만약 비어있지 않다면, 바로 직전의 항목을 꺼내고, 그 항목과 짝이 맞지 않다면, 삭제를 한다.

이러한 과정을 통해 검사를 수행한다.

문제가 없는 괄호라면 True, 문제가 있다면 False가 출력되게 된다.
비슷한 원리로 ' " " ' 역시 검사할 수 있다. 미리 조건에 넣어주기만 하면 된다.

하지만 위의 코드에서는 이상한 점이 하나 있다. 바로 위에서 만든 스택 클래스를 사용한것이 아니라 리스트를 사용했다는 점이다.
물론, 파이썬에서는 리스트를 스택과 거의 유사하게 사용 할 수 있다.
마찬가지로 이 리스트를 이용해, 큐나 디큐 역시 유사하게 구현 할 수 있지만 앞으로는 가능하면 클래스를 통한 구현
그리고 collections에 있는 stack을 불러오는 것으로 구현하도록 해야한다. 그것이 정확한 구현이니깐...

Infix to PostFix

중위계산식과 후위계산식에 대해서는 인터넷을 찾아보면 알 수 있다.

def precendence(op):
    if op == '(' or op == ')':
        return 0
    elif op == '+' or op == '-':
        return 1
    elif op == '*' or op == '/':
        return 2

def toPostfix(expr):
    s = Stack()
    res = []
    for term in expr:
        if term in '(':
            s.push('(')
        elif term in ')':
            while not s.isEmpty():
                op = s.pop()
                if op == '(':
                    break
                else:
                    res.append(op)
        elif term in "+-*/":
            while not s.isEmpty():
                op = s.peek()
                if (precendence(term)) <= precendence(op):
                    res.append(op)
                    s.pop()
                else:
                    break
            s.push(term)
        else:
            res.append(term)

    while not s.isEmpty():
        res.append(s.pop())
    return res

# expr = "(A/B)*C"
# expr = "A+(B*C)-D/E"
# expr = "(X+Y)-(W*Z)/V"
# expr ="U*V*W+X-Y"
# expr = "A/B*C-D+E"
expr = "A*(B+C)/D-E"

print(toPostfix(expr))

계산식 변환에서는 ()나 우선 * / 가 + - 보다 우선되는등 고려할 내용이 많다.

우선 precendence를 이용하여 계산순위를 지정해준다.
그 후 다음과 같은 프로세스를 통해 계산을 수행한다.

1. 괄호가 있는 경우 괄호를 스택에 집어넣는다

• 이는 괄호가 최우선 계산순위이기 떄문이다)

2. 연산자인 경우 op 값을 스택의 최상위값으로 두고 두 값의 precendence를 판단하여 스택에 저장한다.

3. 그냥 숫자의 경우 계속 스택에 집어넣는다

다음과 같은 결과를 거치면 print하게 되면 결과물이 출력된다.

단순연결리스트 스택

특징

기존의 스택과 다르게 이번 스택은 linked list를 이용한 스택이다. 이를 linked stack이라고 부른다.

이 스택의 특징은 헤드 포인터를 스택의 top으로 이용한다는 점이다. 자료의 입출력이 모두 top에서 이루어지기에 별다른 조치도 필요없다.

구현 코드

class Node:
    def __init__(self, elem, link=None):
        self.data = elem
        self.link = link


class LinkedStack:
    def __init__(self):
        self.top = None

    def isEmpty(self):
        return self.top is None

    def clear(self):
        self.top = None

    def push(self, item):
        n = Node(item, self.top)  # make a node by using class node
        self.top = n

    def pop(self):
        if not self.isEmpty():
            n = self.top
            self.top = n.link
            return n.data

    def peek(self):
        if not self.isEmpty():
            return self.top.data

    def size(self):
        node = self.top
        count = 0
        while node is not None:
            node = node.link
            count += 1
        return count

    def display(self, msg='LinkedStack:'):
        print(msg, end='')
        node = self.top
        while node is not None:
            print(node.data, end=' ')
            node = node.link
        print()

• 노드클래스에 대해서는 연결리스트에 가면 자세한 설명이 있다.

주로 신경써야할 부분인 push와 pop 부분에 대해 보도록 하겠다.
우선 push, 즉 삽입연산이다.

우선 node 클라스를 통해서 새로운 노드를 만든다. 그 후, self.top 즉 top을 그 새로운 노드로 채운다. 여기서 새로운 노드를 만들 떄, 링크에 self.top 을 넣어서 기존의 탑을 다음 링크로 넣어준다는것을 알 수 있다.

다음은 삭제연산 pop이다. 우선 n을 self.top으로 설정한다. 그 후, self.top에는 n.link 즉, n 바로 다음 스택의 링크를 걸어준다. 이리하면 top에는 2번째가 들어가게 된다. 그 후, n.data를 반환하면 우리는 맨 위의 값을 지우면서 반환받게 된다.

사이즈를 측정하는 count의 경우, node 값이 None가 될 때 까지 지속적으로 주소를 바꿔가면서 count++를 수행한다.

마치며

이번 글에서는 스택의 원리와 구현 그리고 사용 사례에 대해 알아보았다. 스택은 실제로도 많이 사용되는 자료구조의 한 형태이기에, 자세히 알아두면 좋을것이라 생각한다.