Stack and Queue 개념

---

Stack과 Queue 모두 선형 자료구조의 일종으로 Stack은 나중에 들어간 원소가 먼저나오며
차곡차곡 쌓이는 구조가 특징이고, Queue는 먼저 들어간 원소가 먼저 나오는 특징을 가지고 있다.

Stack

---

후입선출 (LIFO, Last-In-First-Out)

• 스택(stack)이란 쌓아 올린다는 것을 의미한다.

• 스택 자료구조는 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

• 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.

• 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다.

• 스택에서는 삽입 연산을 push, 삭제 연산을 pop이라고 한다.

스택 사용 사례

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

스택 특징

• top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
• top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다. 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.

Queue

---

선입선출 (FIFO, First in first out)

• Queue의 사전적 의미는 (무엇을 기다리는 사람, 자동차 등의)줄, 혹은 줄을 서서 기다리는 것을 의미

• 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 나뉘어서 이루어진다.

큐 특징

• 데이터 접근, 삽입, 삭제가 빠르다.
• 큐 역시 스택과 마찬가지로 중간에 위치한 데이터에 대한 접근이 불가능하다.

큐 사용 사례

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