[알고리즘 개념] 스택/큐

 

스택

 

출처 : https://mygumi.tistory.com/357

그림을 보면 알 수 있듯, 스택은 LIFO(Last In Frist Out) 후입 선출 구조이다. 

즉, 밑이 막힌 구조로 마지막으로 넣은 것이 먼저 나온다는 것이다.

쉽게 생각하면 쌓아 올린 접시를 생각하면 된다.

 

실생활에서는 컴퓨터의 뒤로 가기 기능이 스택을 이용하여 구현되었다.

페이지 뒤로 가기, 실행 취소 (Ctrl + Z)와 같은 기능은 스택의 대표 예제이다.

 

데이터를 삽입할 때는 push 데이터를 삭제할 때는 pop이라는 용어를 사용한다.

스택에서는 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 사용하여 구현하게 된다.

 

스택 구현은 배열과 연결 리스트를 통해 구현할 수 있다.

배열의 장점은 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다는 것이다.

하지만, 배열의 크기가 정해져 있기 있고, 삽입과 삭제 연산에 비효율적이라는 단점이 있다.

 

배열로 구현한 스택의 단점

 

반면, 연결 리스트로 구현한 스택은 데이터의 최대 개수가 한정되어 있지 않고, 

데이터의 삽입, 삭제가 용이하다는 장점이 있다.

다만, 연결 리스트는 노드가 순차적으로 나열되어 있기 때문에

배열처럼 한 번에 원하는 데이터에 접근할 수 없다는 단점을 가지고 있다.

 

이처럼 두 구현 방법의 장단점이 있다.

배열은 삽입, 삭제가 거의 없고 데이터의 접근이 많을 때 유리하고, 

연결 리스트는 삽입 삭제가 빈번히 일어나는 경우에 유리하다.

따라서 상황에 맞게 배열과 연결 리스트를 선택하는 것이 좋다.

 

 

 

큐

 

출처 : https://mygumi.tistory.com/357

큐는 스택과 반대 개념이라고 생각하면 된다.

그림에서도 볼 수 있든 먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 선입선출 구조이다.

쉽게 생각하면, 계산대에 줄 서 있는 모습과 같다.

 

실생활에서 주로 순서를 보장하기 위한 처리에서 큐가 사용된다.

CPU 처리가 대표 예라고 할 수 있다.

 

큐에서 데이터를 삽입할 때는 Enqueue 삭제할 때는 Dequeue라는 용어를 사용한다.

큐에서는 마지막 노드를 가리키는 rear라는 변수를 사용하게 된다.

 

큐도 스택과 마찬가지로 배열과 연결 리스트를 이용하여 구현할 수 있다.

배열과 연결 리스트의 장단점은 위의 설명과 같다.

 

배열로 구현한 큐는 데이터의 최대 개수가 제한되어있다는 단점이 있고,

또한 연결 리스트와는 반대로 삭제 과정에서 비효율적인 작업이 생긴다.

바로 데이터를 계속 앞으로 이동해 주어야 한다는 것이다. 

 

만약 데이터를 앞으로 이동해 주지 않는다면, 큐의 앞부분은 비어있지만 마지막 부분에 데이터가 들어가 있어

큐가 가득 차지 않았음에도 가득 찬 것처럼 인식하는 경우가 생긴다. (rear가 마지막 인덱스를 가리키는 경우)

 

이를 보완하기 위해 등장한 것이 원형 큐이다.

 

 

 

데이터 추가 시 선형 큐와 마찬가지로 rear가 한 칸 움직이는 것은 동일하나

rear값을 (rear+1)%(일차원 배열의 크기)로 설정하여 마지막 인덱스의 개념이 없는 것처럼 하는 것이다.

 

즉 원형 큐는 개념 적으로는 원형 배열이지만 구현은 일차원 배열을 사용하는 것이다.