08/30 CS공부 - 자료구조(스택, 큐)

1. 스택(Stack)

말 그대로 데이터를 쌓는 자료구조이다. 입력과 출력이 한방향으로 제한되며 후입선출구조를 따라 가장 나중에 들어온 것이 가장 먼저 나온다.
함수의 콜스택, 문자열 역순출력, 연산자 후위표기법 등을 이용할 때 사용된다.

push(삽입)과 pop(제거, 제거된 데이터를 return 함, 코틀린 기준)연산이 주를 이룬다. isEmpty, isFull 등을 이용해 스택의 상태를 검사한다. 이러한 연산을 처리하기 위해 SP(스택 포인터)를 사용한다.

단방향 접근만 허용되므로 중간의 원소를 꺼내기 위해서는 해당 원소 뒤의 모든 원소를 pop해야한다.
배열 기반의 Stack의 경우 배열의 단점인 고정크기를 계승한다. 링크드 리스트, 동적배열 사용을 통해 해결할 수 있다.

2. 큐(Queue)

입력과 출력을 각각 한쪽 끝(front, rear)으로 제한한다. 선입 선출구조로 가장 먼저 들어온 것이 가장 먼저 나온다.
작업 대기열, 버퍼, BFS(너비 우선탐색) 등에서 사용된다.

큐의 가장 첫원소를 front, 끝 원소를 rear라고 부르며 모든 원소는 rear를 통해 들어와 front를 통해 나간다.

enQueue(삽입, rear에서), deQueue(제거, front에서)를 통해 데이터를 추가/제거하며 isEmpty, isFull을 이용해 상태를 검사한다.
이를 위해 rear와 front에서 위치정보를 기억해야한다.

일반 큐에서는 빈 메모리가 남아있어도 rear가 끝에 도달했을 때 큐가 가득 차있는 것으로 판단할 수 있다. 이를 해결하기 위해 원형큐를 사용하며 공백, 포화 상태를 구분하기 위해 항상 자리 하나를 비워둔다.
배열로 구현된 큐 역시 고정크기를 계승하며 이를 개선하기 위해 링크드 리스트를 이용한다.