[자료구조] 스택(Stack)과 큐(Queue)

스택 (Stack) 이란?

스택(Stack)은 쌓아 올린다는 것을 의미한다.

따라서, 스택(Stack)은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 의미한다.

즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조이다.

 

스택의 특징

스택은 시간 순서에 따라 데이터가 쌓이게 되므로, 

가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다.

• 위의 그림과 같이 아래에서 위로 쌓이는 형식이다.
• 가장 최근(마지막)에 들어온 자료를 top이라고 부른다.
• 스택 내부의 데이터는, top 을 통해서만 접근할 수 있다.
  • 삽입과 삭제는 한 곳(top)에서만 이루어지게 된다.
  • 가장 위쪽(최신)의 데이터부터 꺼낼 수 있다.
  • 후입선출(LIFO, Last In First Out)의 구조

 

• 데이터를 삽입할 때, top 위에 쌓게 된다. ('push' 연산)
• 데이터를 삭제할 때, top 에 위치한 데이터를 삭제하게 된다. ('pop' 연산)

 

• 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow) 발생
• 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow) 발생

 

스택의 활용 예시

1. 웹 브라우저 방문기록 (뒤로 가기)
   • 가장 마지막에 열린 페이지부터 다시 보여준다.
2. 실행 취소 (undo)
   • 가장 마지막에 실행된 것부터 실행을 취소한다.
3. 역순 문자열 만들기
   
   • 가장 마지막에 입력된 문자부터 출력한다.
4. 후위 표기법 계산
5. 수식의 괄호 검사
   • 연산자 우선순위 표현을 위한 괄호 검사

 

큐 (Queue) 란?

큐(Queue) 는 "줄을 서서 기다린다."라는 사전적 의미를 가지고 있다.

따라서, 큐 (Queue) 는 먼저 들어온게 먼저 나가는 선입선출(FIFO, First In FirstOut) 방식의 자료구조이다.

 

 

큐의 특징

스택은 정해진 곳(top) 에서만 삽입, 삭제가 이루어졌었다.

• 큐는 삽입, 삭제가 다른 방향에서 이루어진다.
• 삭제 연산만 수행되는 곳을 프론트(front) 라고 한다.
  • 프론트(front)에서 이루어지는 삭제 연산을 디큐(dnQueue) 라고 한다.

• 삽입 연산만 수행되는 곳을 리어(rear) 라고 한다.
  
  • 리어(rear)에서 이루어지는 삽입 연산을 인큐(enQueue) 라고 한다.

• 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.
  • 선입선출(FIFO, First In FirstOut) 구조

 

큐의 활용 예시

큐는 주로, 데이터가 입력된 순서에 따라 처리되어야 할 때 사용된다.

 

1. 일상생활에서, 줄을 서서 기다려야하는 모든 행동에 사용
   • 은행 업무 : 빠른 번호표를 가진 사람이 먼저 업무를 본다.
   • 콜센터 고객 대기시간
   • 놀이동산
   • 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력된다.
2. 프로세스 관리
3. 너비 우선 탐색(BFS, Breadth-First Search) 구현
4. 캐시(Cache) 구현

---

 

참고 자료

https://cocoon1787.tistory.com/691

https://wooono.tistory.com/395