[Java] 스택(Stack)과 큐(Queue)

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

 

 

스택(Stack)과 큐(Queue)

Stack과 Queue

 Queue 는 먼저 들어간 데이터를 먼저 꺼내는 FIFO구조로 되어있고,  Stack 은 LIFO구조로 되어있어서 마지막에 저장한 데이터를 가장 먼저 꺼내게 된다.  Stack 은 수식계산이나 워드프로세서의 undo/ redo, 또는 웹브라우저의 뒤로/앞으로 같은 기능들을 구현할 때 활용되고, 큐는 최근 사용 문서, 인쇄 작업 대기목록, 버퍼(buffer)등의 기능을 구현할 때 활용된다. 

 

 

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 을 반환(배열과 달리 위치가 1부터 시작)

 

 

 

 

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을 반환

 

 

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList();	//Queue의 인터페이스 구현체인 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.isEmpty()) {
			System.out.println(st.pop());
		}
		
		System.out.println("=== Queue ===");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

 

실행결과

스택과 큐가 어떤구조로 되어있는지 확인하는 예제이다. 넣을 때는  0 ,  1 ,  2 로 같은 순서의 같은 값을 넣었지만 차이가 있는 것을 확인할 수 있다.  Queue 는 먼저 넣은 것이 먼저 나오는 FIFO구조이기 때문에 넣은 순서대로 나오고,  Stack 은 나중에 넣은것이 먼저 나오는 LIFO구조이기 때문에 넣은순서와 반대로 꺼내진 것을 알 수 있다.

자바에서는 스택을  Stack 클래스로 구현하여 제공하지만 큐는  Queue 인터페이스만 있고 별도의 클래스가 없다. 그래서  Queue 인터페이스를 구현한 클래스들을 사용해야 한다.

 

 

 

 

PriorityQueue

   Queue 인터페이스의 구현체 중 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다.  null 을 저장하면  NullPointerException 이 발생한다.  PriorityQueue 는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다. (자료구조의 heap과 JVM의 heap은 이름만 같고 다른 것들이다.)

 

 

package Example;

import java.util.*;

public class Example {
	public static void main(String[] args) {
		Queue pq = new PriorityQueue();
		
		pq.offer(3);	//원래는 pq.offer(new Integer(3));해야하는데 오토박싱이 된것
		pq.offer(1);
		pq.offer(5);
		pq.offer(2);
		pq.offer(4);
		System.out.println(pq);
		
		Object obj = null;
		
		//PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
		while((obj = pq.poll()) != null)
			System.out.println(obj);
	}
}

 

실행결과

저장 순서가  3 ,  1 ,  5 ,  2 ,  4 인데도 출력 결과가  1 ,  2 ,  3 ,  4 ,  5 인 것을 확인할 수 있다. 우선순위는 숫자가 작을수록 높아져서  1 이 가장 먼저 출력된다. 숫자가 아닌 객체를 저장하려면 각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다. 배열에 저장된 순서와 실제 우선순위가 다른 것은  PriorityQueue 가 각 요소를 힙이라는 자료구조의 형태로 저장한 것이라서 그렇다. 

 

 

 

Deque(Double-Ended Queue)

Queue와 Deque

 Queue 의 변형으로, 한쪽 끝으로만 추가/삭제할 수 있는  Queue 와 달리,  Deque 는 양쪽 끝에서 추가/삭제가 가능하다.  Deque 의 조상은  Queue 이며, 구현체로는  ArrayDeque 와  LinkedList 등이 있다.

 

 

 Deque 는  Stack 과  Queue 를 하나로 합쳐놓은 것과 같아서  Stack 으로 사용할 수도 있고,  Queue 로 사용할 수도 있다.