스택을 간단하게 설명하자면 후입선출(LIFO)특성을 가지는 자료구조를 일컫는다.
스택에 데이터를 넣는 작업을 푸시
스택에서 데이터를 꺼내는 작업을 팝
겹쳐 쌓은 접시처럼 데이터를 넣고 꺼내는 작업을 맨 위부터 수행한다.
이렇게 푸시하고 팝하는 윗부분을 꼭대기(Top),아랫부분(Bottom)이라고 한다.
스택 구현
스택 배열: stk
푸시한 데이터를 저장하는 스택 본체인 list형 배열입니다.
스택 크기: capacity
스택의 최대 크기를 나타내는 int형 정수(이 값은 배열 stk의 원소 수인 len(stk)와 일치한다.)
스택 포인터: ptr
스택에 쌓여있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 한다.
ex)스택이 비어있으면 ptr의 값은 0이 되고 가득 차 있으면 capacity와 같은 값이 된다.
cf)Fixed stack 클래스는 일정한 크기를 가지는 스택을 구현한 클래스이다. Fixed stack 클래스는 스택의 크기를 생성자에서 지정하고,그 이상의 데이터가 push되는 경우 에러를 발생시킨다. 따라서 FixedStack 클래스를 사용하여 스택 작업을 수행하는 경우 스택 포인터 ptr값은 반드시 0 이상이거나 capacity값 이하가 된다.
스택이 비어 있는지 가득 차 있는지를 알아내는 예외 클래스와 사용함수
예외 처리 클래스 Empty
pop()함수 or peek()함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리이다.
예외 처리 클래스 Full
push()함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리이다.
초기화하는 'init()'함수
init()함수는 스택 배열을 생성하는 등의 준비 작업을 수행한다. 매개변수로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고 모든 원소가 None인 리스트형 stk를 생성한다.
쌓여 있는 데이터 개수를 알아내는 len()함수
len()함수는 스택에 쌓여 있는 데이터 개수를 반환한다. 여기서 스택 포이터 ptr값을 그대로 반환한다.
스택이 비어 있는지를 판단하는 is_empty()함수
is_empty()함수는 데이터가 하나도 쌓여 있지 않은 상태를 판단하는 함수이다. 스택이 비어 있으면 True를 그렇지 않으면 False를 반환한다.
스택이 가득 차 있는지를 판단하는 is_full()함수
is_full()함수는 더 이상 데이터를 푸시할 수 없는 상태를 판단하는 함수이다. 스택이 비어 있으면 True를 그렇지 않으면 False를 반환한다.
데이터를 푸시하는 push()함수
push()함수는 스택에 데이터를 추가한다. 그러나 스택이 가득 차서 더 이상 푸시할 수 없는 경우에는 FixedStack.Full을 통해서 예외 처리를 내보낸다. 스택이 가득 차 있지 않으면 전달받은 value를 배열원소 stk[ptr]에 저장하고 스택 포인터 ptr을 1 증가시킨다.
데이터를 팝하는 pop()함수
pop()함수는 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환한다. 그러나
스택이 비어서 팝할 수 없는 경우에는 Fixedstack.Empty를 통해서 예외처리를 내보낸다. 스택이 비어 있지 않으면 스택 포인터 ptr 값을 1 감소시키고 stk[ptr]에 저장된 값을 반환한다.
데이터를 들여다보는 peek()함수
peek()함수는 스택의 꼭대기 데이터를 들여다본다. 그러나 스택이 비어 있는 경우에는 FixedStack.empty를 통해서 예외 처리를 내보낸다. 스택이 비어 있지 않으면 꼭대기 원소 stk[ptr-1]의 값을 반환한다. 데이터의 입출력이 없으므로 스택포인터는 변화하지 않는다.
스택의 모든 데이터를 삭제하는 clear()함수
clear()함수는 스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스텍을 만든다. 스택 포인터 ptr의 값을 0으로 하면 끝난다.
데이터를 검색하는 find()함수
find()함수는 스택 본체의 배열 stk 안에 value와 값이 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열 어디에 들어 있는 지를 검색한다.
데이터 개수를 세는 count()함수
count()함수는 스택에 쌓여 있는 데이터(value)의 개수를 구하여 반환한다.
데이터가 포함되어 있는지 판단하는 contains()함수
contains()함수는 스택에 데이터(value)가 있는지 판단한다.
있다면 True를 반환하고 그렇지 않으면 False를 반환한다.
스택의 모든 데이터를 출력하는 dump()함수
dump()함수는 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력한다.
