Stack, Queue / JAVA

 

Stack과 Queue

종류	특징
Stack	- 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조 - 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어 단 방향으로만 동전을 빼는 구조
Queue	- 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조 - 양 옆만 막혀있고 위아래로 뚫려있어 한 방향을 넣고 다른 방향으로 빼는 파이프 같은 구조

 

 

LIFO구조인 Stack에 0, 1, 2 순서로 데이터를 넣었다면 꺼낼 때는 2, 1, 0의 순서로 꺼내게 된다.

순차적으로 데이터를 추가하고 삭제하는 Stack에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하다.

(과자 프링글스통 같은 구조)

 

FIFO구조인 Queue는 0, 1, 2의 순서로 데이터를 넣었다면 꺼낼 때 역시 0, 1, 2 순서로 꺼내게 된다.

데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터 복사가 발생하므로 비효율적이다. Queue는 ArrayList보다 데이터의 추가·삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

(위 아래가 뚫린 통)

---

Stack과 Queue 메서드

컬렉션	메서드	설명
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부터 시작
Queue	boolean add()	- 지정된 객체를 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()	- 삭제없이 요소를 읽어옴, 비어있으면 null을 반환

 

 

---

Stack과 Queue 메서드 간단한 활용 예제

package java;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {

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

 

자바에서는 Stack클래스로 구현하여 제공하고 있지만

Queue는 Queue인터페이스만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다.

대신 Queue인터페이스를 구현한 클래스들이 있어서 이 들 중의 하나를 선택하여 사용하면 된다.