[Java] Stack, Queue, Priority Queue

1. Stack

import java.util.Stack;

Stack<String> stack = new Stack<String>();

• push() : 삽입
• pop() : 삭제
• peek() : 조회
• isEmpty() : 비었?
• size() : 크기

 

Stack underflow와 overflow를 조심하자.

 

---

2. Queue

import java.util.Queue;

Queue<String> queue = new ArrayDeque<String>(); // 
//또는
Queue<String> queue = new LinkedList<String>();

 

Java의 java.util.Queue는 interface다.

 

구현체로는 대표적으로 ArrayDeque 또는 LinkedList를 사용한다.

 

대부분의 상황에선 LinkedList보다는 ArrayDeque를 사용하자.

 

ArrayDeque 양쪽 끝에서 삽입, 삭제하기에 효율적이다.

 

• offer() : (rear에) 삽입
• poll() : (front에) 삭제
• peek() : 조회
• isEmpty() : 비었?
• size() : 크기

 

---

3. Priority Queue

package lacture;

import java.util.PriorityQueue;

public class PriorityQueueTest {

    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(3);
        pq.offer(7);
        pq.offer(5);
        pq.offer(4);

        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }
}
/*
3
4
5
7
*/

기본은 오름차순으로 정렬한다.

 

package lacture;

import java.util.PriorityQueue;

public class PriorityQueueTest {

    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)-> -(Integer.compare(a, b))); // Comparator interface 람다식

        pq.offer(3);
        pq.offer(7);
        pq.offer(5);
        pq.offer(4);

        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }
}
/*
7
5
4
3
*/

정렬의 순서를 자신이 원하는 방법으로 바꾸고 싶다. → Comparator를 추가한다.

 

package lacture;

import java.util.PriorityQueue;

public class PriorityQueueTest {

    public static void main(String[] args) {
        PriorityQueue<Data> pq = new PriorityQueue<>();

        pq.offer(new Data(3, 1));
        pq.offer(new Data(2, 2));
        pq.offer(new Data(2, 4));
        pq.offer(new Data(2, 1));
        pq.offer(new Data(6, 5));

        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }

    static class Data implements Comparable<Data> {
        int x, y;
        Data(int x, int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public String toString() {
            return "Data [x=" + x + ", " + y + "]";
        }
        @Override
        public int compareTo(Data o) {
            if(this.x == o.x) {
                return Integer.compare(this.y, o.y);
            }
            return Integer.compare(this.x, o.x);
        }
    }
}
/*
Data [x=2, 1]
Data [x=2, 2]
Data [x=2, 4]
Data [x=3, 1]
Data [x=6, 5]
*/

또는 Comparable을 구현해도 된다.

 

---

 

Data Structure	Insertion Time Complexity	Deletion Time Complexity
Stack	O(1)	O(1)
Queue	O(1)	O(1)
Priority Queue	O(log n)	O(log n)