[자료 구조] 스택 & 큐

[스택]

LIFO(Last In First Out) = "후입 선출"의 구조 -> 마지막에 넣은 것을 먼저 뺌

그림으로 그렸을 때 위에 형태와 같다. 즉 가장 나중에 삽입된 앨리먼트가 가장 먼저 처리되는(LIFO) 추상 자료형이다.

동작

• push() : 스택에 데이터를 추가하는 것.
• pop() : 스택에서 데이터를 빼는 것

시간복잡도

• 삽입(push) : O(1)
• 삭제(pop) : O(1)
• 읽기(Peek) : O(1)
• 탐색(Search) : O(n)

자바에서의 스택

Stack<Integer> stack = new Stack<>();

 

위의 코드와 같이 Java에서는 Stack을 따로 지원해준다. 하지만 쓰지 말라고 한다!!!

 

그 이유로는

<Stack 클래스가 너무 오래됐다. (1988년 등장)>

• 이때 당시에는 CPU 코어가 하나밖에 없었던 시절이기 때문에 모든 작업에 잠금이 수행되는 Vector라는 자료형을 기반으로 한다.
• Vector의 경우 메서드들이 synchornized가 걸려있어, 메서드 실행시 동기화 여부를 확인하느라 오버헤드가 발생할 수 있다!

이런 문제들로 인해 자바 공식 문서에서는 Stack 대신에 Deque 자료형을 사용할 것을 권고한다.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(23);
stack.push(4);
stack.pop(); -> 4

 

[큐]

FIFO(First In First Out) = "선입 선출"의 구조 -> 먼저 넣은 것을 먼저 뺌

그림으로 그렸을 때 위에 형태와 같다. 즉 가장 먼저 삽입된 앨리먼트가 가장 먼저 처리되는(FIFO) 추상 자료형이다.

스택보다 쓰임은 적지만 Deque나 Priority Queue와 같은 큐의 변형들이 여러 분야에서 매우 유용하게 쓰임!

BFS나 캐시 등을 구현할 때도 사용된다.

 

동작

• Enqueue() : 큐에 데이터를 추가하는 것.
• Dequeue() : 큐에서 데이터를 빼는 것

시간복잡도

• 삽입(Enqueue) : O(1)
• 삭제(Dequeue) : O(1)
• 탐색(Search) : O(n)

자바에서의 큐

자바에서의 Queue는 인터페이스이고, 이를 실제로 구현하는 자료형은 LinkedList 와 ArrayDeque가 있다.

Queue 인터페이스에는 큐에 필요한 삽인 연산 offer(), 추출 연산 poll()이 정의되며 이를 LinkedList가 구현한다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(23);
queue.offer(4);
queue.poll() -> 23