💭 Stack & Queue (스택 & 큐)

🙄 스택과 큐란 뭘까?

스택

LIFO(Last In First Out) 구조  :  맨 마지막에 추가한 데이터가 가장 먼저 꺼내지는 구조

이 구조를 사용해 역순 문자열을 만들거나 수식의 후위 표기법 변환 등의 작업에 사용할 수 있음

 

스택에서 데이터를 추가할 때는 push()를 사용하고, 꺼낼때는 pop()을 사용

스택의 예시로는 시스템 스택이 있음

시스템 스택은 함수 호출과 복귀 순서를 스택의 구조를 응용해 관리

 

큐

FIFO(First In First Out) 구조 : 큐는 스택과 반대로 가장 먼저 추가한 데이터가 가장 먼저 꺼내지는 구조

우선순위가 같은 작업 예약이나 선입 선출이 필요한 대기열 등에서 사용될 수 있음

 

선형 큐(Linear Queue)는 배열을 이용하여 구현되며, 새로운 데이터를 추가하면 rear(rear-end)가 가리키는 위치가 한 칸 이동하고, 데이터를 제거하면 front(front-end)가 가리키는 위치가 한 칸 이동함.

그러나 큐에서 데이터를 제거하면 데이터가 저장되었던 공간은 재사용되지 않음.

즉, 데이터를 꺼내서 사용하던 공간은 그대로 남아있게 되어, 메모리가 낭비됨

 

이러한 문제점을 보완하기 위해, 원형 큐(Circular Queue) 등장!

원형 큐는 배열의 처음과 끝이 서로 이어져 있는 구조

선형 큐에서 rear와 front가 끝까지 이동한 후에는 더 이상 데이터를 추가할 수 없는데, 원형 큐는 끝까지 이동하면 다시 배열의 처음으로 돌아가서 데이터를 추가할 수 있음

이렇게 구현하면, 배열의 처음과 끝이 이어져 있기 때문에 메모리 공간을 효율적으로 사용할 수 있다!