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

※ 본문은 혼자 공부한 내용을 기록한 글입니다. 오개념이 있다면 댓글로 알려주세요!

 

 

Stack과 Queue는 자료구조의 한 종류이다. Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out)구조로 되어 있고, Queue는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out)구조로 되어 있다.

 

자바는 Stack과 Queue를 제공하고 있으며 Stack은 Vector를 상속받는 클래스이고, Queue는 Collection을 상속받는 인터페이스이다. 

 

 

---

[ 1 ] Stack 클래스

Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내는 구조이므로 ArrayList와 같은 배열기반의 컬렉션 클래스로 구현하는 것이 적합하다. 배열에 순차적으로 데이터를 저장하고, 데이터를 꺼낼 때에는 단순히 배열의 가장 뒷 요소를 삭제하면 되기 때문이다. (배열에서 중간 요소를 삭제할 때에는 삭제하는 요소의 모든 뒷 요소들을 앞으로 당겨야하지만, 가장 뒷 요소는 단순히 삭제만 하면 되기 때문)

 

실제로 자바에서도 Stack 클래스를 내부에 Object 배열을 멤버변수로 갖고 있는 Vector 클래스를 상속받아 구현하였다.

ArrayList로 구현하지 않은 이유는 Stack 클래스는 컬렉션 프레임워크 이전부터 존재하던 클래스이기 때문이다.

 

- Stack 클래스 메서드

메서드	내용
boolean emtpy()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체 반환. pop()과 달리 Stack에서 객체를 꺼내진 않는다. (Stack이 비어 있다면 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체 반환. (Stack이 비어 있다면 EmptyStackException 발생)
Object push(Object obj)	Stack에 객체를 저장.
int search(Object obj)	Stack에서 주어진 객체(obj)를 찾아서 그 위치를 반환. 못 찾으면 -1을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작)

 

- 예제

import java.util.Stack;

public class myStack {

    public static void main(String[] args) {
        Stack stack = new Stack();

        stack.push("0");
        stack.push("1");
        stack.push("2");

        System.out.println("-- Stack --");
        while(!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
        // LIFO 이므로 2 1 0 출력
    }
}

 

 

---

[ 2 ] Queue 인터페이스

Queue는 데이터를 꺼낼 때 항상 첫 번째로 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스로 구현하면 비효율적이다. 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 뒷 요소들을 앞으로 당겨야하기 때문이다.

 

그래서 Queue는 배열기반의 클래스보다 데이터의 추가/삭제에 효율적인 LinkedList로 구현하는 것이 적합하며, 실제로 LinkedList는 Queue 인터페이스를 구현하고 있다. (LinkedList 말고도 Queue 인터페이스를 구현하는 클래스들이 많은데, 이는 Java API 문서를 참고하자)

 

- Queue 인터페이스 메서드

메서드	내용
boolean add(Object obj)	지정된 객체를 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 반환.

 

- 예제

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

public class myQueue {

    public static void main(String[] args) {
        Queue q = new LinkedList();

        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println("-- Queue --");
        while(!q.isEmpty()) {
            System.out.println(q.poll());
        }
        // FIFO 이므로 0 1 2 출력
    }
}