스택(Stack) 이란?

스택(stack)은 후입선출(Last-In-First-Out, LIFO)의 구조를 가지고 있다.

01

Stack 클래스

Stack 클래스는 List Collection 클래스의 Vector 클래스를 상속받아, 스택 메모리 구조의 클래스를 제공한다. 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조이다. 스택의 가장 상단의 요소를 top이라고 한다.

Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메소드를 5개만 상속받아 사용한다.

메소드
설명
boolean empty() 해당 스택이 비어 있으면 true, 비어 있지 않으면 false를 반환한다.
E peek() 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환한다.
E pop() 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거한다.
E push(E item) 해당 스택의 제일 상단에 전달된 요소를 삽입한다.
int search(Object o) 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환한다.
이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작한다.

큐(Queue) 란?

큐(Queue)는 선입선출(First-In-First-Out, FIFO)의 구조를 가지고 있다.

02

Queue 클래스

클래스로 구현된 스택과 달리 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다. 이러한 인터페이스를 상속받는 하위 인터페이스는 다음과 같다.

  1. Deque
  2. BlockingDeque
  3. BlockingQueue
  4. TransferQueue

Queue 인터페이스를 직/간접적으로 구현한 클래스는 상당히 많다. 그 중에서 Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는데 가장 많이 사용된다.

큐 메모리 구조는 가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조이다.

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메소드만 상속받아 사용한다.

메소드
설명
boolean add(E e) 해당 큐의 맨 뒤에 전달된 요소를 삽입한다.
만약 삽입에 성공하면 true, 큐에 여유 공간이 없어 실패하면 illegalStateException을 발생시킨다.
E element() 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환한다.
boolean offer(E e) 해당 큐의 맨 뒤에 전달된 요소를 삽입한다.
E peek() 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환한다.
만약 큐가 비어있으면 null을 반환한다.
E poll() 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거한다.
만약 큐가 비어있으면 null을 반환한다.
E remove() 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거한다.

Reference