#자료구조_02_스택, 큐, 데크

1. 스택(Stack)

데이터 구조의 하나로써 원소의 삽입과 삭제가 한쪽 끝에서만 일어나는 선형 리스트이다. 원소들의 삽입, 삭제가 일어나는 부분을 top라고 하며, 원소를 스택에 넣는 것을 push, 스택에서 원소를 꺼내는 것을 pop이라고 한다. 스택에서는 나중에 들어간 원소가 먼저 꺼내어지므로 후입선출(LIFO, Last-In, First Out)이라고 한다.

 

스택은 주로 어떤 내용을 기억시켰다가 다시 이용하고자 할 때 사용되며 컴퓨터 알고리즘에 자주 쓰이는 데이터 구조이다. 스택의 활용 예로써, 운영체제에서 인터럽트가 발생한 경우에 복귀 주소의 저장이나 산술 계산에 사용된다.

 

2. 큐(Queue)

데이터 구조의 하나로써 큐도 여러 데이터 항목을 일정한 순서로 입출력하기 위한 선형 데이터구조로써, 선형 리스트의 한쪽 끝에서는 삽입 동작만, 반대쪽에서는 삭제 동작만 이루어진다.

 

큐에는 한 방향으로 데이터 항목들이 삽입/삭제되는 선형 큐와 시작점과 끝점이 서로 연결되어 있는 환형 큐가 있다. 먼저 입력되는 데이터를 먼저 삭제하므로 선입선출(FIFO, First in First out)이라고 한다.

 

큐는 rear, front 노드를 이용하여 삽입, 삭제를 구현한다.

 

큐의 활용 예로써 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다

• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (은행 카운터)
• 프린터의 출력 처리

 

3. 데크(Deque : Double-ended queue)

 

데크는 스택과 큐를 혼합한 상태이며 비슷한 동작으로 양쪽 끝 모두에서 삽입과 삭제가 일어나도록 설계 된 데이터 구조이다. 스택의 한쪽 끝에서 삽입과 삭제가 동시에 일어날 경우 그 위치(주소)를 알려주는 포인터가 1개 필요하였듯이 데크에서는 2개의 포인터가 필요하다. 데크는 선형구조이므로 배열을 이용할 수 있다.