스택에서는 가장 최근에 삽입된 원소가 삭제된다. 즉, 후입선출 정책을 구현한 것이다. 큐에서는 집합에서 가장 오랜 시간 동안 존재한 원소가 삭제된다. 즉, 선입선출 정책을 구현한 것이다.

🗂 스택

스택에서는 스택에 값을 추가하는 연산을 Push, 인자를 값을 삭제하는 연산을 Pop이라고 한다.

💡 이때 Pop은 인자를 가지지않고 가장 최근에 삽입된 원소를 제거한다.

💡 이 연산들의 이름은 카페테리아 식당에서 스프링으로 접시를 받쳐 올려주는 접시 스택에서 유래된 것이라고 한다.

배열 S[1..n]으로 최대 n개의 원소를 가지는 스택을 구현할 수 있다. 배열은 가장 최근에 삽입된 원소를 가리키는 S.top을 속성값으로 가진다. S[1]은 스택의 맨 밑에 있는 원소를 나타내고 S[S.top]은 맨 위에 있는 원소를 나타낸다.

S.top = 0일때, 스택이 비었다(empty)고 한다. 빈 스택에서 원소를 추출하려고 하면 Stack Underflow 에러가 발생하며 S.top이 원소의 개수 n을 초과하면 개발자들에게 가장 친근한 이름 Stack overflow가 발생한다.

📦 큐

큐의 Push 연산을 Enqueue, Pop 연산을 Dequeue라고 한다. 스택의 Pop 연산과 동일하게 Dequeue도 인자를 갖지 않는다.

큐의 FIFO 특성은 계산대에 줄을 서있는 사람을 서비스하는 일에 비유할 수 있다. 큐는 Head와 Tail이라는 인자를 가진다. 새로 도착한 손님이 줄의 맨 끝에 위치하는 것처럼 원소가 삽입될 때 그 원소는 큐의 꼬리에 위치한다. 큐에서의 삭제는 가장 오래 기다린, 대기열의 맨 앞에 있는 손님처럼 항상 큐의 머리 위치에 있는 원소를 삭제한다.

큐의 head가 tail과 같은 경우 큐는 비었다고 말한다. 빈 큐에서 원소를 삭제하려고 하면 Queue underflow가 발생한다. 또한 큐가 가득찬 상태에서 원소를 삽입하려고 하면 Queue overflow가 발생한다.

결론

오늘은 코딩을 하면서 가장 많이 들었던 2개의 자료구조 스택과 큐에 대해서 알아보았다. 확실히 가장 기본적인 자료구조 2가지라 그런지 그렇게 특별한 점은 없는 것 같다.