Stack (스택)

Stack 이란?

스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조 입니다.
이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)라고 합니다.
이때 스택에 삽입하는 연산을 푸시(push), 꺼내는 연산을 팝(pop)이라고 합니다.

Stack의 동작 원리

1. 초기에 빈 스택이 있습니다

2. 여기에 데이터 1을 push하면 현재 스택은 [1]이 됩니다.

3. 데이터 2를 push하면 현재 스택은 [1, 2]가 됩니다.

4. 데이터 3을 push하면 현재 스택은 [1, 2, 3]이 됩니다.

5. 마지막으로 pop을 하면 마지막에 push한 데이터 3이 빠져나가고 스택은 [1, 2]가 됩니다!

Stack의 ADT

스택에는 push, pop, isFull(가득 찼는지), isEmpty(비었는지)과 같은 연산을 정의해야 합니다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top도 있어야 합니다.

• boolean isFull() : 스택에 들어 있는 개수가 maxsize인지 확인해 boolean값을 반환

• boolean isEmpty() : 스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환

• void push(ItemType item) : 스택에 데이터를 push

• ItemType pop() : 스택에 최근에 push한 데이터를 pop하고, 그 데이터를 반환

• int top : 스택에 최근에 push한 데이터의 위치를 기록

• ItemType data[maxsize] : 스택의 데이터를 관리하는 배열 / 최대 maxsize개의 데이터를 관리

Stack 구현

위에 정의한 스택을 구현하면 다음과 같습니다. (Python)

stack = [ ] # 스택 리스트 초기화
max_size = 10 # 스택의 최대 크기

def isFull(stack):
    # 스택이 가득 찼는지 확인하는 함수
    return len(stack) == max_size

def isEmpty(stack):
    # 스택이 비어 있는지 확인하는 함수
    return len(stack) == 0

def push(stack, item):
    # 스택에 데이터를 추가하는 함수
    if isFull(stack):
        print("스택이 가득 찼습니다.")
    else:
        stack.append(item)
        print("데이터가 추가되었습니다.")

def pop(stack):
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack):
        print("스택이 비어 있습니다.")
        return None
    else:
        return stack.pop( )

예시문제

import sys

n = int(sys.stdin.readline())

for i in range(n):
    words = sys.stdin.readline().rstrip().split()
    reversed_words = []

    while len(words) > 0:
        reversed_words.append(words.pop())

    print(f"Case #{i+1}: {' '.join(reversed_words)}")

풀이과정

테스트케이스에서 this is a test가 Case #1: test a is this 로 출력되는 과정입니다.
1. 우선 'this is a test' 이 문장을 ["this", "is", "a", "test"] 리스트로 만들어야합니다!
words = sys.stdin.readline().rstrip().split() 이렇게 들어온 문장을 배열로 만들 수 있습니다.
2. 이 리스트에서 pop()을 빈 스택에 다시 넣는 것을 반복하여 ["test", "a", "is", "this"]이라는 새 리스트를 만듭니다.
reversed_words = [] while len(words) > 0: reversed_words.append(words.pop())
이렇게 words에서 하나씩 빼서 reversed_words에 넣는 과정으로 문장을 뒤집습니다.
3. 문장출력
print(f"Case #{i+1}: {' '.join(reversed_words)}")

마무리

최근 알고리즘 문제들을 퇴근 후 매일 풀고 있는데, 먼저 자료구조를 정리해야겠다는 생각이 들어서 오늘 글을 작성하게 되었다.. 자료구조를 정리하고, 그 후에 여러 알고리즘을 정리해봐야겠다는 생각이 들었다..!!

참고

코딩 테스트 합격자 되기 - 파이썬 편 책을 참고 하였습니다!
감사합니다