[ 알고리즘 ] 스택, 큐

스택 ( Stack ) vs 큐 ( Queue )

스택과 큐는 자료 구조의 형태이며, 서로 상반되는 형태를 가진 자료 구조이다.

둘이 어떤 차이가 있는지 한번 살펴보도록 하자

스택이란 쌓는다는 것을 의미한다. 예를 들어 책을 박스에 쌓어서 창고에 보관하려고 했는데 내가 보려고 뒀던 책을 상자에 실수로 넣었으면 넣은 순서의 반대로 하나 하나 꺼내서 책을 찾아야 할 것이다.

상자에 차곡 차곡 쌓인 책을 꺼낼때 밑에서 부터 꺼낼수 없듯이 마지막에 넣은 자료가 가장 먼저 꺼내지는 특징을 가진 구조이다. 이러한 스택의 구조는 후입선출 ( LIFO ) 구조라고 한다.

상자에 책을 쌓는, 스택에 값을 삽입하는 연산을 Push, 상자에서 책을 꺼내는, 스택에 값을 삭제하는 연산을 Pop 이라 한다.

참고로 빈 스택에서 원소 추출을 하는 것을 Stack underflow, 스택이 넘치는데 스택을 추가하려 하면 stack overflow 라고 한다.

큐는 줄을 선다는 것을 의미하는 영단어로, 게임에서 매치 메이킹을 돌릴 때 나오는 "큐 돌렸다" 는 말이 여기서 나온것이다. 또 놀이 공원에서 입장 대기줄을 서는 것도 큐와 같은 형태라고 할 수 있다.

놀이 공원에 줄을 서면 가장 먼저 선 사람이 가장 먼저 들어가는것 처럼 큐도 먼저 넣은 데이터가 먼저 나가는 선입 선출 ( FIFO ) 구조라고 한다.

놀이 공원에 줄을 서는 과정을 큐에 값을 삽입하는 과정을 Enqueue 놀이 공원에 입장을 하는 과정을 큐에서 값을 삭제하는 과정을 Dequeue 라고 한다.