큐, 스택이란?

자료구조

1) 큐

• 큐는 컴퓨터 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO 구조로 저장하는 형식을 말한다
• 영어단어로 QUEUE는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈수있다.
• 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
• 프린터의 출력 처리나, 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 순서대로 처리해야할 필요가 있는 상황에 이용된다.

큐의 종류

• 원형큐 : 큐를 위해 배열을 지정해 놓고, 큐를 쓰다보니 배열의 앞부분이 비게된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐입니다.
• 우선순위큐 : 우선순위 큐는 말 그대로 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼내는 것입니다.
• 데크 : 일반적인 큐는 뒤에서만 삽입이 이루어지고, 앞에서만 자료를 꺼내올 수 있지만, 데크는 양쪽에서 모두 삽입/인출이 가능하다.

큐의 용도

• 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.
• 서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용된다.

2) 스택

• 후입선출 구조(LIFO)의 자료구조, 스택은 일종의 바닥이 막힌 상자라고 보면 된다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수 있다.

스택의 특징

• 스택에서 데이터를 확인하려면 가장 위의 데이터부터 확인해야 한다.
• 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 있다.
• 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.

스택의 용도

• 재귀알고리즘
• 웹브라우저 방문기록(뒤로가기)
• 실행취소