또 순서가 어그러졌다. 원래 힙 정렬(Heap Sort)에 대해 포스팅을 작성하려했는데, 힙 정렬 포스팅을 하려니 Heap이 발목을 잡고, Heap을 포스팅하려니 이진 트리(Binary Tree)가 발목을 잡는다. 물론 바로 힙 정렬 내용을 포스팅하고 추후 링크로 연관된 내용에 대한 포스팅을 연결해도 되지만, 그래도 직접 코드도 작성해보지 않고 포스팅하기에는 틀린 내용도 있을까봐 자신도 없고 해서 테스트 후에 천천히 작성을 하려 한다. 조금 시간도 벌 겸, 필자가 이전 회사 업무 중에 많이 사용했던 Stack과 Queue에 대해서 조금 다루어볼까 한다.
먼저 이번 포스팅은 Stack 부터.
** Java의 Stack과 Queue는 이 포스팅을 참고하자
1. Stack 개요
맨날 숫자 줄 세우기 놀이만 하다가 자료구조로 넘어오니 마음이 편하다. 그림 그릴 게 많지 않거든.
Stack은 선형 자료 구조의 일종이다. 선형 자료구조라서 생긴 것은 배열처럼 생겼는데, 한 쪽이 뚫려 있는 자료 구조다. 그리고 이 뚫려있는 곳으로만 저장할 자료가 들고 나고 한다는 특징이 있다. 프링*스 과자 통이 Stack과 동일한 구조를 띄고 있어서 Stack에 대한 설명을 보면 프링*스 아저씨가 꼭 빠지지 않고 나온다.
참고로 필자는 오리지널을 제일 좋아한다. 그런데 저 통 디자인은 개발자가 했을까?
필자의 대학 전공과 연관있는 생물학에서는 "생긴대로 논다(Morphology: 형상학)"라는 용어가 있는데, 이 스택도 가만 보면 생긴대로 논다. 저 프링*스 아저씨가 그려진 통을 보면 알겠지만, 입구가 하나라 먼저 통에 넣은 과자가 제일 밑바닥으로 들어가고, 꺼낼 때 가장 마지막에 나오게 된다. 반대로 나중에 들어간 과자는 꺼낼 때 가장 먼저 나온다. 과자를 가운데에 끼워넣겠다고 통 가운데를 자르면서 배열처럼 Pringl*s[4]를 사용할 수도 없다.
정리하자면 Stack은 선형 자료 구조이나, 특정 방향으로만 데이터의 유입과 유출이 일어나고, 가장 최근에 Stack에 저장된 데이터가 가장 먼저 나온다는 특징이 있다. 마지막 특징은 조금 더 고상한 용어로 후입선출(Last In First Out, LIFO)라고 한다.
Stack을 사용은, 이전의 데이터를 참조해야하는 작업들이 많다. 위의 Java 링크에도 작성한 내용이지만, 문서나 그림판과 같은 작업 프로그램의 Undo와 Redo기능, 혹은 웹 브라우저의 뒤로가기와 다음 페이지(가 맞나?) 이동이 Stack을 사용한 구현 기능이다.
개요는 이게 끝이다.
2. Stack 기능 및 용어
Stack은 아래의 용어로 구성이나 기능이 정의되어 있다.
| 용어 | 구성 및 기능 |
| capacity | Stack의 최대 크기 |
| ptr | Stack에 쌓인 데이터의 갯수 표시 |
| stk | Stack을 의미하는 용어 |
| top | 최종 유입(Push) 된, 처음 유출(Pop)되는 데이터 |
| bottom | 유입된 데이터의 가장 아랫부분 |
| clear | Stack 비우기 |
| dump | Stack 내 모든 데이터 출력 |
| find | 데이터 검색 |
| peek | 마지막 데이터 값의 반환 또는 출력 |
| pop | 마지막 데이터 값 추출 및 반환 |
| push | Stack에 데이터 추가 |
Stack은 데이터의 저장과 유출이 한 쪽 끝 단에서 발생한다는 것만 제외한다면, 구성과 기능에 대한 내용도 이해하기 어렵지는 않다. 이제, 위 내용으로 Stack을 코드로 만들어보려한다.
3. Stack 구현 코드
Stack은 구성과 기능이 많기 때문에 이전의 정렬 알고리즘을 구현할 때와 같이 함수로만 작성하기에는 어려움이 많다. 그래서 아래와 같이 클래스 뼈대를 만들었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = __capacity
self.__stk = [None] * self.__capacity
def clear(self) -> None:
pass
def dump(self) -> None:
pass
def find(self) -> None:
pass
def peek(self) -> None:
pass
def pop(self) -> None:
pass
def push(self) -> None:
pass
|
cs |
1) StackTest 클래스의 멤버변수는 모두 private 접근 제어자를 사용하기 위해 변수명 앞에 언더바 두 개를 추가했다. 클래스 외부에서 self.__stk나 self.__capacity의 내용을 함부로 변경하지 못하게 하기 위함이다.
2) 쌓여있는 데이터의 수를 반환하는 ptr의 경우, top과 동일하게 움직이므로 클래스의 멤버 변수로 굳이 넣지 않고 self.__top이 기능을 대체하도록 했다. 단, self.__top의 경우 데이터가 마지막으로 추가된 Index를 가리키므로 초기 값을 -1로 지정했다.
3) self.__BOTTOM은 항상 0번 index에 위치하므로 변수명을 대문자로 작성했다.
여기에 추가로 데이터의 추가 및 삭제 시, self.__stk가 가득 차 있는지(__is_full) 비어있는지(__is_empty) 확인할 수 있는 내부 매서드가 필요하다. 이 매서드 역시 굳이 외부에서 호출할 일이 없으니 private 접근자로 매서드를 생성하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
def __is_empty(self) -> bool:
pass
def __is_full(self) -> bool:
pass
def clear(self) -> None:
pass
def dump(self) -> None:
pass
def find(self) -> None:
pass
def peek(self) -> None:
pass
def pop(self) -> None:
pass
def push(self) -> None:
pass
|
cs |
(1) private 매서드 작성: __is_empty(), __is_full()
self.__top 그리고 self.__capacity가 모두 정의되어 있으므로, 매서드의 작성은 매우 간단하게 끝이 난다. __is_empty()의 경우 self.__top이 -1인 경우, __is_full()의 경우 self.__top과 self.__capacity - 1의 값이 같다면 True를 반환하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
def __is_empty(self) -> bool:
return self.__top == -1
def __is_full(self) -> bool:
return self.__capacity - 1 == self.__top
|
cs |
(2) clear() 및 dump() 매서드 작성
clear() 매서드와 dump() 매서드는 매서드에서 구현하는 기능의 특성 상 self.__stk이 비어있던, 꽉 차 있던 기능에는 큰 영향을 미치지 않는다. 따라서 아래와 같이 간단히 코드를 작성할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
...(생략)
def clear(self) -> None:
self.__stk = [None] * self.__capacity
self.__top = -1 return None
def dump(self) -> None:
print(self.__stk)
return None
|
cs |
Python에서 Stack 구현 시, 내부적으로 List를 사용하나 직접 Index 값에 접근하여 데이터를 변환하게 되면 그냥 List를 사용하는 것과 동일하니 clear() 매서드에서 기존 self.__capacity 크기만큼 배열(여기서는 List)을 생성하도록 만들어준다. 또한 Stack이 완전히 비워지게 되는 순간 self.__top 역시 -1로 초기화되도록 코드를 추가해준다.
dump() 역시 출력 외에 별다르게 볼 것이 없으므로, self.__capacity 변수 저장 값을 전부 출력하도록만 코드를 작성하면 된다.
(3) push() - 데이터 추가 매서드 작성
본격적으로 self.__stk에 데이터를 추가해보자. 우선 매서드를 통해 데이터를 넣으려면, 추가할 데이터를 매서드 인자로 받아와야한다. 우선은 String으로 데이터를 추가하는 것으로 진행해보려한다.
데이터의 추가는 self.__stk에서 self.__top 값에서 1을 더한 Index에 추가가 되어야한다(초기값을 -1로 설정했기 때문이다). 또한 self.__stk가 가득 차 있는 경우에는 데이터의 추가가 불가능하므로 이에 대한 별도 처리도 진행해주어야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
...(생략)
def push(self, data:str) -> None:
if not self.__is_full():
self.__top += 1
self.__stk[self.__top] = data
else:
print("[WARNING] Stack is full")
return None
|
cs |
self.__stk[self.__top] 값이 None인 것도 검증하고 데이터를 넣으면 좋겠지만 이 포스팅에서는 생략한다.
(4) peek() - Stack의 Top 값 반환 또는 출력.
peek은 단순히 self.__top에 위치하고 있는 stack 저장 값을 반환하거나 출력만 할 뿐, self.__stk의 데이터에는 영향을 미치지 않는다. 따라서 값을 반환하도록 하던지 값 반환없이 print()만 진행하던지 크게 상관은 없다. 필자는 값을 반환하는 방향으로 매서드를 작성했다. 물론, self.__stk이 비어있으면 반환할 값이 없으므로 이에 대한 검증도 매서드 초반에 진행해주어야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 |
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
...(생략)
def peek(self) -> str:
if not self.__is_empty(): return self.__stk[self.__top]
print("[WARNING] Stack is empty")
return None
|
cs |
(5) pop() - Stack의 Top 값 반환 및 Stack Top 값 제거
pop()은 peek()과 달리, Stack의 Top 값을 반환받음과 동시에, Stack에서 Top 값을 제외한다. 따라서 pop() 매서드는 값을 반환하면서 Stack에서 없애는 동시에 self.__top 값도 1 감소시켜 top 값이 stack 내 마지막 저장 값을 가리키도록 만들어주어야 한다. 단, Stack에서 데이터 삭제 시, Stack의 크기는 유지해야하므로, self.__top 위치의 데이터를 None 값으로 대체해주어야 한다. 마찬가지로 Stack이 비어있는 상태에서는 pop() 매서드가 동작하지 않으므로 이에 대한 검증도 매서드 초반에 진행해주어야 한다.
그런데 이미 필자는 peek() 매서드에서 Stack의 Top 값을 반환하도록 함수를 작성했기 때문에, 괜히 pop() 매서드 내에 중복되는 함수를 작성할 이유가 없다. 따라서 peek() 매서드를 활용하여 아래와 같이 pop() 매서드를 작성했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
...(생략)
def pop(self) -> None:
tmp = self.peek()
if tmp is not None:
self.__stk[self.__top] = None
self.__top -= 1
return tmp
return None
|
cs |
self.peek() 매서드로부터는 반드시 top 값이 반환되어야하나, Stack이 비어있는 경우라면 None이 반환되므로 이에 대한 검증을 진행했다. pop()의 경우 tmp 변수에 self.peek()의 결과가 저장되는데, 이 값이 None인 경우는 self.__top index의 저장 값이 None인 경우 또는 Stack이 빈 경우 뿐이다. 전자의 경우 코드 작성을 잘못하지 않는 이상 벌어질 수 없는 일이므로, tmp is None이 True인 경우 Stack이 비어있는 경우 밖에 없다. 이 때 WARNING 로그는 peek() 매서드에서 이미 출력을 진행하므로 pop()에서는 단지 None만 반환하면 된다.
(6) find() - Stack 내 저장된 데이터 찾기
마지막으로 find() 매서드다. find()는 Stack 내에 특정 값이 저장되어 있는지 아닌지 확인하는 매서드다. 따라서 self.__BOTTOM부터 self.__top index까지의 배열을 스캔한 뒤, 일치하는 값이 있다면 True를, 일치하는 값이 없다면 False를 반환하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class StackTest():
def __init__(self, capacity:int=10):
self.__BOTTOM = 0
self.__top = -1
self.__capacity = capacity
self.__stk = [None] * self.__capacity
...(생략)
def find(self, data:str) -> bool:
for idx in range(self.__BOTTOM, self.__top + 1):
if data == self.__stk[idx]:
return True
return False
|
cs |
위에서 구현한 코드는 아래와 같이 잘 동작함을 확인할 수 있다.
IT 보안 물을 꽤 많이 먹어서인지, 마음같아서는 clear()도 아무나 못하게 보안을 걸어버리고 싶은데, 포스팅 내용을 벗어나는 내용이라 스킵한다.
다음 포스팅은 Queue에 대해서 다루어보려한다.
Fin.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 16. 선형 자료 구조 - Queue(1) (0) | 2024.03.20 |
|---|---|
| [자료구조 with Python] 14. 정렬 알고리즘(7), 쉘 정렬(Shell Sort) (0) | 2024.03.18 |
| [자료구조 with Python] 13. 정렬 알고리즘(6), 퀵 정렬(Quick Sort) (0) | 2024.03.15 |
| [자료구조 with Python] 12 - 정렬 알고리즘(5), 병합 정렬(Merge Sort) (0) | 2024.03.13 |
| [자료구조 with Python] 11 - 정렬 알고리즘(4), 선택 정렬(Selection Sort) (0) | 2024.03.12 |
댓글