Java의 Stack과 Queue

YeJi Kim·2023년 2월 6일

JAVA

목록 보기

1/5

Stack

스택은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다.
자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택을 사용한다.
스택에 데이터를 넣는 작업을 push라 하고, 스택에서 데이터를 꺼내는 작업을 pop이라고 한다.
또, push와 pop이 이루어지는 쪽을 top이라 하고, 그 반대쪽을 bottom이라고 한다.

Stack 구현 클래스

자바에서는 스택을 Stack 클래스로 구현하여 제공하고 있다. Vector를 상속받아 구현된 클래스이기 때문에 동기화를 지원한다.
Stack의 메서드는 다음과 같다.

boolean empty(): Stack이 비어있는지 알려준다.
Object peek(): Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않음.(비어있을 때는 EmptyStackException 발생)
Object pop(): Stack의 맨 위에 저장되는 객체를 꺼낸다. (비어있을 때는 EmptyStackException 발생)
Object push(Object item): Stack에 객체(item)를 저장한다.
int search(Object o): Stack에서 주어진 객체를 찾아서 그 위치를 반환. 못 찾으면 -1을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작)

👉 자바 Stack 공식문서

🤔 Stack 대신 Deque?

공식문서에서는 더 완전한 LIFO를 구현하기 위해서는 Deque 인터페이스를 사용하라고 명시하고 있다.
아래의 글은 우테코에서 작성한 Stack 대신 Deque를 사용해야 하는 이유에 대한 글이다.
👉 Java 의 Stack 대신 Deque
다음 글 역시 참고할 만큼 유용한 글이다.
👉 [Java]Stack 대신 Deque 사용하기

Queue

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아두는 기본 자료구조 이다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)이다.
큐에 데이터를 넣는 작업을 en-queue라 하고, 데이터를 꺼내는 작업을 de-queue라고 한다.
또, 데이터가 나오는 쪽을 front라 하고, 데이터를 넣는 쪽을 rear라고 한다.

Queue 구현 클래스

자바에서는 큐를 Queue 인터페이스로 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다.
대신 Queue 인터페이스를 구현한 클래스들이 있어서 이들 중의 하나를 선택해서 사용하면 된다.
Queue를 구현한 클래스들은 대표적으로 ArrayDeque, LinkedList, PriorityQueue 등이 있다.
각 클래스들은 Queue 인터페이스에 정의된 메서드를 모두 작성해 놓았으면, 대부분 거의 같은 기능을 한다.
Queue의 메서드는 다음과 같다.

boolean add(Object o): 지정된 객체를 Queue에 추가
한다. 성공하면 true를 반환. 저장공간이 부족하면 IllegalStateException 발생
Object remove(): Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생
Object element(): 삭제없이 요소를 읽어온다. peek과 달리 Queue가 비어있을 때 NoSuchElementException 발생
boolean offer(Object o): Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환
Object poll(): Queue에서 객체를 꺼내서 반환. 비어있으면 null을 반환
Object peek(): 삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환

Summary of Queue methods
사진 출처: https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

👉 자바 Queue 공식문서

Pritority Queue

Queue 인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다.
null은 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다.
저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다. 힙은 이진 트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.
내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NlogN)이다.

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리, Deque는 양쪽 끝에 추가/삭제가 가능하다.
Deque의 조상은 Queue이며, 구현체로는 ArrayDeque와 LinkedList 등이 있다.
Deque은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.
다음과 같은 메서드들을 제공한다.
- Queue 메서드(FIFO)
  - addLast(e)
  - offerLast(e)
  - removeFirst(e)
  - pollFirst()
  - getFirst()
  - peekFirst()
- Stack 메서드(LIFO)
  - addFirst(e)
  - removeFirst()
  - peekFirst()