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

stack(스택)이란?

• 스택이란 쌓다 라는 의미로 스택 자료구조란 책처럼 차곡차곡 쌓아 올린 형태의 자료 구조를 의미한다.
• 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.
• 스택은 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근 가능하다.
• 새로 삽입된 자료는 top이 가리키는 가장 맨 위에 쌓이게 되고, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.
• 스택에서 삽입 연산을 push, 삭제 연산을 pop이라고 하며, 이러한 스택의 구조를 후입선출 구조라고 하며, LIFO(Last In First Out) 라고 부른다.
  예로 들면 책상에 책을 쌓아두는 것이랑 포개둔 일회용 종이컵을 하나씩 꺼내서 사용하는것을 말할수 있다.

스택의 사용 사례

• 웹 브라우저 방문 기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 후위 표기법 계산

---

Queue(큐)란?

• 큐는 제일 먼저 들어온 것이 나가는 구조로 되어있으며, 이러한 큐의 구조를 선입선출 구조라고 하며, FIFO(First In First Out) 라고 부른다.
• 삭제 연산이 수행되는 곳을 프론트(front)라고 하며, 삽입 연산이 수행되는 곳은 리어(rear)라고 한다.
• 선입선출 구조를 위해서 스택과는 다르게 한쪽에서는 삽입 작업이 반대쪽에서는 삭제 작업이 이루어 지고 있다.
• 큐에서 리어에서 진행되는 삽입 연산을 인큐(Enqueue)라고 하며, 프론트에서 진행되는 삭제 연산을 디큐(Dequeue)라고 한다.
  예로 들면 카페에서 먼저 와서 주문한 손님이 음료를 먼저 받고 나가는것을 말할수있다.

큐의 사용 사례

• 은행 업무
• 대기열 순서와 같이 우선 순위의 작업 예약 등
• 서비스 센터의 대기 시간
• 프로세스 관리

---

Reference
Blog
Blog