자료구조 이론 :) Stack이해하기

 

 

 

 

 

 

 

goal

Stack을 이해한다.

 

 

Stack 및 Queue 다시 정리

 

 

1] Stack

1. Stack 이해하기

Stack은 블럭 쌓기 이다.

 누군가 Stack에 대해서 묻는다면 한 문장으로 stack은 블럭 쌓기라고 이야기해주고 싶다.

현실 세계의 (예)로 이해하기

 현실에서 같은 모양의 4개의 블럭을 하나의 상자에 쌓는다고 가정한다.

쌓기를 시작하면 첫 번째 블럭, 두 번째 블럭, 세 번째 블럭, 네 번째 블럭으로 쌓이게 될 것이다.

반대로 이 블럭들을 빼면 가장 먼저 나오는 순서대로 네 번째 블럭, 세 번째 블럭, 두 번째 블럭, 첫 번째 블럭이 될 것이다.

이 개념 자체가 Stack이다.

Stack의 자료구조 관점

 자료구조 관점에서 Stack은 첫 번째 들어간 블럭이 가장 늦게 나온다는 것을 이유로

Last In First Out 자료구조라 하며 이것을 줄여서 LIFO 자료구조라고 명명했다.

 

 그래서 Stack 언제 사용하는데?

• 웹 브라우저 방문기록 저장
• 실행취소 (ctrl + z라 이해하자)
• 문자열을 역순으로 만들기
• 수식의 괄호 검사

 위와 같은 상황들에서 코드를 구현할 때 Stack을 채택한다면 효율적인 코드를 작성할 수 있다.

반대로 Stack에 적합하지 않은 상황도 있기 때문에 상황에 따른 자료구조를 채택해서 사용하는 것이 매우 중요하다.

2. Stack 구현 생각해보기

• 블럭은 데이터이다.
• Stack의 데이터가 쌓여 있을 때 가장 윗부분을 Top이라고 한다.
• Stack의 데이터가 쌓여 있을 때 가장 아랫부분을 Bottom이라고 한다.

 

동작	내용
push	데이터를 삽입한다. - push를 하면 데이터가 Top에 위치한다.
pop	데이터를 스택에서 삭제한다. (Top의 데이터가 삭제된다.) - pop을 하면 Top 데이터가 삭제된다.
empty	Stack이 비어있는 유무를 판단한다. - 비어있다면 true, 데이터가 존재한다면 false반환
clear	Stack의 데이터를 모두 삭제하고 초기화한다.
peek	Stack의 가장 위의 데이터를 추출한다. - 추출만 한다. - 데이터는 삭제되지 않는다.
size	Stack의 크기를 출력한다. - 크기란 데이터를 의미한다 (블럭이 쌓인 개수)
contains	Stack에 사용자가 입력한 값이 있는지 확인한다. - 있다면 true, 없으면 false 반환

Java의 Stack Type의 메소드(동작)을 기준으로 작성한 표이다.

python의 경우 push는 append로 Data가 삽입된다.
언어별 메소드 이름에 차이가 있을 뿐 동작을 이해하는 메커니즘은 같다.

- 자바로 Generic을 사용하여 Stack을 직접 구현할 생각인데 쓰면서 생각해보니 쉽지 않을 것 같다...