<자료구조> 스택과 큐(1)

 

1.  스택이란

* 스택

 - 데이터를 임시 저장할 때 사용하는 자료구조이다. 후입선출 방식의 입출력 순서를 가진다.

 - 푸시(Push) : 스택에 데이터를 쌓아 넣는 일

 - 팝(Pop) : 스택에서 데이터를 꺼내는 일

 - 데이터는 겹겹이 쌓이는 방식으로 푸시하면 top에 쌓이고 pop하면 top에서부터 꺼낸다.

 

 

2. 스택의 구현

- 스택을 구현하기 위해 크기가 결정된 고정길이 스택을 클래스를 이용하여 만드려면 어떤 요소들이 필요할까.

 

* 스택 구현

 - 스택을 구현하기 위해서는 다음과 같은 요소들이 필요하다.

 

 - 스택 배열 : 푸시한 데이터를 list형 배열에 저장하도록 하면 첫번째 푸시한 데이터는 list[0]에 저장된다.

 - 스택포인터 : 스택에 쌓여있는 데이터의 갯수이다. 가장 마지막에 푸시한 데이터는 list[포인터-1] 이 된다.

 

 - 예외처리 클래스 : 데이터를 pop하거나 볼 때 스택이 비어있으면 실행할 예외처리가 필요하다. 그리고 push할 때 스택이 가득 차 있으면 실행할 예외처리도 필요하다.

 

 - 초기화 함수 : 스택배열을 생성하는 일을 한다. 매개변수 capacity로 받은 값을 스택의 크기로 해야하므로 그 갯수만큼 원소를 None으로 리스트로 생성하면 된다. 물론 이 때 스택포인터는 0이다.

 - 데이터 개수 : 데이터 개수를 반환해주는 함수도 있어야 할 것이다. 이는 스택포인터 값을 반환하면 된다.

 - 판단함수 : 스택이 비어있는지를 판단하는 함수와 가득 차 있는지를 판단하는 각각 True와 False를 반환하는 함수가 있으면 좋을 것이다.

 

 - 푸시함수 : 스택에 데이터를 추가하고 스택포인터를 1씩 증가시키는 함수이다. 만약 스택이 가득차있다면 위에서 만든 예외처리 클래스를 이용한다.

 - 팝함수 : top의 데이터를 꺼내고 스택포인터를 1씩 감소시키는 함수이다. 이 또한 스택이 비어 있으면 예외처리 클래스를 사용하도록 처리 한다.

 

 - 피크함수 : top에 있는 데이터, 즉 다음에 팝하게 될 데이터를 보는 함수이다. 리스트[포인터-1] 을 반환하면 될 것이다.

 - 삭제함수 : 스택을 clear하는 함수도 필요하다. 포인터 값도 0으로 만들어 줘야 한다.

 

 - 검색함수 : 선형 검색을 통해 찾으려는 값이 배열에 있는지 검색한다.

 - 카운트함수 : 데이터 갯수를 세는 함수이다.

 

 - 그 외 함수 : 데이터가 포함되어있는지 판단만하는 함수를 멤버십 판단 연산자인 in을 사용하여 만들 수 있다. 그리고 모든 데이터를 리스트로 출력해주는 함수도 만들 수 있다. 즉 우리가 만든 스택을 통째로 보여주는 함수이다.

 

 

 

 

 

 

---

 

 

참고

 

 

이 글은 ‘이지스퍼블리싱’의 ‘자료구조와 함께 배우는 알고리즘 입문’을 공부 후 정리하며 쓴 글입니다.

작성된 모든 내용과 코드는 교재 및 관련 사이트를 참고하여 직접 재구성하였습니다.

 

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편

http://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

이지스퍼블리싱 스터디룸 카페

Do it! 스터디룸 : 네이버 카페

 

교재 공식 깃허브

easysIT/doit_dsalgo_with_python