[자료구조 이론] 스택(Stack) 이해하기

 스택은 나중에 들어가것이 먼저 나오는 구조이기 때문에 '후입선출'방식의 자료구조 라고 하며, 영어로는 LIFO(Last in First out) 형식의 자료구조라고도 불림.

 

한쪽 끝에서만 자료를 넣고 뺄 수 있다.

 

- 스택의 연산

스택의 자료구조 사용법

시작하기전 마지막 데이터가 스택에 어느 위치에 잇는지 기억하기 위해 top이라는 변수를 만든다. 삽일을 한다면 top +1이 됩니다. 

 

1) pop:  스택에서 가장 위에 있는 항목을 제거 한다. 스택은 LIFO라고 했으니까 가장 최근에 추가한 항목이 가장 먼저 제거될 항목이다. pop을 하기 된다면 top의 위치는 -1

2) push: 데이터 하나를 스택의 가장 윗 부분에 추가한다.  top +1

3) peek: 스택의 가장 위에 있는 항목을 반환한다. 마지막 위치(top)에 해당하는 데이터를 읽어준다. 이때 top의 변화는 ? 없습니다.

4) isEmpty: 스택이 비어 있을 때에 true를 반환한다.

 

 

 

- 스택 구현

 

스택의 구현방법은 배열 기반 구현과 연결리스트 기반 구현 두가지가 있다.

 

 배열기반 구현은 부담스럽지 않다. 구현이 쉽고 원하는 데이터의 접근 속도가 빠르다. 내가 찾는 데이터가 배열의 5번째에 있다면 array[4]를 사용한다면 한번에 접근이 가능하다. 그러나 데이터의 최대개수를 미리 정해야한다는 단점이 있다. 그리고 push, pop을 사용할때 매우 비효율 적이다. 만약 1.000.000 개의 데이터가 있는데 첫번째 위치의 데이터를 삽입하려면, 그 뒤에 있는 모든 데이터(1.000.000)를 한칸씩 옮겨야 한다. 

 

 연결리스트 구현은 데이터의 최대개수가 한정되어 있지 않고, 데이터의 삽입 삭제가 용이하다. 연결리스트의 구조는 배열과 다르게 데이터들이 순차적으로 나열 되어 있지 않다. 연결리스트 중간에 데이터를 삽입하고 싶다면. 연결을 끊고 다음위치에 해당하는 노드이 주소값만 바꿔주면 된다. 그러나 단점이 있다면 배엵과 다르게 한번에 원하는 데이터의 접근이 불가능하다. 연결되어 있는 링크를 따라 차근차근 하나씩 확인 하며 데이터를 찾아야 하기 때문이다.