[JAVA의 정석]Stack과 Queue

이 글은 유튜브 '자바의 정석 - 기초편'을 보고 정리한 글입니다. 

 

 

 

📂content

1. 스택과 큐 (Stack & Queue)

- 스택 (Stack) : LIFO 구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다. 

- 큐 (Queue) : FIFO 구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. 

스택
- 밑이 막힌 상자 
- 저장할 때와 추출할 때 순서가 반대

큐
- 양끝이 뚫린 상자  
- 저장할 때와 추출할 때 순서가 동일 

 

Stack과 Queue를 구현한다고 할 때, 배열과 LinkedList 중
어느 것이 더 효율적일까?
Stack은 배열이고, Queue는 LinkedList이다.  

 

 

 

 

 

2. 스택과 큐 (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에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못 찾으면 -1을 반환. (배열과는 달리 위치는 0이 아닌 1부터 시작) -> 마지막에 저장된 것부터 1

 

 

⚝ Queue의 메서드 

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가. 성공하면 true반환. 저장공간이 부족하면 IllegalStateException 발생 (추가)
Object remove()	Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생 (삭제)
boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true, 실패하면 false 반환 (추가)
Object poll()	Queue에 객체를 꺼내서 반환. Queue가 비어있으면 null을 반환 (삭제)
Object element()	삭제없이 요소를 읽어옴. peek과 달리 Queue가 비어있을 때 NoSuchElementException 발생
Object peek()	삭제없이 요소를 읽어 온다. Queue 비어있으면 null 반환

 

 

 

✎ 정리

add(추가), remove(삭제) => 예외발생 O
offer(추가), poll(삭제) => 예외발생 X

 

 

 

 

 

3. 인터페이스를 구현한 클래스 찾기

Stack은 클래스가 있지만, Queue는 인터페이스다. 

import java.util.Stack;
 
Stack<Integer> st = new Stack<>();

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

Queue<Integer> q = new LinkedList<>();​

그렇기 때문에, Queue를 사용하고 싶다면
Queue를 직접구현하거나 Queue를 구현한 클래스를 사용한다. 

 

Java API문서에서 찾은 Queue

All Known Implementing Classes 
Queue를 구현한 클래스 목록 

Queue인터페이스에 있는 추상메소드를 다 가지고 있다. => 즉, 이 중에 하나를 골라서 사용하면 된다. 

Queue<Integer> q = new LinkedList<>();
        
Queue<Integer> qq = new ArrayDeque<>();​

참조변수를 Queue대신에 LinkedList를 사용해도 상관은 없다. 하지만 Queue를 사용하는 이유는
1. LinkedList만 가지고 있는 메서드를 사용하지 않았다는 것. 즉, 클래스들의 공통메서드만 사용했다는 것이다. 
2. Queue를 구현할 수 있는 클래스라면 그 아래 코드를 검토하지 않아도 무엇으로 바뀌든지 상관X

그렇기 때문의 참조변수의 타입도 가능하면 좁혀주는 것이 좋다. 

 

 

 

⍟실습

package etc;


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

public class Ex11_2 {
    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.empty()){ //비어있는지 확인
            System.out.println(st.pop()); //스택에서 요소 하나를 꺼내서 출력
        }

        System.out.println(" = Queue = ");
        while(!q.isEmpty()){
            System.out.println(q.poll()); //큐에서 요소 하나를 꺼내서 출력
        }

    }
}

 

 

 

 

 

출처

https://www.youtube.com/watch?v=oJlCC1DutbA&list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp