[Data Structure] 스택

geonhee1492·2022년 6월 2일
0

자료구조

목록 보기
1/1

고정 길이 스택

LIFO(Last in First Out,후입선출) 방식

push:데이터 넣기
pop:데이터 꺼내기
top:윗 부분.push,pop 일어남
bottom:아랫 부분

스택 배열:stk,list형 배열
index 0 -> bottom
스택 크기:capacity,int형 정수,len(stk)와 일치
스택 포인터:ptr,스택 데이터 개수 나타내는 정숫값
비어 있으면 0,가득 차 있으면 capacity

스택에 쓰이는 함수

Empty():예외 처리 클래스,pop이나 peek 호출할 떄 스택 비어있으면 실행
Full(): "" 스택 가득 차있으면 실행
__init__:초기화 함수,전달받은 매개변수 capacity 값으로 stk 생성,
ptr 0으로 초기화


push(): 스택에 데이터를 추가,꽉 차면 Full()을 통해 예외 처리를 내보냄.
pop(): 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환, 비었을 경우 Empty()를 통하여 예외 처리를 내보냄.
* peek에서 ptr -= 1하면 안돼요!!

이게 처음에 "왜 삭제를 안 하지?" 했는데 pop하면 ptr이 -1되는데 어차피 다음에 push하면 새로운 value가 들어가기 때문에 사실상 빈칸인 것이다.마찬가지로 ptr이 0이면 스택이 완전히 비었다고 할 수 있다.

find()함수:데이터를 검색,꼭대기 -> 바닥으로 선형 검색한다.
count()함수:스택에 쌓여 있는 데이터 개수 구함
contains()함수:데이터가 포함되어 있는지 판단

* 던더 함수(더블 언더스코어)는 특별한 함수이다.
__contains()는 값 in 인스턴스로 사용 가능
__len
()는 len(인스턴스)로 사용 가능

이제 프로그램에 적용해보자

profile
생각만 하면 망상, 만들면 개발자.

0개의 댓글