<게시물 내부링크>
스택 요약정리 부분 바로가기
파이썬 코드부분 바로가기
자료구조 Stack(스택)에 대한 이해
Stack(스택) motivation: 스택 공부 동기
스택은 데이터를 저장하는 자료구조입니다.
한 번에 하나의 정보를 입력하거나 출력할 수 있어요.
정보의 저장 및 제거는 항상 스택 성분의 마지막위치(최상단)에서 일어나요.
만약 스택을 직접 사용하지 않더라도 구조와 동작을 잘 알아두는 것이 좋습니다.
컴퓨터나 프로그램에서 함수의 실행에 대한 이해에 많은 도움이 되거든요.
대부분의 프로그래밍 언어에서 중첩된 함수를 구현할때,
스택 구조를 이용하고 있어요.
함수가 호출되면 콜 스택에 저장하고, 실행이 완료되면 다시 제거하는 방식입니다..
이러한 스택의 크기는 정해져있어서, 일정 개수 이상의 함수를 중첩하면
스택이 넘치는 오류가 발생해요. 이것을 스택 오버플로우(Stack Overflow)라고해요.
개발자들이 질문을 주고받는 사이트의 이름이
stack overflow(스택 오버플로우) 인것만 생각해 봐도 중요성이 느껴지시죠?.
이제 스택의 개념에대해 살펴봅시다.
스택은 아주 적절하게 명명된 자료구조라서, 그 이름을 이해하는것만으로도
이에 대한 감을 잡을 수 있습니다.
우선 영단어로 stack이 무슨 의미를 갖는지 알아볼까요?
영단어 stack의 뜻
구글에 stack definition(스택의 정의)를 검색하면 나오는 문장입니다.
직역하자면 "물건의 쌓임, 특별히 멋지게 정돈되어 있음" 정도가 되겠네요.
검색결과 그대로 스택이란 가지런히 쌓여 층을 구분할 수 있는 물건들의 더미를 의미합니다.
바로 아래의 사진과 같은 것들은 전부 스택이라 부를 수 있어요.
책으로 스택의 동작을 비유하기
저런 책더미를 만들고, 치우는 과정이 바로 스택 메서드의 동작과정과 똑같답니다.
사진을 찍기 전과 후에 작가분이 어떻게 행동했을지 간단히 생각해 볼까요?
Q. 책더미를 쌓아야겠어요. 위의 사진을 찍은 사람은 저 스택을 어떻게 만들었을까요?
A. 마음에 드는 책을 골라 먼저 놓은 책 위에 새로 고른 책을 쌓았을 겁니다.
Q. 만족스러운 사진이 나왔군요. 이제 책을 정리하기 위해 어떤 방법을 사용할까요?
A. 맨 위에 있는 책부터 정리합니다. 한 권씩 집어서 책꽂이에 꽂아 넣습니다.
위의 두 가지 Q&A가 모두 이해되셨나요?
축하합니다!
스택이라는 자료구조의 구조와 동작을 전부 이해하셨습니다.
스택자료구조의 특징 LIFO: Last In First Out
더미를 쌓는 과정과 다시 정리할 때를 생각해 봅시다.
동작순서의 특징이 보이시나요?
맨 위(peek)에 위치하는 책은 마지막에 놓였습니다.(Last in)
하지만 정리할 때에는 첫 번째로 정리됩니다 (first out).
이러한 특징을 LIFO라고 합니다.
마지막에 들어간 게 처음으로 나온다는 뜻이죠.
스택은 LIFO의 특징을 가지고 있는 자료구조입니다.
*스펠링 축약에 대해 잘 알아두세요.
데이터 입출력의 순서에 비슷한 약어가 많이 쓰입니다.
다음에 알아볼 Queue(큐)라는 친구는 FIFO구조를 가지고 있어요.
스택의 메서드 push와 pop
스택의 동작은 크게 두 개의 메인 메서드로 이루어집니다.
새로운 데이터를 저장하는 push,
저장된 데이터를 출력하는 것은 pop이라는 메서드가 바로 그것이죠.
push는 스택의 맨 위층에 새로운 데이터를 저장합니다.
마찬가지로 pop도 최상단의 정보를 반환하지요.
스택구현은 위 두 가지 동작으로 충분합니다.
그 외의 동작이 존재한다면 스택 전체를 프린트한다던가,
현재의 꼭대기 데이터를 보여던가 하는 부수적인 기능들이죠.
Recap: LIFO, push 그리고 pop
스택은 정보를 순서대로 저장하는 자료구조입니다.
마지막에 저장된 데이터가 가장 먼저 출력되는 LIFO 구조를 가지고 있습니다.
* 데이터의 입, 출력은 1개씩 이루어집니다.
push 메서드는 피크(peek: 현재 꼭대기)에 위치한 데이터 위에 새로운 데이터를 추가합니다.
pop 메서드는 피크 데이터를 반환합니다.
전부 이해 하셨나요?
그렇다면 이제 파이썬 코드를 살펴볼게요.
파이썬으로 구현한 스택 구조
스택을 구현하는데 파이썬의 리스트(list)를 이용했어요.
* 파이썬의 리스트를 사용하여 구현하는 스택의 특징
자바나 c언어의 배열과는 다르게, 파이썬의 리스트는 정보를 추가하면
스스로의 한계 길이가 길어지는 dymanic array랍니다.
그래서 한계용량 초과 시 발생하는 스택 오버플로우는 아무래도 보기 어려울 거예요.
물론 특정 숫자를 스택의 최고길이로 설정하여 인위적인 한계를 보여줄 순 있겠지만
그렇게 하지 않았거든요.
파이썬 코드
class MyStack:
"""
인스턴스 생성시점에 입력받은 list를 stack으로 저장합니다.
만약 그렇지않으면 비어있는 list를 stack 으로 저장합니다.
"""
def __init__(self, input_stack: list = None):
if input_stack is None:
self._stack = []
else:
self._stack = input_stack
def push(self, value):
"""
push 메서드
스택에 정보를 저장합니다.
list의 마지막 인덱스를 추가하는 append 메서드를 사용했습니다.
"""
target = value
self._stack.append(target)
print(f"{target} is pushed!")
def pop(self):
"""
pop 메서드
스택의 피크성분을 출력합니다.
list[-1]은 리스트의 마지막 성분을 반환합니다.
len 메서드로 스택이 비어있는지 확인합니다.
stack의 길이가 0이면 비어있음을 알리는 메시지를 출력합니다.
"""
if len(self._stack) == 0:
print("this stack is empty!!")
else:
target = self._stack[-1]
del self._stack[-1]
print(f"{target} is poped!")
return target
def peek(self):
"""
peek 메서드
필수적이지 않은 메서드입니다.
스택의 피크에 저장된 정보를 보여줍니다.
"""
if len(self._stack) == 0:
print("stack is empty!!")
else:
print(f"peek element : {self._stack[-1]}")
def stack(self):
"""
stack 메서드
필수적이지 않은 메서드입니다.
스택전체를 보여주는 메서드입니다.
"""
stack = self._stack
print(f"state of stack: {stack}")
return self._stack
파이썬의 리스트(list)와 클래스(class) 이용해 구현한 스택의 코드입니다.
인스턴스를 생성해 동작을 확인해 봅시다.
비어있는 스택에 정보를 저장하고 비우기
클래스 생성자에 아무것도 넣지 않은 빈스택을 생성해
정보를 하나씩 집어넣었다가 다시 비워볼게요.
## 새로운 스택을 생성합니다.
fisrt_stack = MyStack()
"""
꼭대기 정보를 확인합니다.
생성자에 아무것도 넣어주지 않았으므로
비어있다는 메시지가 출력됩니다.
"""
fisrt_stack.peek()
## 출력결과: stack is empty!!
"""
pop 데이터를 출력합니다.
마찬가지로 비어있다는 메시지가 출력됩니다.
"""
fisrt_stack.pop()
## 출력결과: this stack is empty!!
##이제 데이터를넣으면서 출력결과를 확인해볼게요
fisrt_stack.push("hello")
## 출력결괴: hello is pushed!
fisrt_stack.stack()
## 출력결과: state of stack: ['hello']
fisrt_stack.push("world")
## 출력결과: world is pushed!
fisrt_stack.stack()
## 출력결과: state of stack: ['hello', 'world']
fisrt_stack.push("!!!!!!!!!!!!!!")
## 출력결과: !!!!!!!!!!!!!! is pushed!
fisrt_stack.peek()
## 출력결과: peek element is : !!!!!!!!!!!!!!
fisrt_stack.stack()
## 출력결과 : state of stack: ['hello', 'world', '!!!!!!!!!!!!!!']
fisrt_stack.pop()
## 출력결과 : !!!!!!!!!!!!!! is poped!
fisrt_stack.stack()
## 출력결과: state of stack: ['hello', 'world']
fisrt_stack.pop()
## 출력결과: world is poped!
fisrt_stack.stack()
## 출력결과: state of stack: ['hello']
fisrt_stack.pop()
## 출력결과: hello is poped!
fisrt_stack.stack()
## 출력결과: state of stack: []
fisrt_stack.peek()
## 출력결과: stack is empty!!
이미 정보가 들어있는 리스트로 스택 만들기
클래스 생성자에 리스트를 집어넣어 정보가 있는 스택을 생성한 후
몇 개의 데이터를 제거하고 새로운 데이터를 넣어볼게요.
second_stack = MyStack(["this", "is", "a", "stack"])
second_stack.stack()
## 출력결과 : state of stack: ['this', 'is', 'a', 'stack']
second_stack.peek()
## 출력결과 : peek element : stack
second_stack.pop()
## 출력결과 : stack is poped!
second_stack.pop()
## 출력결과 : a is poped!
second_stack.push("fun")
## 출력결과 : fun is pushed!
second_stack.stack()
## 출력결과 : state of stack: ['this', 'is', 'fun']
후기
자료구조와 알고리즘을 복습하기 위해 파이썬으로 하나하나 구현해보려고 합니다.
저는 주력언어를 자바스크립트로 정했지만 수학과 관련한 프로그래밍은 파이썬환경이 적합한것 같아서요.
다음에는 Queue(큐)나 Heap(힙)을 들고오겠습니다.
그동안 존댓말과 반말을 혼용해서 글을 작성했어요.
하지만 오늘은왠지 당근 테크블로그의 문체가 이뻐 보여서 전부 존댓말로 작성했습니다.
읽어주셔서 감사합니다. 오탈자나 오류는 댓글로 알려주세요!
'it공부 (개념) > 자료구조와 알고리즘 그리고 파이썬' 카테고리의 다른 글
| Queue(큐): 큐는 차례를 기다리는 줄과 같다. /파이썬 리스트로 구현해보기 enqueue, dequeue (0) | 2023.03.13 |
|---|---|
| 파이썬 자료구조(data structure)의 속성. sequence. mutable (0) | 2023.01.01 |