스택, 큐, 덱? 너 누군데?

자료구조의 일종, 각기 다른 방식으로 데이터를 저장하고 관리

 

스택

[정의]

 데이터를 차곡차곡 쌓는다는 의미인 스택은 top을 통해서만 접근이 가능하기 때문에 push와 pop 모두 top에서 이루어진다. 마지막에 추가된 데이터가 가장 먼저 제거되는 후입선출(後入先出) 구조를 따른다. 물론 프로그래밍 언어와 구현에 따라 서로 다른 자료형을 혼합하는 경우도 있을 수 있지만, 일반적으로는 동일한 자료형으로 구성된다. 그래야 안정성이 보장되기 때문이다.

 

[장점]

 스택은 리스트로 구현되어 있다. 각 요소가 배열의 끝에 추가되며, 필요할 때에만 메모리가 할당되어 메모리 사용이 효율적이다. 재귀 함수 호출 시에도 스택 특유의 후입선출 구조가 자연스러운 관리를 유도한다.

▲ 구현이 간단하고 메모리 사용이 효율적이다.

▲ 함수 호출 시 유용하다.

 

[단점]

 프로그램 실행을 위해 예약한 메모리 공간의 일부로, 고정된 크기를 가지기 때문에 제한된 저장 공간 내에서 경량적으로 사용하게 된다. 너무 많은 데이터를 스택에 저장하려 할 때 stack overflow가 발생하므로 주의해야 한다. 빠른 메모리 할당과 해제를 위해 top 데이터만 접근이 가능하다.

▼ 저장 공간이 제한적이다.

▼ 중간 데이터 접근이 불가능하다.

 

[활용]

 후입선출 메커니즘의 장점을 활용하여 가장 마지막 활동을 스택에 push 하고, 원할 때 push 된 마지막 작업을 pop 하여 이전 상태로 되돌릴 수 있게 된다.

▶ 웹 브라우저의 뒤로가기 기능

▶ Undo 기능

 

큐

[정의]

 스택과 달리 접근할 수 있는 방향이 양쪽이다. 삽입은 오직 rear을 통해 이루어지고 삭제는 오직 front를 통해 이루어진다. 가장 먼저 추가된  데이터가 가장 먼저 제거되는 선입선출(先入先出) 구조를 따른다.

 

[장점]

 먼저 들어온 데이터가 먼저 나가므로, 대기열 같은 상황에서 효과적인 자료구조이다.

▲ 대기열의 데이터 처리가 공정하다.

 

[단점]

 front와 rear를 통해서만 접근이 가능하므로, 중간 데이터 접근이 불가능하다. 삽입과 삭제가 양쪽 끝에서 일어나기 때문에, 특히 동적 메모리 할당이 빈번하게 발생할 경우 성능 저하가 더 두드러질 수 있다.

▼ 중간 데이터 접근이 불가능하다.

▼ 메모리 관리에 주의가 필요하다.

 

[활용]

 선입선출 메커니즘의 장점을 활용하여 각종 대기열 상황에서 순차적으로 관리하고 처리할 수 있다.

▶ 프린터 대기열

▶ 프로세스 스케줄링

 

덱

[정의]

 삽입과 삭제에 있어서 정해진 접근 방향 없는 큐라고 이해하면 쉽다. 덱이라는 이름도 Double Ended Queue을 줄인 것이다.

 

[장점]

 양쪽에서 데이터 접근이 가능하기 때문에 유연성이 높고, 스택과 큐의 기능을 동시에 제공한다.

▲ 스택과 큐 대비 유연성이 높다.

▲ 스택과 큐의 기능을 동시에 제공한다.

 

[단점]

 장점이 많은 만큼 구현이 복잡할 수 있으며, 고정 크기 배열 기반으로 구현 시 메모리 사용이 비효율적일 수 있다.

▼ 구현이 어렵다.

▼ 비효율적인 메모리 사용이 우려된다.

 

[활용]

 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있어, 슬라이딩 윈도우나 어떠한 이력 관리 상황에서 효율적으로 활용할 수 있다.

▶ 슬라이딩 윈도우 알고리즘

▶ 우선순위 관리 및 정렬 알고리즘