자료구조(2) : 스택(Stack)과 큐(Queue)

이전에 말한 자료구조란 데이터를 효율적으로 다루기 위한 규칙이라고 배웠습니다. 이번에는 자료구조에서 많이 사용되는 스택(Stack)과 큐(Queue)에 대해 알아봅시다. 스택과 큐는 둘 다 리스트 자료구조의 특별한 경우로, 순서대로 구성된 선형 구조를 가지고 있습니다.

 

---

 

스택(Stack)

웹 브라우저의 뒤로 가기 버튼을 생각해 봅시다. 한 번에 한 페이지밖에 이동하지 못하고, 가장 마지막으로 누른 페이지로 바로 이동할 수 있습니다. 여기에 사용되는 스택은 자료 구조를 순서대로 쌓은 모양입니다. 컵처럼 데이터를 넣고 빼는 구멍이 하나이며, 가장 위쪽에서 데이터를 넣고 뺄 수 있습니다.

• 후입선출(LIFO : Last In First Out) : 나중에 들어간 데이터가 먼저 나옵니다.
  또는 선입후출 (FILO : First In Last Out) : 먼저 들어간 데이터는 나중에 나옵니다.
• 스택에 데이터를 넣는 것을 Push, 꺼내는 것을 Pop이라고 합니다.
• 스택에서 Top은 최상단을 가리키는 인덱스입니다. 즉, 데이터의 삽입과 삭제는 Top에서만 이루어집니다.

스택의 특징

1. 선입후출이라는 구성 덕에 Top이라는 최상위 블록만 확인하면 됩니다. 때문에 데이터를 저장하고 검색하는 프로세스가 매우 빠릅니다.
2. 데이터는 하나씩 넣고 뺄 수 있습니다.
3. 하나의 입출력 방향을 가지는 제한적 접근 형태입니다.
4. 저장되는 데이터는 유한하고 정적입니다.
5. 스택의 크기는 제한되어 있습니다. 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 됩니다. 반대로 스택이 비어있을 때 자료를 꺼내려고 시도를 하면스택 언더플로우(Stack Underflow)가 발생합니다.

 

---

 

큐(Queue)

프린터로 문서를 출력하는 걸 생각해 봅시다. 클릭 한 번으로 문서 데이터는 빠르게 전송되지만, 프린터는 하나씩 인쇄하느라 문서를 대기열에 저장합니다. 데이터를 넘긴 순서대로 문서가 출력되고요. 이렇듯 큐는 데이터를 순서대로 처리할 때 사용합니다.

큐는 고속도로 톨게이트로도 비교됩니다. 앞쪽으로 데이터를 빼고 뒤쪽에서 데이터가 들어오는 두 개의 구멍이 있습니다. 앞쪽에 있는 데이터(가장 먼저 넣은 데이터)부터 순서대로 빼는 구조입니다.

• 선입선출(FIFO : First In First Out) : 먼저 들어간 데이터가 먼저 나옵니다.
  또는 후입후출(LILO : Last In Last Out) : 나중에 들어간 데이터는 나중에 나옵니다.
• 큐에 데이터를 넣는 것을 Enqueue, 꺼내는 것을 Dequeue라고 합니다.
• 삭제되는 데이터(가장 먼저 넣은 데이터)는 Front에, 삽입되는 데이터(가장 나중에 넣은 데이터) Rear에 위치합니다.

큐의 특징

1. 선입선출의 구조 덕에 데이터가 입력된 순서대로 연산을 처리할 때 사용됩니다.
2. 스택처럼 데이터는 하나씩 넣고 뺄 수 있습니다.
3. 두 개의 입출력 방향을 가지며 데이터의 입력과 출력 방향이 다릅니다.

 

---

 

참고 사이트

알고리즘 - 큐(Queue) : 선형 큐와 원형 큐

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

[Data Structure] 스택(Stack)과 큐(Queue) 개념, 특징, 활용 예시