위코드 개강( '20.5/25, 月 )전까지 자료구조를 한번 정리하려고 한다.
1. 스택이란?
스택(stack)은 일상생활에서 물건을 쌓는 행위와 같다.
마치, 100원짜리 동전을 하나하나 쌓아 올리는 것처럼 말이다.
가장 최근에 쌓아올린 동전(즉, 맨 위의 동전)부터 하나씩 꺼낼 수 있다.
회전 초밥집에서 먹은 접시를 테이블에 계속 쌓는 모습을 상상하면 좋다.
- top(스택의 끝, 최근 데이터)
- bottom(스택의 밑, 첫 데이터)
맨 밑에 있는 100원 혹은 접시를 먼저 빼낼 수 없다.
맨 밑의 100원(또는 접시)를 빼내려면,
그 위에 쌓인 것들부터 빼내야한다.
따라서, LIFO라고도 한다.
Last In, First Out
2. 스택 설계
1) 데이터 삽입(push, 데이터의 삽입을 'push'라고 부른다.)
- "스택에 값을 푸시해라"
2) 데이터 추출 및 삭제(pop)
- "스택으로부터 값을 팝해라"
3) 데이터 검색(find)
4) 데이터 보기(show)
위 4가지의 메소드를 스택 클래스에서 정의한다.
3. 스택 코드 작성
class Stack():
# 스택 초기화 : 스택 내부의 empty 리스트를 생성해준다.
def __init__(self):
self.item_list = []
# 스택에 데이터 삽입(LIFO) : 리스트에 데이터를 append시키는 방식
def push(self, data):
self.item_list.append(data)
# 스택에 내가 찾고자 하는 데이터가 있는지 확인하는 메소드
def find(self, data):
# 스택 내 데이터가 없다면
if not self.item_list:
print("stack is empty")
# 스택 내 데이터가 있다면
else:
for item in self.item_list:
if item == data:
return self.item_list.index(item)
# 스택에서 가장 윗부분부터 데이터를 빼서 삭제하는 과정 : pop사용
def pop(self):
return self.item_list.pop()
# 스택 내 데이터를 전부를 보는 메소드
def show_all(self):
print (self.item_list)
# 스택 선언
stack = Stack()
# 스택 내 데이터 삽입(push) : 57 -> 5-> ... -> 50000 순으로 삽입
stack.push(57)
stack.push(5)
stack.push(6)
stack.push(0)
stack.push(-11)
stack.push(50000)
# 스택에서 찾고자 하는 데이터 찾기
index_data= stack.find(200)
print(index_data)
# 스택 전체 데이터 보기
stack.show_all()
# 스택에서 데이터 추출
for i in range(len(stack.item_list)):
if not stack.item_list:
print("stack is empty")
break
else:
# 50000 - > -11 -> ... -> 5 -> 57 순으로 데이터 추출
result = stack.pop()
print(result)
[57, 5, 6, 0, -11,50000] 이었던 stack이
pop을 진행하자
50000 -> -11 -> 0 -> ... - >57 순서로
데이터가 추출되고 보여지는 것을 확인할 수 있다.
4. 코드 설명
result = stack.pop() 이 핵심이라고 생각한다.
C언어 개념으로 바라보자면,
pop() 메소드는 리스트의 마지막 인덱스 주소를 알고있고
그 메모리 주소에 저장된 데이터를 호출 후 삭제한다.
포인터는 다시 리스트의 마지막 인덱스 주소를 저장한다.
따라서, Last In(마지막으로 들어간 데이터가)
Firtt Out(가장 먼저 나온다)
사실 이렇게 구현되는 이유를 pop메소드의 특성이라고만 결부지을 순 없다고 본다.
왜냐하면, 애초에 데이터 삽입을 list.append(data)로 했기 때문이기도 하다.
마지막에 append한 데이터가 리스트에 맨 마지막에 있기때문에, 맨 마지막 데이터가 pop이 되는 것이다.
만약에 데이터가 앞에서부터 저장되는 경우고,
pop을 그대로 사용한다면
더 이상 Last In, First Out 방식이 아니게 되기 때문이다.
5. 스택에 대한 단상
서두에서 언급했듯이 매우 직관적인 자료구조라고 생각한다.
이삿짐 정리시 쌓여진 책들을 위에서부터 꺼내 하나하나 정리하듯이 말이다.
그 이미지를 연상하며 stack 클래스를 정의하면 바로 구현할수 있는 자료구조 중 하나라고 생각한다.
하지만,
데이터 셋이 커지면 비효율적인 방식이라는 것을 직관적으로 알 수 있다.
100원짜리 동전이 50개 쌓여있는데, 꺼낼 동전이 맨 아래에서 5번째에 있다면?
다른 예로, 스택 자료구로 저장된 1000개의 이름이 있다고 하자.
최악의 경우 1000개의 데이터를 모두 검색해야 한다.
(인덱스 0에 내가 찾고자 하는 사람 이름이 저장된 경우 말이다.)
스택은 데이터를 장기간 저장할 목적으로 사용하진 않는다.
임시 데이터를 다뤄야 하는 상황에 많이 적용되는 자료구조다.
- One step at a time - 