자료구조 - 스택, 큐 (Java -Stack, Queue)

제훈·2024년 7월 12일

자료구조

목록 보기

2/4

내가 아는 개념으로는

스택 : 계속 데이터가 쌓이면서 최근에 들어온 데이터가 나가는 Last In First Out (LIFO)
큐 : 먼저 들어온게 먼저 나가는 Fist In First Out (FIFO)

이정도였다. 더 자세하게 정리하고자 한다.

Stack : 수식 계산, 워드프로세서의 undo / redo, 웹브라우저의 뒤로/ 앞으로 와 같은 기능을 구현할 때 활용
Queue : 최근 사용 문서, 인쇄 작업 대기목록, 버퍼(buffer) 등을 구현할 때 활용

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

Stack Method

empty() : Stack이 비어 있는지 알려준다.

boolean 값을 반환해준다. -> 비어 있으면 true, 아니면 false
push(Object ob) : Stack에 객체(ob) 를 저장한다.
peek() : Stack 의 맨 위에 저장된 객체를 반환한다.

비어 있으면 EmptyStackException 발생
제거하는 것이 아닌, 반환만 하는 것이다.
pop() : Stack의 맨 위에 있는 객체를 반환해주고 제거한다.

비어 있으면 EmptyStackException 발생
search(Object ob) : Stack 에 주어진 객체(ob)를 찾아서 위치 반환

못 찾으면 -1 을 반환한다.

스택은 배열과 달리 위치가 1부터 시작한다.

예제 코드

import java.util.Stack;

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

        stack.push("100");
        stack.push("200");
        stack.push("300");

        int i = 1;
        while (!stack.empty()) {
            System.out.println(i + "번째");
            System.out.println("100 search : " + stack.search("100")); // "100" 찾기
            System.out.println("peek : " + stack.peek()); // 맨 위에 있는거 반환
            System.out.println("pop : " + stack.pop()); // 맨 위에 있는거 반환 후 제거
            i++;
        }

        System.out.println(stack.empty());
        System.out.println("End");
    }
}

Queue Method

추가, 삭제, 검사 순
add(Object ob) : 지정된 객체를 Queue에 추가한다.

성공하면 true 반환, 저장공간 부족 시 IllegalStateException
remove() : Queue에서 객체를 꺼내 반환한다.

비어있으면 NoSuchElementException 발생
element() : 삭제 없이 요소를 읽어온다.

peek과 달리 Queue가 비어있으면 NoSuchElementException 발생
offer(Object o) : Queue에 객체를 저장한다.

성공하면 true, 실패 시 false
poll() : Queue에서 객체를 꺼내서 반환

비어있으면 null 반환
peek() : 삭제 없이 요소를 읽어온다.

비어 있으면 null 반환

예제 코드

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

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

        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        int i = 1;
        while (!queue.isEmpty()) {
            System.out.println(i + "번째");
            System.out.println("1st element : " + queue.element());
            System.out.println("element : " + queue.element());
            System.out.println("remove : " + queue.remove());
            i++;
        }

        System.out.println(queue.isEmpty());
        System.out.println("End");
    }
}

PriorityQueue

Queue 인터페이스 구현체 중 하나로, 저장한 순서 상관없이 우선순위가 높은 것부터 꺼낼 수 있다.

PriorityQueue는 저장 공간으로 배열을 사용하며, 요소들을 heap 형태로 저장한다.

import java.util.PriorityQueue;
import java.util.Queue;

public class QueueApplication {
    public static void main(String[] args) {
        Queue queue = new PriorityQueue();

        queue.offer(500);
        queue.offer(35);
        queue.offer(77);

        System.out.println(queue);

        int i = 1;
        while (!queue.isEmpty()) {
            System.out.println(i + "번째");
            System.out.println("1st element : " + queue.element());
            System.out.println("element : " + queue.element());
            System.out.println("remove : " + queue.remove());
            i++;
        }

        System.out.println(queue.isEmpty());
        System.out.println("End");
    }
}