파이썬으로 구현하는 자료구조! - 스택 ( Stack )

오늘부터 시간이 날때마다 초심으로 돌아가 자료구조와 알고리즘에 대해서 하나씩 차근차근 공부해보려 합니다.

 

그 시작으로 이번 글에서는 파이썬을 활용하여 자료구조 중에 하나인 스택에 대해서 적어보려합니다.

1. 스택(Stack)이 뭐야?

스택은 데이터의 삽입과 삭제가 데이터의 가장 한쪽 끝에서만 일어나는 자료구조 입니다.

가장 마지막에 삽입된 데이터가 가장 먼저 사용되거나 삭제됩니다.

이를 후입선출 ( LIFO - Last In, First Out )이라고 합니다.

 

우리 일상 속에서 쉽게 볼 수 있는 것 중에 스택과 같은 것을 이야기 해보자면 프링글스를 예로 들어볼 수 있습니다.

프링글스도 과자통에 가장 마지막으로 담긴 감자칩이 가장 먼저 통에서 나오는 후입선출 구조를 가지고 있기 때문입니다.

 

알고리즘 문제를 풀면서는 아래와 같은 괄호와 관련된 문제를 풀때 많이 사용합니다.

[BaekJoon] 9012번 : 괄호 (Python)

[HackerRank] Stacks and Queues : Balanced Brackets (Python)

2. 주요 Method

2-1. push, pop

 

데이터를 삽입하는 과정을 push,

가장 마지막에 삽입한 데이터를 삭제하는 과정을 pop이라고 부릅니다.

데이터를 삭제하는 pop의 경우 현재 스택에 데이터가 비어있는지 여부를 먼저 확인한 후에 실행합니다.

2-2. top

pop이 가장 마지막에 삽입한 데이터를 삭제하는 것이라면

top은 가장 마지막에 삽입한 데이터를 삭제하지 않고 return 해주는 메소드입니다.

2-3. isEmpty

isEmpty는 현재 스택이 비어있는지 여부를 확인하는 메소드 입니다.

3. 코드로 구현하기

3-1. Python List로 구현하기

class Stack():
    def __init__(self):
        self.stack = []
        
    def push(self, data):
        self.stack.append(data)
        
    def pop(self):
        pop_object = None
        if self.isEmpty():
            print("Stack is Empty")
        else:
            pop_object = self.stack.pop()
            
        return pop_object
            
    def top(self):
        top_object = None
        if self.isEmpty():
            print("Stack is Empty")
        else:
            top_object = self.stack[-1]
            
        return top_object
            
            
    def isEmpty(self):
        is_empty = False
        if len(self.stack) == 0:
            is_empty = True
        return is_empty

python의 List는 그냥 바로 스택으로 활용해도 되지만 그 List를 활용하여 구현해보았습니다.

 

push는 list의 append 메소드를 활용해서 구현하였습니다.

 

pop은 먼저 stack이 비어있는지 isEmpty 메소드를 활용하여 확인하고

비어있다면 "Stack is Empty"를 출력하고 None을 return하고

비어있지않다면 list의 pop 메소드를 활용하여 현재 Stack에서 가장 마지막에 삽입된 값을 꺼내 return 하도록 하였습니다.

 

top도 pop과 마찬가지로 isEmpty 메소드를 활용하여 Stack이 비어있는지 확인 후 

비어있다면 "Stack is Empty"를 출력하고 None을 return

비어있지않다면 list의 가장 마지막 값을 인덱스 -1 을 활용하여 값만 가져와 return 하도록 하였습니다.

 

isEmpty는 스택의 값이 하나도 없을 경우 True, 값이 있을 경우 False를 return 하도록 하였습니다.

3-2. Python Singly Linked List로 구현하기

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
        self.head = new_node
        
    def pop(self):
        pop_object = None
        if self.isEmpty():
            print("Stack is Empty")
        else:
            pop_object = self.head.data
            self.head = self.head.next
        return pop_object
    
    def top(self):
        top_object = None
        if self.isEmpty():
            print("Stack is Empty")
        else:
            top_object = self.head.data            
        return top_object
    
    def isEmpty(self):
        is_empty = False
        if self.head is None:
            is_empty = True
        return is_empty

먼저 LinkedList를 만들기 위해 필요한 Node를 정의해줍니다.

각각의 노드는 data와 next로 이루어져 있습니다.

 

push는 먼저 새로운 데이터를 담은 노드를 먼저 생성합니다.

생성한 이후 이 노드의 next에 현재 리스트의 head를 연결해줍니다.

그 다음 다시 self.head에 새로운 데이터를 담은 노드를 연결해줍니다.

 

pop은 먼저 isEmpty 메소드를 통하여 스택이 비어있는지를 먼저 확인하고

비어있다면 "Stack is Empty"를 출력하고 None을 return

비어있지않다면 head 노드의 데이터를 꺼내온 뒤 head에 self의 next 노드를 넣어주고 아까 꺼낸 데이터를 return 합니다.

 

top도 pop과 마찬가지로 먼저 isEmpty 메소드를 통하여 스택이 비어있는지를 먼저 확인하고

비어있다면 "Stack is Empty"를 출력하고 None을 return

비어있지않다면 head 노드의 데이터를 꺼내와 return 합니다.

 

isEmpty는 head가 None일경우 True를 None이 아닐 경우 False를 return합니다.

4. 관련 문제 풀어보기

Programmers - 코딩테스트 연습 > 스택/큐

프로그래머스

BaekJoon - 단계별로 풀어보기 > 스택

스택 단계

HackerRank - Interview Praperation Kit > Stacks and Queues

Solve Stacks and Queues Interview Questions | HackerRank

LeetCode - Problems > Tags > Stack

Problems - LeetCode

5. 구현 코드 GitHub

SOMJANG/DataStructure-Algorithm-Practice

 

앞으로 큐 > 트리 > 그래프 순으로 포스팅 할 예정입니다.

 

읽어주셔서 감사합니다.

 

다른 자료구조 알아보기

파이썬으로 구현하는 자료구조! - 스택 ( Stack )

파이썬으로 구현하는 자료구조! - 큐 ( Queue )