Java :: Collection :: 1.4 Stack & Queue

김병철·2022년 9월 1일

Collection Java Java의 정석 queue stack

Java

목록 보기

4/20

Java의 정석 3판을 보며 공부한 내용을 정리하였습니다.
남궁성님께 많이 배우고 있습니다.

1.4 Stack 과 Queue

Stack, Queue

# Stack ?

그림 1. 스택

마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조

예 )
IN : 3 -> 2 -> 1
OUT : 1 -> 2 -> 3

# Queue란?

그림 2. 큐

처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조

예 )
IN : 3 -> 2 -> 1
OUT : 3 -> 2 -> 1

# 스택과 큐에 알맞는 컬렉션 클래스

그렇다면 스택과 큐는 어떤 컬렉션 클래스를 사용하여 구현하는 것이 좋을까??

순차적으로 데이터를 추가/삭제하는 스택은 ArrayList가 좋을 것 같다.

추가할 때는 앞에서부터 순차적으로 입력되고, 꺼낼 때는 뒤에서부터 꺼내니 아주 적합하다.

그렇다면 큐는 어떨까?
추가할 때는 앞에서부터 순차적으로 입력되지만, 꺼낼 때도 앞에서 꺼내야 한다.
만약 ArrayList를 쓴다면 앞에서 꺼낼 때마다 빈 공간을 채우기 위해 ArrayList의 데이터들의 복사가 발생하므로 비효율적이다.

-> 큐는 삭제시에도 작업이 단순한 LinkedList가 적합하다.

# 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에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1을 반환.(배열과 달리 위치는 0이 아닌 1부터 시작)

# Queue의 메서드

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

static public void main(String[] args) {
	Stack st = new Stack();
	Queue q = new LinkedList();
		
	st.push("1");
	st.push("2");
	st.push("3");
	
	q.offer("1");
	q.offer("2");
	q.offer("3");
		
	System.out.println("STACK");
	while(!st.empty()) {
		System.out.println(st.pop());
	}
	
	System.out.println("QUEUE");
	while(!q.isEmpty()) {
		System.out.println(q.poll());
	}
}