[자료구조 - Python] 스택(STACK)

자료구조에서 가장 중요하고 기초라고 할 수 있는 후입선출(LIFO) 구조의 스택에 대해 알아보자. 기본적으로 자료구조에서 기본적으로 자료를 담을 수 있는 방식에는 배열(Array)과 스택(Stack), 큐(Queue)가 있다. 각각의 기본적인 공통점은 자료를 넣어두고 사용하는 것이다. 여기서 우리가 생각할 수 있는 점은 효율적으로 자료를 관리하기 위해, 자료를 담는 방식에 대한 차이를 이해하는 것이 중요하다. 컴퓨터 과학에서 중요한 자료구조 중 하나인 스택(Stack)에 대해 알아보도록 하자.

 

---

 

스택(Stack)이란

 

스택은 데이터를 임시 저장할 떄 사용하는 자료구조이다. 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있다. 이러한 자료구조를 직관적으로 풀어보면, 프링글스 과자와 같다고 할 수 있다. 프링글스 과자를 만들 때, 처음 통에 넣은 과자는 가장 마지막에 먹을 수 있다. 반대로 가장 마지막에 넣은 프링글스 과자는 뚜껑을 열면 가장 상단에 있기 때문에 바로 먹는 것이 가능하다. 이렇게 순차적으로 쌓이기 때문에 나중에 넣은 것을 먼저 꺼낼 수 있는 자료구조가 바로 스택(Stack)이라고 할 수 있다.

 

스택은 다양한 컴퓨터 과학 분야에서 요융하게 사용된다. 다른 블로그에서 소개될 함수 호출이나 재귀 알고리즘에서 스택은 매우 중요한 역할을 한다. 또한, 웹 브라우저의 방문 기록의 뒤로 가기나, 텍스트 편집기에서 실행 취소의 기능도 모두 스택 자료구조를 통해서 만들어진다.

 

스택의 구현 방식을 조금 더 쉽게 그림으로 알아보자. 아래의 그림등 A 데이터와 B 데이터를 순차적으로 PUSH 하여 담아주는 그림이다.

 

made in hanpy

 

위의 그림에서는 데이터 A와 B를 순차적으로 쌓아 올린것을 확인할 수 있다. 이렇게 쌓아 올린 데이터는 A, B가 쌓여 있는 것을 확인할 수 있다. 이 상태에서 하나의 데이터를 빼면, 아래와 같이 B가 빠지는 것을 확인할 수 있다. 여기서 C 데이터를 넣으면 A위에 C가 쌓이는 것을 확인가능하다. 즉, 데이터가 후입선출(LIFO) 방식으로 나중에 들어간 데이터가 먼저 나온다고 이해를 하면 된다.

 

made in hanpy

 

 

우리가 위 그림에서 중점적으로 봐야하는 부분은, 같은 부분으로 데이터가 들어오고 나간다는 점이다. 따라서 중간 부분을 핸들링할 수 없고 한 부분만 핸들링이 가능하기 때문에 코딩 부분도 간단하다. 이러한 의미는 다른 자료구조는 그렇지 않다는 점을 의미한다. 우선은 간단히 만들기가 가능한 stack에 대한 코드 구현을 해보도록 하자.

 

스택(stack) 구현하기

스택은 배열(Array)나 연결 리스트(Linked List)로 구현이 가능하다. 배열을 사용한 구현 방식은 효율적이지만, 크기가 고정되어 있어 데이터의 추가 삭제 시에 메모리 크기 변경이 필요하다. 하지만 연결 리스트로 구현을 한다면 메모리 제약이 없고 동적으로 크기가 조정할 수 있다. 이것은 일반적인 배열/연결 리스트의 장단점이고 파이썬에서는 배열로 간단하게 구현해서 사용가능하다.

 

스택 자료구조에서 일반적으로 포함되는 기본 연산은 다음과 같다.

 

1. 푸시(Push): 스택의 맨 위에 데이터를 추가한다.
2. 팝(Pop): 스택의 맨 위에 위치한 데이터를 제거하고 반환한다.
3. 피크(Peek): 스택의 맨 위에 위치한 데이터를 반환한다. 이때, 데이터의 변화는 없다.
4. 비어 있는지 확인(IsEmpty): 스택이 비어 있는지 여부를 확인한다. 이때, 데이터의 변화는 없다.
5. 스택의 크기 확인(Size): 스택에 저장된 데이터의 개수를 반환한다. 이때, 데이터의 변화는 없다.

 

아래는 간단히 관련 Stack을 만들어 보자.

 

스택(Stack) 클래스

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

 

Stack이라는 클래스를 만들었다. 객체생성을 위해서는 아래와 같이 간단하게 클래스를 호출하여 가능하다. __init__ 를 통해 우리는 처음 인스턴스 생성 시 self.items로 배열을 넣는 것이 가능하다.

 

s = Stack()

 

객체 생성 시 items라는 배열이 생성된다. 이 배열이 Stack을 담고 있는 자료구조라고 할 수있고, 이 배열을 가지고 Stack의 만든다고 이해하면 된다.

 

스택(Stact) Push

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

 

간단히 class 내부에 items에 데이터를 넣어줄 수 있는 append를 넣어준다.

 

 

스택(Stact) Pop

    def pop(self):
        if len(self.items) != 0:
            return self.items.pop()
        else:
            print("Stack is empty")

 

여기서 중요한 것은 pop()를 사용한다는 것이다. pop() 함수는 lsit에 포함된 함수로 리스트 내부의 데이터 중에 가장 마지막에 있는 데이터를 꺼내어 return 해준다. 따라서 Stack의 자료구조라 할 수 있다. 만약 items의 리스트가 빈 배열이라면 에러가 발생할 수 있기 때문에 리스트가 비어있는지 체크를 해주면 된다. 위의 로직에서는 print로 값이 비어 있는 경우 알려주는 방식으로 작성을 했지만, 다른 로직을 추가해 줘도 가능하다.

 

 

스택(Stact) Peak

    def peek(self):
        if len(self.items) != 0:
            return self.items[len(self.items) - 1]
        else:
            print("Stack is empty")

 

가장 위의 데이터를 반환해주는 Peak를 만들어 보자. 리스트의 마지막 값을 리턴해주는 로직으로 간단히 작성이 가능하다. 이 경우도 값이 없는 경우 에러가 날 수 있으니 체크를 해주면 된다.

 

 

스택(Stact) isEmpty

    def isEmpty(self):
        if self.items == []:
            return True
        else:
            return False

 

스택이 비었는지 확인해 주는 로직으로는 간단히 위와 같은 로직으로 만들면 된다. 값이 비어있다면 True를 리턴해주고, 값이 비어있지 않다면 False를 리턴해 주면 된다.

 

 

스택(Stact) Size

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

 

간단히 리스트의 개수를 리턴해주면 된다.

 

 

 

스택(Stact) 만들기

위의 각각의 기능별로 만든 코드를 모아서 결합시키면 아래와 같다.    

 

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

    def isEmpty(self):
        if self.items == []:
            return True
        else:
            return False

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

    def pop(self):
        if len(self.items) != 0:
            return self.items.pop()
        else:
            print("Stack is empty")

    def peek(self):
        if len(self.items) != 0:
            return self.items[len(self.items) - 1]
        else:
            print("Stack is empty")
 
     def size(self):
        return len(self.items)

    def display(self):
        return (self.items)



# __main__
s = Stack()
c = 0
while c != 5:
    print('\tSTACK OPERATIONS')
    print('1.Push')
    print('2.Pop')
    print('3.Peek')
    print('4.Display Stack')
    print('5.Exit')
    c = int(input('Enter your choice(1-5): '))
    if c == 1:
        x = input("Enter the item: ")
        s.push(x)
    elif c == 2:
        s.pop()
    elif c == 3:
        s.peek()
    elif c == 4:
        print(s.display())
    elif c != 5:
        print('Wrong Choice! Choose from 1 to 5 only')

print('Bye')

 

__main__ 아래 부분은 간단히 while 문을 활용해서 stack를 사용하는 예시를 만들어 보았다. 참고만 하면 좋을 것 같다.

 

 

스택(Stact) 만들기 (deque 활용)

 

collections.deque 라이브러리르 이용하면, 간단히 stack을 구현할 수 있다. 사실 Stack과 Queue를 만들 때는 메모리/속도 효율성을 증대시키기 위해서 일반 배열(list)이 아니라 collections.deque를 활용하서 만든다. 그 이유는 deque는 이중 열결리스트로 만들어져 있기 때문에 여러 측면에서 일반 배열보다는 빠르다.

 

from collections imort deque

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

    def isEmpty(self):
        if len(self.items) == 0:
            return True
        else:
            return False

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

    def pop(self):
        if len(self.items) != 0:
            return self.items.pop()
        else:
            print("Stack is empty")

    def peek(self):
        if len(self.items) != 0:
            return self.items[len(self.items) - 1]
        else:
            print("Stack is empty")

    def display(self):
        return (self.items)

 

위의 코드들을 하나씩 뜯어보면, 사실 기초적인 파이썬 지삭만 있으면 충분히 이해가 될 수 있는 내용으로 구성되어 있다. 위의 내용을 참고하여 자신만의 Stack을 만들어 보도록 하자.