이번에는 스택 ADT를 살펴볼 것입니다.
스택은 간단히 말해서 "후입 선출" 즉, 나중에 들어온 것이 제일 첨 나간다.
예시를 들자면, 쌓여있는 책중에서 우리가 고르는 것은 제일 위에 있는(제일 나중에 들어온) 책을 고르게 됩니다.
또는 웹브라우저의 방문기록도 이러한 스택의 구조를 가지고 있습니다.
이러한 스택 ADT의 메쏘드를 살펴봅시다.
주로
push(e) : 원소를 삽입
pop() : 가장 최근에 삽입된 원소를 삭제하여 반환
이 두개의 함수가 쓰이게 되고 이외에는
top() : 가장 최근에 삽입된 원소를 삭제하지 않고 반환
isEmpty() : 비어 있는지 여부를 반환
이러한 메쏘드들도 사용됩니다.
이런 스택을 응용하게 되면
직접 응용
1. 웹브라우저에서 방문한 웹페이지들의 기록
2. 문서편집기에서 되돌리기 기록
3. 재귀의 구현
간접 응용
1. 보조 데이터 구조
이러한 작업들을 할 수 있게 됩니다.
그리고 실제로 구현할 때 우리는 배열이나 연결 리스트를 통해서 스택 ADT를 구현할 수 있게 됩니다.
먼저 배열로 만드는 경우를 살펴봅시다.
배열로 스택을 구현하게 된다면
1. 크기 N의 배열을 사용해야 하고
2. 원소들을 배열의 왼쪽에서 오른쪽으로 추가해야 합니다.
3. 변수 t를 사용해 top원소의 index를 관리할 수 있습니다.
그리고 연결 리스트로 스택을 구현하게 된다면
1. 단일 연결 리스트를 사용해 스택을 구현할 수 있습니다.
2. top원소를 연결 리스트의 첫 노드에 저장하고 이곳을 t포인터로 가리키게 합니다.
3. 기억 장소 사용 : O(n)
4. 스택 ADT의 각 작업 : O(1)
그리고 실제 함수들을 c언어로 구현해 보았습니다.
배열 스택
결과 화면
연결 리스트 스택
결과 화면도 비슷하게 나옵니다.
여기까지 스택에 관한 이야기였습니다~
