0. Introduction
- 이번 chapter의 학습은 Do it! 자료구조와 함께 배우는 알고리즘 입문로부터 학습했습니다.
- 더 자세한 내용과 관련 내용의 코드는 위 서적의 출판사 사이트에서 확인하실 수 있습니다.
1. 스택(Stack)
데이터를 임시 저장할 때 사용하는 자료 구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In, First Out) 방식이다.
이 스택에 데이터를 넣는 작업을 푸시(push) 라 하며, 스택에서 데이터를 꺼내는 작업을 팝(pop) 이라 한다.
회전 초밥 집에서 먹은 후, 쌓인 접시를 생각해보자. 마지막에 먹는 초밥 접시가 맨 위에 있고, 이 접시들을 꺼낸다고 하면 마지막에 먹은 초밥 접시가 제일 먼저 꺼내진다.
이렇게 쌓인 스택 자료 구조에서 쌓인 데이터의 윗 부분, 아랫 부분을 별도로 부르는 명칭이 있다.
윗 부분은 꼭대기(top), 아랫 부분은 바닥(bottom) 이라 한다.
1.1 스택: list형 배열
이 스택(stack, stk)은 list형 배열이다.
list의 index가 0으로 갈수록 위의 바닥(bottom) 과 가까워지고, 바깥쪽으로 갈수록 꼭대기(top) 에 가까워진다고 생각하자.
또한, 이 스택의 크기는 capacity 단어가 의미하며, 스택에 쌓여 있는 데이터의 개수를 나타내는 정수값을 스택 포인터(stack pointer, ptr) 라 한다.
그래서, stk가 비어 있으면 ptr은 0이 되고, stk가 가득 차면 capacity와 동일한 값이 된다.
1.2 고정 길이 스택을 구현하기 위한 클래스와 메서드 종류
그러면 고정 길이 스택을 구현하기 위한 클래스와 메서드를 알아보자.
아래와 같이 정리하는 이유는 이 스택을 구현하기 위한 기본 틀을 정립하기 위함이다.
메서드 명이 정확히 일치하지 않을지라도 다음과 같은 기능을 구현할 필요가 있다는 걸 알기 위함이다.
초기화 __init__ method
- 스택 배열을 생성하는 준비 작업을 수행하는 함수로서, capacity 만큼으로 스택 크기가 결정된다. 첫 모든 원소는 None이 list가 생성된다.
데이터 갯수를 알 수 있는 __len__ method
- stack에 쌓여 있는 데이터 개수를 반환한다.
stack이 비어 있는지 판단하는 is_empty() method
- stack이 비어 있는지 판단하여, 비어있으면 True, 그렇지 않으면 False를 반환한다.
stack이 가득 차 있는지를 판단하는 is_full method
- stack이 가득 차 있는지 판단하여, 가득차면 True, 그렇지 않으면 False를 반환한다.
예외 처리 클래스 Empty와 Full
- Empty class는 pop() 함수를 호출할 때, 비어있으면 내보내는 예외처리 class다.
- Full class는 push() 함수를 호출할 때, 가득 차 있으면 내보내는 예외처리 class다.
데이터를 푸시하는 push() method
- stack에 데이터를 추가한다.
데이터를 팝하는 pop() method
- stack의 top에서 데이터를 꺼내어 그 값을 반환한다.
데이터를 들여보는 peek() method
- stack의 꼭대기 data를 들여다본다.
스택의 모든 데이터를 삭제하는 clear() method
- stack에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만든다.
스택의 데이터를 검색하는 find() method
- 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인
데이터 갯수를 세는 count() method
- stack에 쌓여 있는 데이터의 갯수를 구한다.
데이터가 포함되어 있는지 판단하는 __contains__ method
2. 큐(Queue)
데이터를 임시 저장할 때 사용하는 자료 구조로, 데이터의 입력과 출력 순서는 선입선출(FIFO: First In, First Out) 방식이다.
스택과 동일하게 list형 배열이며, 은행 창구에서 차례를 기다리거나, 마트에서 계산을 기다리는 줄을 생각하면 된다.
데이터를 꺼내는 쪽을 프런트(Front) 라고 하며, 맨 앞 원소를 가리킨다.
데이터를 넣는 쪽을 리어(rear) 라고 하며, 맨 끝 원소를 가리킨다.
리어 에 데이터를 추가하는 작업을 인큐(enqueue) 라고 하며, 프런트 에서 데이터를 꺼내는 작업을 디큐(dequeue) 라고 한다.
스택과는 달리 데이터를 추가하고 꺼내는 작업의 방향이 다르다는 걸 아래 이미지로 볼 수 있다.
이미지 상의 차이로 큐는 디큐를 하면 전체 배열을 위로 하나씩 올려야 하는 비용이 들고 복잡도로 판단하자면 O(n) 이다.
그래서 이를 해결하는 방법이 링 버퍼(ring buffer) 다. 이 방식은 인큐와 디큐에 따라 시작 원소와 끝 원소가 달라지는 상황에 맞춰서 전체 원소를 옮기는 것이 아닌 프런트(Front) 와 리어(Rear)의 각 인덱스를 계속해서 바꾸는 것이다. 이런 경우 복잡도는 O(1) 이다. 아래 이미지를 참조하자.
from: RingBuffer aka Circular Queue
그러면, 이 큐를 구현하기 위한 클래스와 메서드에는 무엇이 필요할까???
고정 길이 큐를 구현하기 위한 클래스와 메서드 종류는 위에 스택과 동일하므로, 스택을 참고하자.