[자료구조] 스택(Stack)

스택이란?

스택은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다.

스택은 입구와 출구가 같은 선형 구조이다. 

따라서 가장 먼저 입구에 들어간 자료가 가장 늦게 출구로 나갈 수 있다. 

프링글스 통을 생각하면 이해가 쉽다.

처음 프링글스 통이 채워질 때 가장 먼저 들어간 프링글스가 가장 마지막에 우리들의 손에 집혀 입으로 들어온다.

이를 후입 선출(또는 LIFO, last in first out) 구조라고 한다.

스택에서의 접근은 항상 마지막 원소에서만 일어난다. =>  제일 위에 있는 프링글스를 잡는다. 

이 마지막 원소를 top이라고 한다.

 

스택의 탐색

앞서 포스팅한 배열과 연결 리스트가 자료구조를 구현하는 기본적인 방법이다.

보통 스택의 탐색을 top함수라고 한다.

배열로 구현했을 때 아주 간단하다.

배열 사이즈 - 1의 인덱스의 값을 리턴해주면 된다.

 

 

연결 리스트로 스택을 구현했을 때는 두 가지를 선택할 수 있다.

1. head를 top으로 하는 방법.

2. tail을 top으로 하는 방법.

 

1번 방법은 연결 리스트에서 바로 접근 가능한 head노드가 저장하고 있는 값을 리턴하면 되지만,

2번 방법은 tail노드까지 이동한 다음 tail노드가 저장하고 있는 값을 리턴해야 하기 때문에 비효율적이다.

 

 

스택의 삽입

스택의 삽입 연산은 스택으로 데이터를 밀어 넣는다는 느낌으로 push라고 보통 칭한다.

배열로 구현했을 땐 항상 간단하다.

스택의 크기를 나타내는 size번째 인덱스에 삽입될 원소 x를 지정하고 size를 증가시켜주면 끝이다.

연결 리스트로 구현했을 때는 약간 더 복잡하다.

먼저 삽입될 노드 newNode를 생성해주고 그 노드의 값을 x로 설정한다.

이 또한 head노드를 top으로 하는 것이 효율적이므로 기존의 head노드 앞에 새로운 노드가 삽입되는 것이다.

따라서 newNode의 next가 지정하는 노드를 기존의 top으로 해준 다음 top을 newNode로 바꿔준다.

그리고 크기를 나타내는 size를 증가시키면 끝이다.

스택의 삭제

 

 

스택의 삭제 연산은 보통 pop이라고 한다. top연산과 헷갈리지 않도록 한다.

배열로 구현했을 때는 size를 줄여주기만 하면 끝이다.

왜냐하면 인덱스를 통해 접근할 수 있는 범위가 size까지이기 때문에 별도의 삭제 없이 size만 줄여주면 삭제된 것처럼 된다.

이후 push연산 시 기존에 있던 값(삭제됨)을 덮어 씌우기 때문에 아무런 이상이 없다.

 

연결 리스트로 구현했을 때는 기존의 top의 next가 가리키는 노드를 top으로 바꿔주면 된다..

이 역시 head를 top으로 했으니까 간단한 것이다.

만약 tail을 top으로 하면 반복문을 통해 tail 이전 노드까지 순회한 다음 그 노드를 tail로 설정해야 하기 때문에 비효율적이다.

 

이렇게 스택을 배열과 연결 리스트로 구현했을 때 각각의 탐색, 삽입, 삭제에 대해 알아봤다.