17. [JAVA] 스택 과 큐(Stack / Queue)

알고리즘을 공부하던 도중

 

스택 과 큐에 대해서 공부하게 되었다

 

스택 과 큐의 개념은 알고 있었으나 

 

이걸 왜 사용하는지 궁금했고

 

이걸 원래는 JAVA 클래스로 구현해서 사용했었고

 

그렇기에 더더욱이 이 방식을 채택해야하는 이유에 의문이 있었으나

 

실제로 Queue , Stack 이라는 클래스가 기존에 만들어져 있다는 사실을 알게 되었다

 

 

 

---

 

 

간단하게 설명하자면

 

스택은 쌓이는 개념

큐는 앞으로 빠져 나가는 개념이다

 

 

그림으로 보도록 하자

 

---

 

[스택]

 

스택

 

스택은 Push로 데이터를 넣고 Pop 으로 데이터를 꺼내 올 수 있다

 

LIFO 방식으로 만약 0 1 2 순으로 데이터를 넣었을 때

 

스택은 데이터가 위로 쌓이게 된다

 

그렇기에 위에서 부터 데이터를 꺼낼 수 있고

 

마지막에 넣은 데이터를 꺼내야만 그 앞에 넣은 데이터를 꺼낼 수 있다

 

 

---

 

[큐] 

 

큐

 

큐는 일방통행이다 

 

큐는 Add로 데이터를 입력하고 Poll로 데이터를 뺄 수 있다

 

큐는 FIFO 방식으로 처음에 들어간 데이터가 처음에 데이터를 빼게 되는데

 

예를 들어 0 1 2 라는 데이터를 넣으면 

 

스택은 마지막에 넣은 2를 먼저 빼지만 큐는 가장 처음에 넣은 0을 먼저 빼게 된다

 

 

---

 

 

Stack

 

// 스택 생성
Stack<Integer> stack = new Stack<>();

// 1 2 3 순으로 데이터를 입력
stack.push(1);
stack.push(2);
stack.push(3);

// 가장 위에 있는 데이터를 체크할 수 있다
System.out.println(stack.peek());

// 마지막에 넣은 것 먼저 데이터를 출력하므로 3 2 1 순으로 데이터를 출력함
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());

 

 

push : 데이터 삽입

pop : 데이터 출력

peek : 가장 최근에 넣은 데이터를 확인

 

---

 

 

Queue

 

 

// 큐 생성 (LinkedList 로 생성함)
 Queue<Integer> queue = new LinkedList<>();

 // 큐에 데이터 넣기
 queue.add(1);
 queue.add(2);
 queue.add(3);

 // 큐의 데이터 중 가장 앞에 있는 데이터를 확인
 System.out.println(queue.peek());

 // 큐에 있는 데이터 출력 - 큐는 처음에 넣은 것을 먼저 빼기에 1 2 3 순으로 출력
 System.out.println(queue.poll());
 System.out.println(queue.poll());
 System.out.println(queue.poll());
 

 

 

add : 데이터 삽입

poll : 데이터 출력

peek : 가장 처음에 넣은 데이터 확인

 

 

또한 스택은 가장 최근에 넣은 데이터를 넣고 빼지만

 

큐는 가장 처음 넣은 데이터와 마지막에 넣은 데이터를 확인할 수 있는 키워드가 필요하고

 

가장 앞의 데이터를 front, 가장 뒤의 데이터를 rear 라고 표현한다

 

 

 

---

 

우선 순위 큐 ( Priority Queue )

 

 

우선 순위 큐란?

 

일반적인 FIFO 방식의 큐가 아닌 우선 순위를 결정해서 해당 우선 순위가 높은 것이 먼저 나가도록 하는 자료구조 이다

 

 

우선순위 큐를 구현하기 위해서는 반드시 Comparable 인터페이스를 반드시 구현해줘야한다

 

Comparable은 전에 공부했지만 간단하게 말하자면 우선 순위를 정해주는 인터페이스로 CompareTo 라는 메소드를 반드시 구현하게 되어있다. 해당 메소드에서 O1, O2 중 누가 우선 순위가 높은지 체크해서 비교해 리턴하게 해준다

 

 

[ 사용법 ]

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 - 오름차순
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

// 데이터 입력
priorityQueueLowest.add(2);
priorityQueueLowest.add(1);
priorityQueueLowest.add(4);
priorityQueueLowest.add(3);

// 데이터 출력 : 1 2 3 4
System.out.println(priorityQueueLowest.poll());
System.out.println(priorityQueueLowest.poll());
System.out.println(priorityQueueLowest.poll());
System.out.println(priorityQueueLowest.poll());

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언 - 내림차순
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

// 데이터 입력
priorityQueueHighest.add(2);
priorityQueueHighest.add(1);
priorityQueueHighest.add(4);
priorityQueueHighest.add(3);

// 데이터 출력 : 4 3 2 1
System.out.println(priorityQueueHighest.poll());
System.out.println(priorityQueueHighest.poll());
System.out.println(priorityQueueHighest.poll());
System.out.println(priorityQueueHighest.poll());

 

또한 Comparable을 자신이 구현할 수 있다

 

// 우선 순위를 설정하는 Comparable 인터페이스를 구현하는 PriorityQueue
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1,o2) ->{

    int first = Math.abs(o1);
    int second = Math.abs(o2);

    if(first == second){
        // 절댓값이 같을 때는 음수를 앞으로 배치
        return o1 > o2 ? 1 : -1;
    }else{
        // 절댓값을 기준으로 정렬하기
        return first - second;
    }
});

// 데이터 입력
priorityQueue.add(-1);
priorityQueue.add(-5);
priorityQueue.add(-3);
priorityQueue.add(1);
priorityQueue.add(5);
priorityQueue.add(3);
priorityQueue.add(7);

// 데이터 출력
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());

 

해당 방식으로 진행 시

 

절댓값으로 비교하는 Math.abs를 사용해서 값이 같은지 확인 한 뒤

 

두 값이 같을 때 값의 크기를 비교해서 음수를 앞 쪽으로 배치하도록 한다

 

그게 아닐 때는 절댓값을 기준으로 앞쪽으로 배치할 수 있도록 한다

 

출력하면 

 

-1 1 -3 3 -5 5 7

 

이라는 값이 출력되게 된다