스택(Stack)/큐(Queue)/덱(Deque)

[ 목차 ]

 

스택(Stack)

- 스택이란, 한쪽에서만 자료를 넣고 뺄 수 있는 후입선출 LIFO(Last In First Out) 형식의 선형 자료구조이다.

- 그렇기 때문에 스택의 모든 연산은 스택의 최상단에서 일어난다.

스택은 주로 컴퓨터 연산에 사용하는 자료구조로 연산의 우선순위에 따라 쉽게 연산할 수 있도록 도와준다.

숫자와 연산자가 들어오면 연산자의 우선순위에 따라 스택에 쌓아두거나 스택의 위에서 나오면서 연산이 이루어진다.

가장 대표적으로 완전 탐색의 DFS 알고리즘을 구현하는데 사용한다. 

 

스택의 대표적인 메서드

1. push() : 인자로 넘어간 값을 스택의 맨 뒤에 삽입한다.
2. pop() : 맨 뒤의 요소를 뽑아서 리턴
3. peek() : 맨 뒤의 요소를 리턴한다. 단, 삭제하지않고 요소만 복사해서 리턴함.
4. empty() : 스택이 비어있는지 확인, 더 상위 개념의 isEmpty()사용을 추천.
5. size() : 스택의 크기 리턴

 

스택 시간복잡도

- 스택은 데이터를 한쪽 끝에서만 추가하고 제거하므로, 삽입과 삭제 모두 상수 시간에 수행된다.

- 삽입(Push) / 삭제(Pop)  : O(1)

- 탐색(Search) : 탐색하는 것은 stack의 구조와 맞지 않다. 굳이 한다면 O(n)

 

 

큐(Queue)

- 큐란, 한 쪽에서 삽입 작업이 이루어지고, 다른 한 쪽에서는 삭제 작업이 이루어지는 선입선출 FIFO(First In First Out)형식의 선형 자료구조이다.

- 이때, 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear), 리어에서 이루어지는 삽입 연산을 인큐(enQueue), 프론트에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 부른다.

큐는 이러한 선입선출의 특징 때문에 임시로 자료를 저장하거나, 버퍼와 같은 경우에 주로 사용하는 자료구조 형태이다.

 

큐의 대표적인 메서드

1. offer() / enqueue() : 인자로 넘어간 값을 큐의 맨 뒤로 삽입한다.
2. poll() / dequeue() : 맨 앞의 값을 뽑아서 리턴한다.
3. peek() / getfront() : 맨 앞의 값을 복사해 리턴만 하고 삭제하지는 않는다.
4. empty() : 큐가 비어있는지 확인한다.

 

큐 시간복잡도

- 큐는 양 끝에서만 데이터가 삽입,삭제가 발생하기 때문에, 모두 상수 시간에 수행된다.

- 삽입(Push) / 삭제(Pop) : O(1)

- 탐색(Search) : 탐색하는 것은 Queue의 구조와 맞지 않다. 굳이 한다면 O(n)

 

 

덱(Deque)

- 덱은 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 자료구조로, 스택과 큐의 특성을 모두 가지고 있다.

실제로 양쪽에서 삽입, 삭제가 필요한 경우는 많지 않고, 큐나 스택을 구현한 후 추가적으로 삽입, 삭제가 필요한 경우 사용한다. 보통 스케줄링에 많이 사용하며, 스케줄링이 복잡할수록 큐와 스택보다 더 나은 효율을 보여주곤 한다.

 

덱의 대표적인 메서드

1. offerFirst(), offer() : 두 메서드로 양끝에서 삽입할 수 있다.
2. pollFirst(), poll() : 두 메서드로 양 끝에서 값을 리턴받고 삭제할 수 있다.
3. peekFirst(), peek() : 두 메서드로 양 끝에서 값을 복사해서 리턴 받을 수 있다.
4. isEmpty() : 큐가 비어있는 지 확인한다.

 

덱 시간복잡도

- 덱은 양 끝에서 둘 다 데이터가 삽입,삭제가 가능하기 때문에, 모두 상수 시간에 수행된다.

- 삽입(Push) / 삭제(Pop) (앞/뒤에) : O(1)

- 탐색(Search) : O(1) (index 접근)

 

 

요약

• 스택: LIFO, 마지막 데이터 우선 접근에 최적화. 간단하지만 중간 데이터 접근이 어렵고 크기 제한이 있을 수 있음.
• 큐: FIFO, 순서대로 작업을 처리하기에 최적화. 하지만 중간 접근이 제한적이며 배열로 구현 시 공간 낭비 가능.
• 덱: 양쪽에서 삽입과 삭제가 가능해 유연하지만, 구현 복잡도와 메모리 사용이 큐보다 클 수 있음.

 

자바에서의 스택, 큐, 덱의 특징

1. 자바에서 스택, 큐, 덱 모두 컬렉션을 상속받기 때문에 컬렉션에서 지원하는 메서드들도 사용가능하다.
2. 자바에서 큐와 덱은 구현체없이 인터페이스만 존재한다. LinkedList를 이용해 인스턴스를 생성하고 다형성을 이용해 큐와 덱으로 객체 타입을 바꿔서 선언해 사용해야 한다.

 

 

 

-각각의 자료구조에 대해 공부했으니, 앞으로 상황에 맞는 자료구조를 선택하여 효율적으로 사용하자!

 

출처

https://velog.io/@jin5eok5/%EC%9E%90%EB%B0%94%EC%9D%98-Stack-Queue-Deque

[Java] Stack, Queue, Deque

https://velog.io/@falling_star3/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%ED%81%90Queue%EB%8D%B1Deque

[자료구조] 스택(Stack)/큐(Queue)/덱(Deque)

https://bigsong.tistory.com/32

[자료구조] 스택과 큐, 데크(Stack, Queue, Deque)