[JAVA] Stack, Queue, Deque

Stack

대표적인 LIFO(Last in First Out) 구조의 자료구조로 나중에 들어온 것부터 먼저 내보낸다는 규칙을 가지고 있다. Stack은 Vector를 상속받아서 만들어졌ㄷ.

데이터를 입력하면 데이터가 쌓이게 된다, 이렇게 쌓인 데이터들은 가장 나중에 쌓인 데이터가 가장 위로

올라와 있게 된다. 이렇게 데이터를 입력하는 연산을 push라고 한다.

 

 

삭제 연산이 들어가게 되면, 가장 위에 있는 데이터(= 가장 나중에 들어간 데이터부터 제거)가 된다.

이렇게 데이터를 제거하는 연산을 pop라고 한다.

 

Stack은 컬렉션에서 List라고 하는 인터페이스 클래스를 이용하여 구현한 것이다.

List list = new Vector();

 

자바는 Stack보다 Deque로 사용하는 것을 권장한다.

보다 완전하고 일관성 있는 LIFO 스택 연산은 Deque 인터페이스를 사용하는게 좋다고 한다.

 

 

Deque(덱)

LinkedList가 Deque 인터페이스를 사용을 한다. public class LinkedList<E> exntends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable 자바의 LinkedList는 Doubly LinkedList 성격을 가지는데, 기 이유가 바로 Deque 때문이다. Deque은 앞 뒤로 추가제거가 가능한 자료구조이고, LinkedList 연산과 Stack 연산을 내장하고 있다.

 

Stack을 사용하기 위해선, Stack을 import 해야한다.

 

import java.util.Stack;

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

 

Stack 주요 메소드

형태	메소드	설명
boolean	empty()	스택이 비었으면 true, 아니라면 false
E	peek()	가장 맨 위에 위치한 값을 반환
E	pop()	가장 맨 위에 위치한 값을 제거하고 반환
E	push(E item)	가장 맨 위에 item을 추가
int	search(Object o)	1-based position에 의거하여 o의 위치를 반환 (o가 없다면 -1 반환)

출처 : Oracle Java SE Documentation

스택의 메소드는 5가지이다. 하지만, Vector를 상속받기 때문에, Vector에서 썼던 메소드도 사용이 가능하다.

Stack (Java Platform SE 8 )

 

 

 

Queue

대표적인 FIFO(First in First out) 즉, 선입선출 자료구조이다. (먼저 들어간 데이터가 가장 먼저 나오게 된다) 먼저 입력한 데이터를 front(head) 라고 하고, 뒤에 입력한 데이터를 rear(tail) 이라고 한다

가장 먼저 삽입된 데이터는 front로 기억이 되고, 가장 마지막에 삽입된 데이터는 rear로 기억이 된다.

 

삭제연산은 remove이다. 

front 지점의 데이터를 삭제하고 그 다음 데이터를 가리키게 된다.

 

삽입연산은 add이다.

rear지점의 위치 다음 데이터를 삽입한다.

 

Deque(덱)

덱은 Double-ended queue 의 줄임말로 LinkedList가 이 덱을 implements 해서 만든 것이다. (LinkedList는 List 인터페이스와, Deque 인터페이스, 그리고 Queue 인터페이스 등을 implements 한 것) 덱은 앞과 뒤에 삽입, 삭제를 할 수 있다. 또한 "Queue + Stack"의 기능을 가지고 있다.

Queue와 거의 같지만, Deque는 front와, rear에서 삽입, 삭제가 가능하다.

사진 출처 : Oracle Java Documents

 

삭제 연산(deQueue 연산)

삭제 연산은 deQueue 라고 한다. 덱에서 삭제 연산은 두가지이다. removeFirst(front 삭제 - Stack의 pop, Queue의 remove)와 removeLast(rear 삭제) 가 있다.

삽입 연산(enQueue 연산)

삽입 연산은 enQueue 라고 한다. 덱에서 삽입연산은 두가지이다. addFirst(front 삽입 - Stack의 push와 addLast(rear 삽입 - Queue의 add) 가 있다.

 

Queue와 Deque는 인터페이스이기 때문에, 해당 자료구조 인터페이스를 상속하는 클래스와 붙여 사용해야 한다.

 

 

Queue 주요 메소드

형태	메소드	설명
boolean	add(E e)	e를 Queue에 추가 (단, 사용 가능한 공간이 없으면 IllegalStateExeption 발생)
E	element()	front 부분의 값을 반환
boolean	offer(E e)	욜량 제한을 위반하지 않고 이 Queue를 사용할 수 있다면 e를 바로 Queue에 추가
E	peek()	front 부분의 값을 반환 (단, Queue가 비었다면 null값 반환)
E	poll()	front 부분의 값을 제거하고 그 값을 반환 (단, Queue가 비었다면 null값 반환)
E	remove()	front 부분의 값을 제거하고 그 값을 반환

Deque 주요 메소드

형태	메소드	설명
boolean	add(E e)	e를 rear 부분에 추가 (단, 사용 가능한 공간이 없으면 IllegalStateExeption  발생)
void	addFirst(E e)	e를 front 부분에 추가 (단, 사용 가능한 공간이 없으면 IllegalStateExeption  발생)
void	addLast(E e)	add와 같다.
boolean	contains(Object o)	o가 덱에 있으면 true, 없으면 false 반환
Iterator<E>	descendingIterator()	덱의 reverse Iterator를 반환
E	element()	덱의 front 값을 반환
Iterator<E>	iterator()	덱의 iterator를 반환
E	peek()	덱의 front 값을 반환 (단, 덱이 비었다면 null값 반환)
E	peekFirst()	peek와 같다
E	peekLast()	덱의 rear 값을 반환 (단, 덱이 비었다면 null값 반환)
E	pop()	덱의 front 값을 제거 후 그 값을 반환
void	push(E e)	addFirst와 같다
E	remove()	pop과 같다
E	removeFirst()	pop과 같다
boolean	removeFirstOccurence(Object o)	front 부터 o 값이 처음 나온 지점을 찾아내서 그 값을 제거
E	removeLast()	덱의 rear 값을 제거 후 그 값을 반환
boolean	removeLastOccurence(Object o)	rear 부터 o 값이 처음 나온 지점을 찾아내서 그 값을 제거
int	size()	덱의 크기를 반환

표 출처 : Oracle Java Documents