[자료구조] 스택, 큐, 데크 - 자료구조 삼대장

 

 

이번에 알아볼 것은 굉장히 유명한 자료구조 삼대장들인

스택(Stack), 큐(Queue), 데크(Deque) 입니다.

 

 

스택 (Stack)

 

스택은 자료구조의 맨 위에서만 삽입과 삭제가 일어나는 자료구조 입니다.

포인터가 맨 위를 가르키고 있어, 데이터의 가장 위에서만 삽입과 삭제가 일어나지요.

가장 나중에 들어간 원소가 가장 빨리 나오는

LIFO(Last in - First out) 구조 입니다.

PUSH를 통해 원소를 삽입, POP을 통해 원소를 꺼냅니다.

 

 

 

이는 쌓아놓은 접시와 비슷합니다.

접시를 쌓을 때는 보통 가장 윗 접시부터 꺼내 쓰곤하죠?

 

컨트롤 + z를 눌러 뒤로가기를 하는 것도,

브라우저의 뒤로가기도 스택의 예시 중 하나입니다.

 

 

 

자바의 Stack 클래스

 

 

출력 : 10, 10,  5, 3

 

자바에서는 기본적으로 Stack 클래스를 지원합니다.

push를 통해 원소를  삽입하고, pop을 통해 원소를 꺼냅니다.

원소를 꺼내는 것이 아니라 맨 위에 있는 원소만 슬쩍 보고 싶다면 peek 메소드를 사용하면 됩니다.

사이즈를 알고 싶다면 stack.size()를,

비어있는지 확인하고 싶다면 stack.isEmpty()를 사용하면 됩니다.

 

 

 

stack의 add vs push

stack에 원소를 넣는 방법은 두 가지가 있습니다.

 

 

바로 push와 add 인데요.

 

 

Stack은 Vector를 기반으로 구현되었는데,

Vector의 add 메소드가 밖으로 노출된 형태라 볼 수 있습니다.

add를 사용하여도 큰 문제는 없으나,

스택을 사용함을 보다 직관적으로 명시하기 위해 push 메소드를 사용할 것을 권장하고 있습니다.

 

 

 

 

다만, 스택은 만들어진지 꽤나 오래 된 클래스로써, 여러 결함을 갖고 있어요.

스택 클래스 내부 코드를 들여다보면, 더 완벽하고 일관성있는 LIFO 구조를 제공하는 Deque를 쓸 것을 권장하고 있습니다.

자세한 내용은 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/342

상속과 자바 Stack 클래스의 문제점

 

 

 

 

 

큐 (Queue)

 

 

 

 

반면에 Queue는 한쪽 끝에서만 삽입이 이루어지고, 반대쪽에서만 삭제가 일어나는 자료구조입니다.

FIFO (First - In, First - Out) 구조이지요.

넣는 과정을 Enqueue, 빼는 과정을 Dequeue라고 합니다.

 

 

 

 

이는 맛집에서 음식을 먹기 위해 웨이팅을 하는 것과 비슷합니다.

줄을 가장 처음 선 사람이 첫 번째로 들어가고,

두 번째로 선 사람이 두 번째로 들어갑니다.

새로 오는 사람은 줄의 맨 뒤 부터 기다려야 하죠

 

 

 

자바에서의 큐(Queue) 클래스

 

 

출력 : 3, 3, 1, 6

큐 역시 자바에서 지원하는 Queue 클래스가 있습니다.

offer를 통해 데이터를 삽입(Enqueue)하고,

peek을 통해 가장 처음에 삽입된 원소를 엿볼 수 있습니다.

poll을 통해 원소를 꺼낼 수 있죠 (Dequeue)

 

 

add vs offer

 

 

큐에는 원소를 삽입하는데 add와 offer 두 메소드가 존재합니다.

이 둘의 차이는 무엇일까요?

 

 

 

 

큐의 내부 클래스를 파고 들어가 메소드를 찾아봤습니다.

아하! 컴퓨터의 리소스는 한정되어 있어 큐를 특정 크기 이상으로 넣는 것은 불가능합니다.

add는 더 이상 원소 삽입이 불가능할 경우, 에러를 뿜어내며 종료하고

offer는 더 이상 원소 삽입이 불거능할 경우, false를 반환한다고 하네요!

 

예외처리 등으로 값을 핸들링할 경우에는 add를,

false 등으로 값을 받고 싶다면 offer를 사용하면 될 것 같습니다.

 

 

 

remove vs poll

 

remove와 poll의 경우도 마찬가지 입니다.

큐에서 원소를 꺼낼  때, remove의 경우 꺼낼 원소가 없다면 에러를 일으키지만,

poll의 경우 null을 반환하며 에러를 일으키지 않습니다.

 

 

 

변형 : 우선순위 큐

 

 

출력 : 2, 3, 5

큐의 종류 중 하나로 우선순위 큐가 있습니다.

큐에 들어간 원소에 특정 기준으로 우선순위를 매겨, 가장 우선순위가 높은 원소부터 꺼내는 방식인데요.

Integer 형으로 선언했지만, 클래스 내 멤버변수를 기준으로 설정할 수도 있습니다.

코딩테스트를 하다보면 굉장히 자주 쓰이는 녀석 중 하나입니다.

 

 

 

데큐 (Deque, Double-ended Queue)

데크 혹은 데큐라고 부르는 Deque 입니다.

 

 

 

Deque (Double-ended Queue) 라는 이름처럼,

양끝에서 삽입과 삭제가 가능한 자료구조입니다.

 

 

 

 

위와 같이 addFirst, addLast (offerFirst, offerLast)로 자료구조의 맨 처음과 끝에 자료를 삽입할 수 있고,

pollFirst, pollLast(removeFirst, removeLast)로 자료구조의 맨 처음과 끝에서 자료를 꺼낼 수 있습니다.

 

 

 

스택 vs 큐 vs 데큐

스택 : 선입후출. LIFO (Last In, First Out) 가장 나중에 들어온 자료가 가장 빨리 나감. 접시쌓기와 같음

큐 : 선입선출. FIFO (First In, First Out) 가장 처음에 들어온 자료가 가장 빨리 나감. 맛집 줄서기와 같음.

데큐 : 양쪽 끝 모두 삽입과 삭제가 가능