<자료구조 알고리즘> 스택

스택이란?

배열처럼 선형 구조의 자료구조(뭔가 한 줄이라는 느낌)이며 한 쪽 끝에서만 제한적으로 접근할 수 있는 LIFO( last in first out) 구조의 자료구조이다. 

이름 그대로 데이터를 쌓는 자료구조이다.

자 차근차근 알아보도록 하자.

1. 하노이 탑

스택을 알아보자면서 갑자기 웬 하노이 탑이 나오냐고? 

일단 아래 사진처럼 하노이 탑의 기둥 하나만 떠올려 보자.

하노이탑은 기둥에 원판을 이동하는 퍼즐이다. (원판 크기는 스택이랑 관련 없으니 생각하지 말자)

이 기둥에 원판을 꽂는 것과 스택의 구조가 굉장히 비슷하다.

하노이탑에 원판을 꽂을 때에는 밑에서 꽂을 수도 없고 중간에 넣을 수도 없다. 무조건 위에 꽂아야 한다.

또한 빼낼 때에는 항상 맨 위에 있는 원판만 빼낼 수 있다. (위에 것을 빼내지 않으면 가운데 원판을 빼내지 못한다.)

원판 6개를 모두 꽂았다가 빼보자.

위를 보면 가장 먼저 꽂았던 가장 긴 원판이 가장 나중에 빠지는 것을 알 수 있다. 이러한 구조를  last in first out을 줄여 LIFO 라고 한다. 우리말로 하면 후입선출이라고 하면 되려나. 

 

2.스택

그러면 이제 본격적으로 스택을 알아보자. 스택은 아래와 같이 생겼다. 

하노이탑의 원판이 스택에 저장할 데이터, 기둥이 스택이라고 생각하면 된다. 

 

스택은  원판을 위에 꽂았던 것처럼 맨 위에 데이터 추가(stack.push()), 맨 위 원판을 제거할 수 있었던 것처럼 맨 위에 데이터 삭제(stack.pop()) 그리고 맨 위 데이터에 접근(stack.top())이 가능하다.

 

※ 배열과 같이 i번째 값에 바로 접근 하는 것이 안되고 하노이 탑처럼 위에서 3번째 값을 알고 싶으면 위에 있는 모든 데이터를 꺼내야 한다. 

 

3.구현

동적 배열을 이용해서도 구현을 할 수 있기는 하지만 중간에 있는 데이터에 접근하지는 않을 것이고 끝에 추가 삭제를 많이 할 테니 연결 리스트를 사용하는 것이 더 효율적일 것이다. 

구현은 다음 글에서.....