[자료구조] Stack, Queue

Stack

---

Stack의 정의

• 데이터를 순서대로 쌓는 구조

  

• 연결리스트로 구현하는 경우

  

특징

• 입출력이 하나의 방향으로 이루어지는 제한적 접근

• 후입 선출, 선입 후출의 구조

• 데이터는 하나씩만 넣고 뺄 수 있음

• FILO (First In Last Out)

  • 가장 먼저 들어간 데이터는 가장 나중에 나오는 구조

• LIFO (Last In First Out)

  • 가장 나중에 들어간 데이터가 가장 먼저 나오는 구조

스택의 사용 사례

• 웹 브라우저 방문 기록(뒤로가기)

• 실행 취소 (undo)

• 역순 문자열 만들기

• 후위 표기법 계산

Queue

---

Queue의 정의

• Queue는 Stack과 달리 먼저 들어온 것이 먼저 나가는 선입선출 (FIFO)과 후입후출 (LILO)의 구조

  

특징

• FIFO(First In First Out)

• 데이터는 하나씩만 넣고 뺄 수 있음

• 두 개의 입출력 방향

큐의 사용 사례

• 우선 순위 작업 예약

• 은행 업무

• 프로세스 관리

• 프린터 인쇄

CPU와 컴퓨터 장치 사이의 데이터 통신

• CPU는 대부분의 장치보다 데이터 처리가 빠름

• CPU는 프린터보다 데이터 처리가 빨라 인쇄에 필요한 데이터를 만든 후 인쇄 작업 Queue에 저장하고 다른 작업을 수행

• 프린터는 인쇄 작업 Queue에서 데이터를 받아 일정한 속도로 인쇄를 진행

• 동영상을 시청하는 경우에도 정상적인 재생을 위해 Queue에 데이터를 저장해두었다가 충분한 양의 데이터가 모이면 재생

  • 데이터가 충분하지 않아 재생하지 못하고 기다리는 과정을 버퍼링이라고 함

원형 큐

---

• 선형 Queue의 front와 rear값이 계속 증가하기만 한다는 문제점을 극복한 구조

• front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록 함

• 공백 상태는 front == rear인 상태, 포화상태는 front == (rear + 1) % MAX_QUEUE_SIZE의 값으로 판단

• 모듈러 % 연산을 통해 rear의 값을 0번 자리로 변경시켜줌