스택은 Last In First Out 으로, 요소가 들어올 때마다 기존 요소들에 차곡차곡 쌓아 올린 형태의 자료구조이며, 제일 마지막으로 들어온 요소 즉, Top 이 가르키는 요소에만 접근, POP을 할 수 있다.
비어있는 상태의 스택을 pop 할 때 stack underflow, 꽉 찬 스택에 push 할 때 stack overflow를 발생시킨다.
배열로 구현할 시에, top 인덱스를 활용하여 여러 메소드를 구현한다.
스택의 활용 예시
운영체제의 메모리 스택
웹 브라우저 방문기록의 뒤로가기
역순 문자열, 후위 표기법 계산, 수식의 괄호 검사 등
DFS ( 함수의 재귀, 메모리 스택을 활용 ), 미로찾기
2개로 큐 구현하기.
Queue
큐는 First In First Out 으로, 먼저 들어온 요소에만 접근하여 pop 되는 실생활의 대기줄과 같은 자료구조이며, 큐의 front에서 pop이 일어나고, 큐의 rear에서 push가 일어난다.
배열로 구현시 front, rear 인덱스를 활용하여 구현한다.
스택과 다르게 삽입, 삭제의 발생 인덱스가 달라서, overflow, underflow를 잘 계산하여야 하며, 원소의 수가 적거나 없어도 rear의 인덱스는 항상 증가하여 공간 낭비하는 문제점이 있다.
이를 해결하기 위해, 환형 큐를 사용하며, 인덱스들을 %큐의 크기 연산 해주어 공간 낭비를 해결한다. ( front와 rear인덱스의 값을 비교하여 겹쳐서 overflow인지 underflow인지 구분할 때 사이즈를 사용해야 한다. ) ( 이를 단순하게 하기 위해서 항상 첫 원소를 비워두는 기법도 있다. )
