[데이터구조] 스택, 큐, 해싱

리스트와 링크드 리스트의 장점과 단점

스택, 큐

대표적인 자료구조 4가지

• 스택 : 마지막에 들어온 녀석이 먼저 나감
• 큐 : 먼저 들어온 녀석이 먼저 나감

스택과 큐는 두가지 원리를 가지고 그 이상도 그 이하도 아닙니다. 그렇다면 스택과 큐를 왜 사용할까요? 그 의미를 아는게 중요합니다. 스택이랑 큐는 언제 쓸까요?


스택은 상태(Status)를 저장하는 자료구조입니다. 예를들어, 아래의 그림과 같이 마켓에서 음식을 사러간다고 생각하겠습니다. 마켓에서 미역, 국간장, 후추를 사고 포인트를 적립하려고보니 집에 포인트 카드를 두고온 것을 기억했습니다. 그래서 집에 돌아가서 카드를 가져오려고하니 이번에는 세탁소에 맡긴 옷에 열쇠를 넣어둔게 기억이 났습니다.


이제 세탁소에 가서 열쇠를 찾고 집에가서 카드를 꺼내 마트에서 남은 고기와 냄비를 사고 집에서 미역국을 끓이는 상황을 생각해보겠습니다. 해당 과정의 전체 프로세스는 아래와 같습니다.

여기서 스택은 어떤 역할을 하나 생각해보면, 직전에 하려고한 행동을 기록해둠으로서 다음의 행동을 무엇을 해야할지를 알려줍니다. 아래와 같이 세탁소에서 열쇠를 찾았다고 생각해보겠습니다. 이제 직전에 행동할 행동은 집. (2) 서랍열기입니다. 그래서 열쇠를 찾고 서랍을 열고, 카드를 꺼내고 집에 나온 후에 마트. (4) 고기를 구매하러 가게 되는 것입니다.

위의 과정을 전체 이미지 순서로 살펴보면 아래와 같습니다.

그래서 스택은 언제 쓰이는것인가요? 바로, "상태"의 의존관계가 생길 때 스택을 사용합니다. A라는 일을 마치기 위해서 B라는 일을 먼저 끝내야 할 때처럼 명령간의 의존하는 순서가 있으면 스택을 사용합니다. 대표적으로 함수의 호출을 할때 스택을 사용합니다. 예를들어, 아래의 main이 끝나려면 step1부터 step10까지 순서대로 다 끝나야 되는 구조입니다. 마찬가지로 비슷하게 많이 사용하는 함수가 재귀호출입니다.

def main():
    step1()
    step2()
    .
    .
    .
    step10()

그렇다면 큐는 언제 사용할까요? 아래와 같이 비슷한 상황을 생각해보겠습니다. 비슷하지만 이번에는 고기를 사기위해 집과 세탁소에는 갈 필요가없는 상황입니다. 이런 경우처럼 "상태"의 의존상태가 없을 때 큐를 사용합니다. 기존의 스택에서는 고기 - 집간의 의존관계가 있어서 선행관계가 필요했습니다. 하지만 지금은 고기를 사는것과 월세 입금하기간의 관계가 없고 고기와 냄비구매를 모두 마치고 차례대로 일을 수행하면됩니다. 즉, 미역국 끓이기 - 옷찾기 - 월세입금 순서대로 일을 순서대로 진행하면 됩니다. 보통 병렬화같은 경우에 큐를 사용합니다.

스택 구현하기

[예제 1] 스택 구현하기

이번 예제에서는 정수를 저장하는 stack을 구현합니다.

stack 클래스 내부에 있는 함수를 완성시키고 아래의 예제를 테스트해보세요.

완벽하게 동작한다고 생각되시면 제출을 눌러 점수를 확인해보세요!

아래의 테스트 예제를 main 함수에 복사, 붙여넣기해서 제대로 동작하는지 확인해보세요!

[테스트1]

stack.push(1)
stack.push(2)
stack.pop()
stack.push(4)
stack.pop()

print(stack.size()) 
print(stack.top())
print(stack.empty())

[테스트1 결과값]

1
1
0

[테스트2]

stack.push(3)
stack.pop()
stack.pop()

print(stack.size()) 
print(stack.top())
print(stack.empty()) 

[테스트2 결과값]

0
-1
1

코드

class Stack:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        스택 myStack을 만듭니다.
        '''
        self.myData = []

    def push(self, n) :
        '''
        stack에 정수 n을 넣습니다.
        '''
        self.myData.append(n)
        pass

    def pop(self) :
        '''
        stack에서 가장 위에 있는 정수를 제거합니다. 만약 stack에 아무 원소가 없다면 아무 일도 하지 않습니다.
        '''
        if len(self.myData) == 0 :
            return
        else :
            self.myData.pop()

    def size(self) :
        '''
        stack에 들어 있는 정수의 개수를 return 합니다.
        '''
        return len(self.myData)

    def empty(self) :
        '''
        stack이 비어있다면 1, 아니면 0을 return 합니다.
        '''
        if len(self.myData) == 0 :
            return 1
        else :
            return 0

    def top(self) :
        '''
        stack의 가장 위에 있는 정수를 return 합니다. 만약 stack에 들어있는 값이 없을 경우에는 -1을 return 합니다.
        '''
        if len(self.myData) == 0 :
            return -1
        else :
            return self.myData[-1]


def main():
    stack = Stack()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''
    stack.push(1)
    stack.push(2)
    stack.push(4)

    print(stack.size()) 
    print(stack.top())


if __name__ == "__main__":
    main()

[예제 2] 올바른 괄호인지 판단하기

본 문제에서는 입력으로 주어지는 괄호가 올바른 괄호인지를 판단하는 checkParen(p)를 작성합니다.

예를 들어, ‘(())’ 은 올바른 괄호이지만, ‘(()))’, 혹은 ‘(()()(’ 는 올바른 괄호가 아닙니다.

괄호같은 경우 '('와 ')' 간의 의존관계가 존재해서 스택을 이용한 예시가 됩니다.

[입력값] 괄호 p가 주어집니다.

[결과값] p가 올바른 괄호이면 YES, 그렇지 않으면 NO를 출력합니다.

테스트 예제

[입력 예시 1]

(())()

[출력 예시 1]

YES

[입력 예시 2]

(((())())(()())((())()))

[출력 예시 2]

YES

[입력 예시 3]

(())())()

[출력 예시 3]

NO

[입력 예시 4]

((()())(()())))(())

[출력 예시 4]

NO

코드

def checkParen(p) :
    '''
    괄호 문자열 p의 쌍이 맞으면 "YES", 아니면  "NO"를 반환
    '''
    myStack = []
    for p_ in p: 
        if p_ == '(':
            myStack.append(0)
        else:
            try:
                myStack.pop(0)
            # )만 계속 들어온 경우 
            except:
                return "NO"
    if len(myStack) == 0: 
        return "YES"
    else:
        return "NO"

def main():
    '''
    Do not change this code
    '''

    x = input()
    print(checkParen(x))

if __name__ == "__main__":
    main()

출처

• Elice Academy | 데이터구조 - 스택, 큐, 해싱