스택 & 큐

✅ 스택

• 마지막에 들어온 것이 먼저 나가는 후입 선출 LIFO(Last In First Out) 구조를 가진 자료 구조

출처 http://www.incodom.kr/%EC%8A%A4%ED%83%9D

• 가장 먼저 입력된 데이터가 가장 아래쪽에 위치하며 나중에 입력된 데이터는 그 위에 쌓임

• 함수 호출이 끝나고 이전 함수로 돌갈 때 등 컴퓨터는 내부적으로 스택을 사용하여 관리

⚡ 작업

1 pop() - 자료를 꺼내는 작업
2 push() - 자료를 넣는 작업
3 peek() - 맨 위의 자료를 보는 방법

✅ 큐

• 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있음

• 가장 먼저 들어간 자료를 가장 먼저 꺼낼 수 있는 선입 선출(FIFO, First In First Out) 구조를 가진 자료 구조

⚡ 작업

1 enqueue() - 맨 뒤에 자료를 넣는 작업
2 dequeue() - 맨 앞의 자료를 꺼내는 작업
3 peek() - 맨 앞의 자료를 보는 작업

▶ 선형 큐

출처 https://velog.io/@suitepotato/00004

• front는 제일 처음 인덱스를 가리키고 rear는 제일 마지막 인덱스를 가리킴

• 선형 큐의 문제점은 rear 인덱스에 data가 들어가 있을 경우, 앞의 인덱스에 data가 비어있어도 포화 상태로 인식

• 처음은 front와 rear가 0이고, enqueue일 경우 rear는 인덱스가 증가하며 dequeue일 경우 front의 인덱스가 증가

▶ 원형 큐

출처 https://colomy.tistory.com/64

• 처음 상태는 front와 rear모두 0을 가리킴

• 큐가 비어있는 상태 : front == rear

• 큐가 포화인 상태 : front == (rear+1) % size

• front에는 data가 들어가지 않는데, 이유는 포화 상태를 계산하기 위해서임