[Python / 자료구조] Python으로 Stack 구현하기

---

Python으로 스택(Stack) 구현하기

이번에 면접 대비를 하게 되면서, 간만에 기본에 충실하자! 라는 느낌으로 Python으로 기본적인 자료구조 구현을 진행해보았다. C++로 할 때보다 확실히 쉽고 금방 구현이 가능하다. 특히 Stack의 경우 list에서 애초에 내부적으로 거의 다 구현이 되어있어서 추가적으로 뭔가 만들 필요가 없을 정도다.

 

 

스택(Stack)의 기본 구조

---

 

• 구현에 앞서 간략히 스택에 대해 설명해보자면, 아래의 특성을 가진다.
  
  
• 스택은 기본적으로 LIFO(Last In First Out) 구조를 지니고 있는 선형 자료구조이다.
  
  
• 말 그대로 스택(쌓다) 이므로, 주사위 쌓기를 생각해보면 어떤 구조인지 알 수 있다. 쌓기를 시작할 때는 당연히 맨 밑부터 쌓아나가야하며, 데이터를 뺄 때는 맨 위에서부터 뺄 수 밖에 없다.
  
  
• LIFO의 특성을 활용해야하는 다양한 알고리즘 문제 풀이에서 자주 사용된다. 

 

 

스택이 가져야 할 Method 목록

---

• push(x) : 스택에 x라는 값을 집어 넣는다.
  
  
• pop() : 스택의 맨 윗부분(마지막에 들어온 원소)를 꺼내고 반환한다.
  
  
• size() : 스택의 길이를 반환한다.
  
  
• empty() : 스택이 비어있는지에 대한 유무를 반환한다.
  
  
• top() : 현재 스택의 맨 위에 있는 원소를 보여준다. (꺼내지는 않음)

 

 

구현

---

사실 Python에서 기본적으로 쓰이는 list 자료구조가 stack과 같다. 딱히 직접 구현해야 할 내용이 없지만 Class화를 시켜본다면 아래와 같이 구현할 수 있다.

 

그리고 백준에 이를 다루는 문제가 있으니, 직접 풀어보는 것도 좋을 것 같다!
https://www.acmicpc.net/problem/10828

 

'''
    push(x) - input x to stack
    pop() - delete last element of stack and return it
    size() - return length of stack
    empty() - return boolean that checks whether stack has an element
    top() - return top of stack
'''
class HyunStack():
    def __init__(self):
        self.stack = []

    def push(self,x):
        self.stack.append(x)

    def pop(self):
        return self.stack.pop() if self.stack else -1

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

    def empty(self):
        return not self.stack

    def top(self):
        return self.stack[-1] if self.stack else -1

if __name__ == "__main__":
    q = HyunStack()
    q.push(1)
    q.push(2)
    print(q.top())
    print(q.size())
    print(q.empty())
    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.size())
    print(q.empty())
    q.push(3)
    print(q.empty())
    print(q.top())