Stack과 Queue

스택과 큐는 '자료구조'하면 대부분이 떠올리는 선형 자료구조이자 ADT이다. 둘 다 값을 삽입하는 push와 값을 제거하며 반환하는 pop 명령을 가지며(다르게 부르기도 함), 자료구조가 비어있는지를 확인하는 empty, 원소가 얼마나 들어 있는지를 확인하는 size 명령이 구현되기도 한다. 스택과 큐는 한가지 큰 차이점이 있는데, 스택은 LIFO(Last In, First Out), 큐는 FIFO(First In, First Out) 구조다. 얼핏 생각해 보면, 스택의 특징인 '가장 최근에 들어간 원소부터 꺼내진다'는 굉장히 쓸데없어 보이지만, 꽤 많은 곳에서 사용된다.

• 함수의 call stack : 함수는 호출되었을 때 스택 프레임을 생성하여 call stack에 push되고, 함수가 종료되면 call stack에서 pop된다. 따라서, main -> a -> b -> c 순서로 함수를 호출하면, 순서대로 스택 프레임이 push되고, 가장 최근에 쌓인 스택 프레임부터 pop되어 c -> b -> a -> main 순서로 제어가 돌아온다.
• 브라우저의 히스토리 : 브라우저는 사용자가 방문한 페이지들을 차례로 스택에 push한다. '뒤로가기' 버튼을 누르면, 히스토리에서 주소를 pop하여 보여준다.

큐는 백엔드를 경험해본 사람이라면 익숙하겠지만, 작업 큐에서 자주 쓰인다. 그 외에도 정말 많은 곳에서 쓰인다. 예를 들자면, 운영체제의 스케줄링 알고리즘 중 FCFS(First-Come, First-Served) 스케줄링도 큐(정확히는 큐의 메커니즘인 FIFO)가 쓰인다.

설명만 무작정 하면 재미 없으니, Go로 스택과 큐를 구현하는 것으로 글을 마무리한다. Slice를 단지 써먹은 데에 지나지 않으므로, 진지하게 구현하려면 메모리를 직접 할당하는 방식(C의 mallic, realloc 등..)을 사용하자.