Stack과 Queue

1. Stack이란

스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 LIFO(Last In, First Out)이다. 스택에 데이터를 넣는 작업을 push라고 하고, 스택에서 에이터를 꺼내는 작업을 pop이라고 한다.

스택의 가장 윗부분(push와 pop을 하는)을 top이라고 하고, 스택의 가장 아랫부분을 bottom이라고 한다.

Stack은 자리 이동이 없고 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열기반의 컬렉션 클래스를 통해 구현하는 것이 적합하다..

 

(1) Stack의 예시 : 자바 프로그램에서 메소드를 호출하고 실행하는 프로세스

익히 잘 알고 있는 Call stack의 과정이다.

void x() {/* ... */}
void y() {/* ... */}
void z() {
    x();
    y();
}
int main() {
    z();
}

Stack

(2) Stack 만들기

public class IntStack {
    int max;    // 스택 용량 (스택에 쌓을 수 있는 최대의 데이터 수)
    int ptr;    // 스택 포인터 (스택에 쌓여있는 데이터 수)
    int[] stk;  // 스택의 본체

    // 스택이 비어있을 시 예외
    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){
        }
    }

    // 스택이 가득 찼을때 예외
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){
        }
    }

    public IntStack(int capacity){
        ptr = 0;
        max = capacity;
        try{
            stk = new int[max]; // 스택 본체 배열 생성
        } catch (OutOfMemoryError e){   // 생성 할 수 없음
            max = 0;
        }
    }

    // push method
    public int push(int x) throws OverflowIntStackException{
        if (ptr >= max) throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    // pop method
    public int pop() throws EmptyIntStackException{
        if (ptr <= 0) throw new EmptyIntStackException();
        return stk[--ptr];
    }

    // peek method : 스택의 꼭대기에 있는 데이터 몰레 엿보는 메소드
    public int peek() throws EmptyIntStackException{
        if (ptr <= 0) throw new EmptyIntStackException();
        return stk[ptr-1];
    }
    // indexOf method : 검색 메소드. stk에 x와 같은 값 포함 되어있는지, 포함되어 있따면 배열 어디에 들어있는지 조사
    public int indexOf(int x){
        for (int i = 0; i <= ptr -1; i ++){
            if (stk[i]==x) return i;
        }
        return -1; //검색 실패
    }

    // clear method : 모든 요소 삭제하는 메소드
    /* stack의 push와 pop은 stack pointer(ptr)를 바탕으로 이루어 지기 때문에 배열 요소의 값을 변경할 필요가 없다.
    * 그냥 ptr값을 0으로 초기화 시켜 주면 된다.*/
    public void clear(){
        ptr = 0;
    }

    // capacity method : 스택의 용량값(max)를 반환하는 메소드
    public int capacity(){
        return max;
    }

    // size method : 데이터 수 확인
    public int size(){
        return ptr;
    }

    // isEmpty method : 스택이 비어있는지 검사
    public boolean isEmpty(){
        return ptr <= 0;
    }
    // isFull method : 스택이 가득찼는지 검사
    public boolean isFull(){
        return ptr >= max;
    }
    // dump method : stack안의 모든 데이터를 표시.
    public void dump(){
        if (ptr <= 0) System.out.println("Stack is empty");
        else {
            System.out.print("[ ");
            for (int i = 0; i < ptr ; i++) {
                System.out.print(stk[i] + " ");
            }
            System.out.print("]");
        }
    }
}

stack에서의 여러가지 메소드를 만들어 보았고 예제는 나의 깃헙에 올려놓았다.

https://github.com/juno-junho/Data-Structures-and-Algorithms/tree/master/src/data_structures/stacks/using_array

GitHub - juno-junho/Data-Structures-and-Algorithms

(3) 자바에서 Stack 의 메소드

 - boolean empty()

 - Object peek() (맨위에 저장된 객체 반환)

 - Object pop() (맨위에 저장된 객체 꺼냄. 비었을때는 EmptyStackException 발생)

 - Object push(Object item) (Stack에 객체 저장)

 - int search(Object o) (객체 위치 반환. 못찾으면 -1 반환)

 

2. Queue

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다.

스택이 LIFO였다면 큐는 FIFO(First In, First Out)으로 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어있다. 따라서 Queue는 배열보다 데이터의 추가/삭제가 쉬운 LinkedList가 효과적이다. 요소를 삭제해도 자리이동이 불필요하기 때문이다.

 

큐에 데이터를 넣는 작업을 enqueue(인큐)라고 하고, 데이터를 꺼내는 작업을 dequeue(디큐)라고 한다. 

데이터를 꺼내는 쪽을 front라하고, 넣는 쪽을 rear라고 한다. 

 

(1) 큐의 예시 : 실생활에서 은행 창구에서 차례를 기다리고, 놀이기구를 기다리는 줄, 마트에서 계산을 기다리는 대기열을 들 수 있다.

Queue

(2) Queue 만들기

package collection;

public class IntQueue {
    private int max; // queue의 용량
    private int front;  // 첫 번째 요소 커서
    private int rear;   // 마지막 요소 커서
    private int num;    // 현재 데이터 수
    private int[] que;  // 큐 본체

    // 큐가 비어 있을 때 예외 발생
    class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){};
    }
    // 큐가 가득 찼을 때 예외 발생
    class OverFlowIntQueueException extends RuntimeException{
        public OverFlowIntQueueException(){};
    }
    // 생성자
    public IntQueue(int capacity){
        num = 0; front = 0; rear = 0;
        max = capacity;
        try {
            que = new int[max]; // queue 본체용 배열 생성.
        }catch (OutOfMemoryError e){
            e.printStackTrace();
            max = 0;    // OutOfMemoryError 발생시 생성 할 수 없음/
        }
    }
    // queue에 데이터 enque (넣기)
    public int enque(int x) throws OverFlowIntQueueException{
        if (num >= max) throw new OverFlowIntQueueException();  // queue가 가득 참
        que[rear++] = x;
        num ++;
        if (rear == max) rear = 0; // rear가  max와 같아지면 실제 배열에는 없는 공간인 que[max]를 가리킴.
        return x;
    }
    public int deque() throws EmptyIntQueueException{
        if (num <= 0) throw new EmptyIntQueueException();   // 큐가 비어있음.
        int x = que[front++]; // 첫번째 요소부터 하나씩 뺌. 
        num--;  // 데이터 수 하나 감소.
        if (front == max) front = 0;
        return x;
    }
    public int peek() throws EmptyIntQueueException{
        if (num <= 0) throw new EmptyIntQueueException();
        return que[front];
    }
    public int indexOf(int x){
        for (int i = 0; i < num; i++) { // 데이터 개수 만큼 돈다.
            // rear쪽으로 선형 검색. 
            int idx = (i + front) % max;    
            if (que[idx] == x) return idx;      // 검색 성공
        }
        return -1;      //검색 실패
    }
}

 

(3) 자바에서 Queue의 메소드 ( Exception 발생여부로 각각 두가지 메소드가 있음 )

 

 - boolean add(Object o)  : 지정된 객체를 Queue에 추가. 성공시 true, 저장공간 부족 시 IllegalStateException 발생

 - boolean offer(Obejct o)  : 지정된 객체를 Queue에 추가. 성공하면 true, 실패하면 false 반환

---> 차이점 : Exception을 throw하냐 안하냐 차이

 - Object remove() : Queue에서 객체를 꺼내서 반환. 비어있으면 NoSuchElementException 발생 

 - Object poll() : Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환 (null 처리 해줘야함)

----> 차이점 : 마찬가지로 Exception의 차이. null로 받을 것인지, exception을 발생시킬 것인지.

 - Object element() : 삭제 없이 요소를 읽어옴. peek과 달리 Queue가 비었을 때 NoSuchElementException 발생 

 - Object peek() : 삭제 없이 요소를 읽어옴. Queue가 비었을 때 null 반환

 

** 자바에서 Stack과 Queue의 차이 : Stack은 클래스로, Queue는 인터페이스로 설정되어 있음.(Queue는 LinkedList로 구현)

 

(4) Priority Queue

 - Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것 부터 꺼내게 된다. (일반적인 FIFO 구조를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 설정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조 이다)

null은 저잘 할 수 없고 null을 저장하면 NPE가 발생한다.

PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(Heap) 자료 구조의 형태로 저장한다. (시간 복잡도 O(NlogN)

위와 같이 Comparator를 줘서 순서를 설정할 수 있다.

 

(5) Deque (Double-Ended Queue)

 - Queue의 변형으로, 한 쪽 끝으로만 추가/사겢 할 수 있는 Queue와 달리 Deque는 양쪽 끝에 추가/삭제 가능하다. 

Deque의 조상은 Queue이며, 구현체로는 ArrayDeque와 LinkedList 등이 있다.

 - addFirst(), addLast()로 각각 앞쪽에 element를 삽입하거나, 마지막 쪽에 element를 삽입할 수 있다.

 

 

Reference : 

자바의 정석 3판(도우출판)

Do it! 자료구조와 함께 배우는 알고리즘 입문 (이지스 퍼블리싱)

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90