[자료구조] Stack(스택)(Python)

* 개요

Stack(스택)은 후입선출(Last In First Out - LIFO) 특성을 가지는 자료구조이다. 즉, 데이터의 삽입과 삭제가 메모리의 한 쪽 끝에서만 나타난다고 할 수 있다. 메모리에 새로 들어오는 데이터(push)의 위치가 메모리의 말단에 위치하고, 이를 '탑 포인터'라고 일컫는다. 내보내는 데이터(pop) 역시 메모리의 말단을 거친다. 스택의 추상 자료형(Abstract Data Type - ADT)을 살펴보면, 입력 연산은 push, 출력 연산은 pop이다. 조회 연산은 peek라고 하는데, 탑 포인터가 가리키는 데이터를 조회만 할 뿐, 인덱스에 변화를 주지는 않는다. 스택은 흔히 크기를 고정해서 사용하기 때문에, 이를 다 사용하면 데이터가 넘치게 된다. 이에 대한 대처방안이 존재하지 않으면 다른 메모리 영역을 침범하게 되는데, 이를 스택 오버플로우(Stack Overflow)라고 한다.

 

* 추상자료형(Abstract Data Type - ADT)이란 ?

추상 자료형(Abstract Data Type - ADT)은 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산을 명기한 것이다. 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와 다르다고 할 수 있다.

 

* 스택 구현(배열 vs 연결 리스트)

Stack(스택)은 배열과 연결 리스트로 구현이 가능하다. 배열과 연결 리스트로 구현하였을 때, 각각의 특징이 존재한다.

 

- 배열로 구현하였을 경우 : 처음으로 스택을 위한 배열을 생성하고, index의 값을 0으로 잡는다(탑 포인터). index = 0이면, 스택이 비어있는 것이고, 스택에 push를 할 경우에는 index의 자리에 넣고, index를 1 증가시켜주면 된다. index가 초기 배열의 크기 이상이면 스택이 꽉 찬 것이다. 스택에서 pop을 할 경우에는 index에 있던 값을 반환하고, index를 1 감소시켜주면 된다.

 

- 연결 리스트로 구현하였을 경우 :  연결 리스트로 구현할 때는 배열로 구현하였을 때보다 훨씬 간단하다. 메모리 상에 데이터를 위한 공간을 할당하고, 새로운 데이터가 추가될 때마다 포인터로 연결하기만 하면 된다. 위의 그림에서 좌측 ADT(추상 자료형)는 스택의 연산을 지원하기 위해 1부터 5까지 각 요소가 접시 쌓이듯이 차곡차곡 놓이겠지만, 연결 리스트로 구현하게 된다면, 메모리 상에는 순서와 관계 없이 여기저기에 무작위로 배치되고(랜덤 액세스) 포인터로 가리키게 될 것이다.

 

이제 스택 코드를 보며 스택을 이해하도록 하자. 리스트, 연결 리스트로 모두 구현을 해보았다.

* 파이썬으로 구현한 스택(리스트)

스택을 리스트로 구현해보았다.

class Stack :
    def __init__(self) :
        self.stack = []
    
    # data를 스택 리스트에 추가
    def push(self, data) :
        self.stack.append(data)
    
    # 가장 나중에 들어온 데이터를 꺼낸다.(삭제)
    def pop(self) :
        pop_data = None
        if self.isEmpty() :
            print("스택이 비어있음.")
            
        else :
            pop_data = self.stack.pop()
            
        return pop_data
    
    # 스택 조회 연산
    def peek(self) :
        if self.isEmpty() :
            print("스택이 비어있음.")
        
        else :   
            return self.stack[-1]
    
    # 스택이 비어있는지 확인
    def isEmpty(self) :
        is_empty = False
        if len(self.stack) == 0 :
            is_empty = True
            
        return is_empty

# 실행 코드
stk = Stack() # 스택 객체 생성
stk.push(1) # [1]
stk.push(2) # [1, 2]
stk.push(3) # [1, 2, 3]
stk.peek() # 마지막 데이터인 3을 반환
stk.pop() # 3을 pop
stk.pop() # 2를 pop
stk.pop() # 1을 pop
stk.pop() # 스택이 비어있음.

초기화 부분은 스택을 선언한다. 보통은 스택의 크기를 정해두지만, 해당 코드에는 정해두지 않았다.

push 메서드는 data를 스택 리스트에 차곡차곡 추가하는 코드이다.

pop 메서드는 가장 나중에 들어온 데이터를 꺼내는 코드이다. 가장 나중에 들어온 데이터를 꺼내는 이유는 스택이 후입선출(Last In First Out - LIFO) 구조를 지니고 있기 때문이다.

peek 메서드는 스택을 조회하는 연산 코드이다. 조회만 할 뿐, 인덱스에 영향을 주지는 않으며, 탑 포인터가 가리키는 data가 반환될 것이다.

isEmpty 메서드는 스택이 비어있는지 확인하는 코드이다. 비어있다면 True를 반환하고, 비어있지 않다면 False를 반환할 것이다.

다음은 연결 리스트로 구현한 스택 코드이다.

 

* 파이썬으로 구현한 스택(연결 리스트)

스택을 연결 리스트로 구현해보았다. 

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

class LinkedListStack :
    def __init__(self) :
        self.head = None
    
    def push(self, data) :
        new_node = Node(data)
        new_node.next = self.head
        # 삽입한 데이터가 head가 되도록 한다.
        self.head = new_node
        
    def pop(self) :
        pop_data = None
        if self.isEmpty() :
            print("스택이 비어있음.")
            
        else :
            pop_data = self.head.data
            self.head = self.head.next
            
        return pop_data
            
    def peek(self) :
        if self.isEmpty() :
            print("스택이 비어있음.")
            
        else :
            return self.head.data
    
    def isEmpty(self) :
        is_empty = False
        if self.head is None :
            is_empty = True
        
        return is_empty
    
stk = LinkedListStack() # 연결리스트 스택 객체 생성
stk.push(1) # 1
stk.push(2) # 2 1
stk.push(3) # 3 2 1
stk.peek() # head 데이터인 3을 반환
stk.pop() # 3을 pop
stk.pop() # 2를 pop
stk.pop() # 1을 pop
stk.pop() # 스택이 비어있음.

먼저 노드 클래스를 구현한다. 그 후 연결 리스트 스택 클래스를 구현한다.

push 메서드는 Node(data)를 통해 새로운 노드를 생성하고,  새로운 노드의 next 포인터는 기존의 head 데이터를 가리키고, 새로운 노드는 head 데이터가 되도록 한다.  후입선출 구조라는 것을 잘 기억하자.

peek 메서드는 head 노드의 데이터를 반환하도록 한다.

pop 메서드는 꺼낼 데이터를 head 데이터로 지정하고, 꺼낼 head 데이터의 다음 노드를 새로운 head의 노드로 설정하도록 한다.

isEmpty 메서드는 스택이 비어있다면 True를, 비어있지 않다면 False를 반환하도록 한다.

 

다음 포스팅은 스택의 대척점이라 할 수 있는 Queue(큐)가 될 것이다. 이만 포스트를 줄이겠다 !