[Algorithm] 스택, 큐, 우선순위 큐

스택 (Stack)

 

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

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

 

* 스택의 연산

• pop(): 스택에서 가장 위에 있는 항목을 제거한다. 
• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때 true를 반환한다.

* 관련 메서드

• push(Object item): 해당 item을 Stack의 top에 삽입
• pop(): Stack의 top에 있는 item을 삭제하고 해당 item을 반환.  스택이 비어있을 때는 EmptyStackException 발생
• peek(): Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환.  스택이 비어있을 때는 EmptyStackException 발생
• isEmpty(), empty(): Stack이 비어있으면 true를 반환, 그렇지않으면 false를 반환
• search(Object o): 해당 Object의 위치를 반환 Stack의 top 위치는 1, 해당 Object가 없으면 -1을 반환 (index는 1부터 시작)
• size(): 스택의 크기

 

* 응용하기

• 스택 반복문 돌기
  • while(!stack.isEmpty()) { System.out.println(stack.pop( )); }
• 스택을 활용할 수 있는 문제
  • 괄호 짝 맞추기
  • LIFO 자료구조를 구현할 때

 

큐 (Queue)

 

한쪽에서는 자료를 저장하고(offer) 한쪽에서는 자료를 추출(poll)하는 FIFO 구조의 자료구조

Queue queue = new LinkedList();

 

* 큐 관련 메서드

• add(Object item): 해당 item을 큐에 추가. 성공하면 true, 공간이 부족하면 IllegalStateException 발생
• remove(): 큐에서 item를 꺼내 반환 후 삭제. 비어있는 경우 NoSuchElementException 발생
• element(): 큐에서 item을 꺼내 반환 후 삭제는 하지 않음. 비어있는 경우 NoSuchElementException 발생
• offer(Object item): 해당 item을 큐에 추가. 성공하면 true, 실패하면 false를 반환.
• poll(): 큐에서 item을 꺼내 반환. 비어있는 경우 NULL
• peek(): 큐에서 item을 꺼내 반환 후 삭제는 하지 않음. 비어있는 경우 NULL 반환
• isEmpty(): 비어있으면 true를 반환, 그렇지않으면 false를 반환

 

우선순위 큐(Priority Queue)

 

저장한 순서에 관계없이 우선순위(Priority)가 높은 item부터 꺼낸다.

큐는 배열, 힙(Heap), 연결 리스트 세 가지 방법으로 구현할 수 있으며, 일반적으로 힙을 사용한다.

 

우선순위 큐에 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야한다.

compareTo라는 메서드를 override 하여 우선순위에 따라 리턴하면 우선순위가 높은 객체를 추출해준다.

 

PriorityQueue<Class> pq = new PriorityQueue<Class>();

class Vehicle implements Comparable<Vehicle>{
    private String name;
    private int time;
    
    public Vehicle(String name, int time) {
        this.name = name;
        this.time = time;
    }
    
    public String getName() {
        return this.name;
    }
    
    public int getTime() {
        return this.time;
    }
    
    @Override
    public int compareTo(Vehicle target) {
        // 오름차순
        // 자신의 값보다 작으면 -1, 같으면 0, 크면 1 반환
        if(this.time < target.getTime())
            return -1;
        else if(this.time > target.getTime())
            return 1;
        return 0;
    }
}

import java.util.PriorityQueue;
 
public class Priority_Queue {
 
    public static void main(String[] args) {
        PriorityQueue<Vehicle> pQueue = new PriorityQueue<Vehicle>();
        
        pQueue.offer(new Vehicle("대중교통", 70));
        pQueue.offer(new Vehicle("자가용", 45));
        pQueue.offer(new Vehicle("도보", 400));
        pQueue.offer(new Vehicle("자전거", 125));
        
        while(!pQueue.isEmpty()) {
            Vehicle v = pQueue.poll();
            System.out.println(v.getName() + " 시간 :" + v.getTime());
        }
    }
 
}

offer을 통해 우선순위를 부여해 저장한 후, poll을 통해 추출해보면, 우선순위를 높게 지정한 시간을 기준으로 오름차순 데이터가 추출된다.

 

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

priorityQueue.add(1);
priorityQueue.add(2);
priorityQueue.add(3);
priorityQueue.add(4);

Integer poll = priorityQueue.
System.out.println(poll); // 출력결과 : 우선순위기 가장 낮은 4가 출력