스택(Stack)과 큐(Queue) 그리고 덱(Deque)

• 스택(Stack) 이란?

 스택이란 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출 (LIFO : Last In First Out)이다.

 

• 배열로 스택을 구현하기

 배열로 스택을 구현해보면 훨씬 알기 쉬울 것이다. 우선 IntStack이라는 Class를 통해 스택의 구조를 알아보자.

class Intstack{ // int형 고정 길이 스택
    int[] stk;   // 스택을 구현하기 위한 배열
    int capacity;// 스택 크기
    int ptr;     // 스택 포인터

    Intstack(int max){
        ptr = 0;
        capacity = max;
        try{
            stk = new int[capacity];  // 스택 본체용 배열 생성
        }catch (OutOfMemoryError e){  // 메모리의 공간이 부족해 생성할 수 없음
            capacity = 0;
        }
    }
}

 스택은 Intstack 객체 생성 시 입력한 max 값으로 크기가 정해지고 이는 배열의 크기와 같다. 그리고 ptr이라는 스택 포인터를 0으로 설정하고 시작하는데, 이 ptr이 스택이 얼마나 차 있는가를 나타내는 지표가 된다. 혹시 메모리가 모자랄 수 있으니 예외처리도 해준다.

 

 이렇게 생성자를 통해 기본 스택의 구조를 만들었다. 이제 이 스택에 사용할 수 있는 메서드들을 만들 것이다. 

 

       - push() : 스택에 데이터를 추가한다.

       - pop() :  가장 나중에 들어온 값을 제거하고 출력한다. 

       - peek() : 가장 나중에 들어온 값을 출력한다.

       - clear() : 스택 안의 모든 데이터를 삭제한다.

       - indexOf() : 스택 내에서 입력한 값을 검색한다.

       - getCapacity() : 스택의 용량을 출력한다. (최대 크기)

       - size() : 스택에 쌓여있는 데이터 개수를 반환한다.

       - isEmpty() : 스택이 비어있으면 true 아니면 false를 반환한다.

       - isFull() : 스택이 가득 찼으면 true 아니면 false를 반환한다.

       - dump() : 스택의 모든 데이터를 맨 처음 들어온 값부터 가장 나중에 들어온 값까지 순서대로 출력한다.

 

 먼저 push와 pop부터 구현해보자.

class EmptyIntStackException extends RuntimeException{
    EmptyIntStackException(){}
    // EmptyIntStackException 예외 생성
}
class OverflowIntStackException extends RuntimeException{
    OverflowIntStackException(){}
    // OverflowIntStackException 예외 생성
}
int push(int x)throws OverflowIntStackException{
    if (ptr>=capacity)
        throw new OverflowIntStackException();
    // 스택이 꽉 찼으면 OverflowIntStackException 예외 발생
    return stk[ptr++] = x; // 스택에 데이터 추가 후 출력
}
int pop()throws EmptyIntStackException{
    if (ptr<=0)
        throw new EmptyIntStackException();
    // 스택이 비어있으면 EmptyIntStackException 예외 발생
    return stk[--ptr]; // 스택의 꼭대기값 제거 후 출력
}

 맨 위의 내부클래스 2개는 push와 pop메서드에서 사용할 예외를 만들어 놓은 것이다.  이렇게 사용자가 쓸 예외를 따로 만들 수 있는데 클래스의 이름은 Exception을 뒤에 붙여 마음대로 만들고 일반예외일 경우 Exception을 실행예외일 경우 RuntimeException을 상속시키면 된다. 생성자는 2개를 만들 수 있는데 다음과 같다.

  

public class xxxException extends [ Exception | RuntimeException ]

   public xxxException(){} // 생성자 1

   public xxxException(String message){ super (message);}  // 생성자 2

}

 

 생성자 1은 기본으로 작성해야 하는 것이고 생성자 2는 예외발생 원인 메세지를 전달하기 위해 존재한다. 이번 예제에서는 생성자 2를 따로 만들진 않았다.

 

예외를 정의했으니 push를 정의해보자 만약 스택이 가득 찼으면 예외를 발생시키고 아니면 스택에 데이터를 추가하고 출력한다. 그 아래 pop은 스택이 비어있으면 예외를 발생시키고 스택의 꼭대기값을 제거하고 출력한다.

 예외를 발생시키는 법은 위에서 나온 것처럼 throw new xxxException();을 사용한다. 만약 생성자 2도 있다면 throw new xxxException("message");도 가능하다.

 

 이번에는 peek, clear, indexOf, getCapacity를 구현해 보자.

int peek()throws EmptyIntStackException{
    if (ptr<=0)
        throw new EmptyIntStackException();
    // 스택이 비어있으면 EmptyIntStackException 예외 발생
    return stk[ptr -1]; // 스택의 꼭대기값 출력
}
void clear(){
    ptr = 0; //스택 초기화
}
int indexOf(int x){ // x값을 찾는 선형 검색 시작
    for(int i = ptr-1; i >= 0; i--)
        if(stk[i] == x)
            return i; // 검색 성공
    return -1;        // 검색 실패
}
int getCapacity(){
    return capacity; // 스택의 용량 출력
}

 peek는 스택이 비어있으면 예외를 발생시키고 아니면 스택의 꼭대기값을 출력한다. pop과 달리 제거하진 않는다. clear는 스택의 모든 데이터를 지우는 메서드인데 간단히 ptr = 0으로 만들기만 하면 된다. indexOf는 이전에 배운 선형 검색을 스택에서 하는 것이고 getCapapcity는 그냥 capacity만 출력하는 메서드이다. 

 

 마지막으로 size, isEmpty, isFull, dump를 구현해 보자.

int size(){
    return ptr; // 스택에 쌓여있는 데이터개수 출력
}
boolean isEmpty(){
    return ptr <= 0; // 스택이 비어있으면 true, 아니면 false 반환
}
boolean isFull(){
    return ptr >= capacity; // 스택이 가득 찼으면 true, 아니면 false 반환
}
void dump(){
    if(ptr <= 0)
        System.out.println("스택이 비어 있습니다.");
    // 스택이 비어있으면 메세지 출력 후 종료
    else{
        for(int i=0; i < ptr; i++)
            System.out.print(stk[i]+" ");
        System.out.println();
    }// 스택이 안 비어있으면 스택의 바닥부터 꼭대기값 순으로 출력
}

 size, isEmpty, isFull은 다 위에서 배운 그대로 구현되어있고 dump는 스택이 비어있으면 메세지 출력 후 종료, 그렇지 않으면 반복문으로 스택의 바닥부터 꼭대기값까지 순서대로 전부 출력한다.

 

• 실제 스택 사용방법

 실제로는 스택클래스가 따로 있어서 굳이 만들어 쓸 필요가 없다. 이번엔 Stack 클래스 사용법을 알아보자.

 

   1. Stack 선언

       Stack<자료형> 변수 이름 = new Stack<>(); 로 스택 선언이 가능하다.

 

   2. Stack Method

      Stack 선언을 했다면 메서드도 쓸수 있다.

       변수 이름.push(x) : x를 스택에 추가한다.

       변수 이름.pop()

       변수 이름.peek(x)

       변수 이름.empty()

       변수 이름.contains(x) : 스택에 x가 포함되어 있으면 true 아니면 false 출력 

       변수 이름.clear()

 

• 큐(Queue) 란?

 큐(Queue) 란 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 선입선출 (FIFO : First In First Out)이다.

 

• 배열로 큐 구현하기

 배열을 이용해 큐를 구현한 IntQueue class를 만들어보자. 이번엔 그냥 배열이 아닌 링 버퍼라는 것을 이용할 것이다.

링 버퍼란 배열의 처음부터 시작해 순서대로 자료를 채워가다가 끝까지 가면 다시 처음으로 돌아오는 다음과 같은 구조이다.

출처 : https://www.baeldung.com/java-ring-buffer

 위 그림처럼, 만약 A B C ..... P 까지 가도 다시 A로 돌아오는 원형구조라 생각하면 편하다. 링 버퍼를 알았으니 이를 이용한 큐의 구조를 알아보자.

class IntQueue{ // int형 고정 길이 큐
    int[] que;   // 큐를 구현하기 위한 링 버퍼(배열)
    int capacity;// 큐의 용량
    int front;     // 맨 앞의 요소 커서
    int rear;    // 맨 뒤의 요소 커서
    int num;     // 현재 데이터 개수

    IntQueue(int max){
        num = front = rear = 0;
        capacity = max;
        try{
            que = new int[capacity];  // 큐 본체용 배열 생성
        }catch (OutOfMemoryError e){  // 메모리의 공간이 부족해 생성할 수 없을 때
            capacity = 0;
        }
    }
    class EmptyIntQueueException extends RuntimeException{
        EmptyIntQueueException(){}
        // EmptyIntQueueException 예외 생성
    }
    class OverflowIntQueueException extends RuntimeException{
        OverflowIntQueueException(){}
        // OverflowIntQueueException 예외 생성
    }

 다음과 같이 큐를 구현하기 위한 링 버퍼 배열 que와 큐의 용량 capacity, 큐의 앞쪽 커서 front, 뒤쪽 커서 rear, 데이터의 개수 num으로 이루어져있고 생성자를 통해 입력된 max값을 용량으로 하는 큐가 만들어진다. 그리고 예외 생성은 앞의 스택때와 같이 앞으로 메서드 생성 시 사용되기 때문에 했다. 링 버퍼로 구현하기 때문에 스택을 구현할 때보다 구성 요소가 많고 복잡하다. 

 

 생성자를 통해 큐까지 만들 수 있게 했으니 메서드를 살펴보자. (스택과 같은 메서드는 설명을 생략)

 

      - enque() : 데이터를 큐에 추가하고 출력한다.

      - deque() : 큐의 맨 첫 번째 값을 출력하고 제거한다.

      - peek() : 큐의 맨 첫 번째 값을 출력한다.

      - clear() 

      - indexOf() 

      - getCapacity() :

      - size() : 

      - isEmpty() : 

      - isFull() : 

      - dump() :  큐의 모든 값을 맨 앞부터 맨 끝까지 순서대로 출력한다.

 

 스택에서 한번 연습했으니 이번엔 메서드들을 한 번에 확인해 보자.

int enque(int x)throws OverflowIntQueueException{
    if (num>=capacity)
        throw new OverflowIntQueueException();
    // 큐가 꽉 찼으면 OverflowIntQueueException 예외 발생
    que[rear++] = x; // 큐에 데이터 x 추가
    num++;           // 데이터 개수 1 증가
    if(rear==capacity)
        rear = 0;    // 만약 rear가 index를 벗어나면 0으로 복귀
    return x ;       // 추가한 데이터 x 출력
}
int deque()throws EmptyIntQueueException{
    if (num<=0)
        throw new EmptyIntQueueException();
    // 큐가 비어있으면 EmptyIntQueueException 예외 발생
    int x = que[front++];// 큐의 맨 앞의 값 저장 후 제거
    num--;               // 데이터 개수 1 감소
    if (front == capacity)
        front = 0;       // 만약 front가 index를 벗어나면 0으로 복귀
    return x ;           // 저장했던 x 출력
}
int peek()throws EmptyIntQueueException{
    if (num<=0)
        throw new EmptyIntQueueException();
    // 큐가 비어있으면 EmptyIntQueueException 예외 발생
    return que[front]; // 큐의 맨 앞의 값 출력
}
void clear(){
    num = front = rear = 0; //큐 초기화
}
int indexOf(int x){ // x값을 찾는 선형 검색 시작
    for(int i = 0; i <num ; i++) {
        int index = (i + front) % capacity;
        // 자연스래 링버퍼 index를 순환시키는 법
        if (que[index] == x)
            return index;  // 검색 성공
    }
    return -1;  // 검색 실패
}
int getCapacity(){
    return capacity; // 큐의 용량 출력
}
int size(){
    return num; // 큐에 들어있는 데이터개수 출력
}
boolean isEmpty(){
    return num <= 0; // 큐가 비어있으면 true, 아니면 false 반환
}
boolean isFull(){
    return num >= capacity; // 큐가 가득 찼으면 true, 아니면 false 반환
}
void dump(){
    if(num <= 0)
        System.out.println("큐가 비어 있습니다.");
        // 큐가 비어있으면 메세지 출력 후 종료
    else{
        for(int i=0; i < num; i++)
            System.out.print(que[(i+front)%capacity]+" ");
        System.out.println();
    }// 큐가 안 비어있으면 큐의 front부터 rear까지의 순으로 출력
}

 스택에서 했던 거랑 크게 다르지 않지만 주의해야 할 점이 2가지 있다. 

 첫 번째는 스택에서는 ptr로 웬만하면 해결이 가능했지만 큐에서는 front, rear, num 값을 잘 컨트롤해야 한다. front나 rear 값을 고쳐놓고 num값을 수정하지 않으면 그 큐는 쓸 수 없는 큐가 된다. 두 번째는 index를 표시하는 법이다. 스택에서는 indexOf에서의 선형 검색이나 dump에서 배열의 값을 순서대로 전부 출력할 때 index의 범위는 0 ~ ptr-1까지였다. 따라서 0에서 1씩 더하여 ptr-1까지 가거나 ptr-1에서 1씩 빼서 0까지 가면 됐지만 큐에서는 좀 다르다. 링 버퍼기 때문에 시작 값이 0이 아닌 front기 때문에 배열의 끝 index로 가면 자연스레 다시 index 0으로 돌아와야 한다. 이를 구현하려면 %를 이용하여 index = (front + i)%capacity를 이용하면 된다. 여기서 i는 0부터 num-1까지 증가하는 변수이다. 이렇게 %를 이용하면 자연스레 capacity를 넘어가려는 순간 다시 0으로 돌아가 자연스레 순환할 수 있다.

 스택을 구현할 줄 알고 이 두 가지만 조심한다면 큐도 쉽게 구현할 수 있을 것이다.

 

• 실제 큐 사용 방법

실제로 큐를 사용할 때는 스택때와 마찬가지로 굳이 만들어서 사용할 필요 없이 원래 있는 Queue 클래스를 이용하면 된다. 

 

   1. Queue 선언

  Stack때와는 좀 다르게 LinkedList를 이용해 선언을 한다. 따라서  Queue와 LinkedList가 다 import 되어 있어야 사용 가능하다. 선언은 Queue<자료형> 변수 이름 = new LinkedList<>(); 로 해주면 된다.

 

   2. Queue Method

   큐 선언을 했다면 이제 메서드도 사용할 수 있다.

    변수 이름.add(x) : x를 큐에 추가한다. (큐가 꽉 차있으면 IllegalStateException 예외 발생)

    변수 이름.offer(x) : x를 큐에 추가한다.  (큐가 꽉 차있다면 false를 반환)

    변수 이름.poll() : 큐의 front 값을 반환하고 제거한다. (큐가 비어있다면 null을 반환)

    변수 이름.remove() : 큐의 front 값을 반환하고 제거한다. (큐가 비어있다면 NoSuchElementException 예외 발생)

    변수 이름.clear() : 큐를 초기화한다.

    변수 이름.peek() : 큐의 front 값을 반환한다.

  

• 덱(Deque)이란?

 덱(Deque) 이란 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력을 맨 앞 또는 맨 뒤 중 골라서 할 수 있는 양방향 대기열이다. 즉 큐와 스택을 합친 느낌이다. 덱은 따로 구현하진 않고 실제 사용하는 방법만 알아보자.

 

• 실제 덱 사용 방법

   1. Deque 선언

 덱은 큐와 마찬가지로 LinkedList를 이용해 사용하기 때문에 LinkedList까지 import해줘야한다.

선언은 Deque<자료형> 변수 이름 = new LinkedList<>(); 로 할 수 있다.

 

   2. Deque Method

  덱 선언을 했다면 이제 메서드도 사용할 수 있다

// 추가

    변수 이름.addFirst(x) : x를 덱의 맨 앞에 추가한다. (용량 초과시 예외 발생)

    변수 이름.addLast(x) : x를 덱의 마지막에 추가한다. (용량 초과시 예외 발생)

    변수 이름.offerFirst(x) :  x를 덱의 맨 앞에 추가한다. (용량 초과시 false 반환)

    변수 이름.offerLast(x) :  x를 덱의 마지막에 추가한다. (용량 초과시 false 반환)

// 삭제

    변수 이름.removeFirst() : 맨 앞의 원소 제거 후 해당 원소 반환 (덱이 비어있는 경우 예외 발생)

    변수 이름.removeLast() : 마지막 원소 제거 후 해당 원소 반환 (덱이 비어있는 경우 예외 발생)

    변수 이름.pollFirst() :  맨 앞의 원소 제거 후 해당 원소 반환 (덱이 비어있는 경우 null 반환)

    변수 이름.pollLast() : 마지막 원소 제거 후 해당 원소 반환 (덱이 비어있는 경우 null 반환)

// 확인

    변수 이름.getFirst() : 맨 앞의 원소를 반환 (덱이 비어있는 경우 예외 발생)

    변수 이름.getLast() : 마지막 원소를 반환 (덱이 비어있는 경우 예외 발생)

    변수 이름.peekFirst() : 맨 앞의 원소를 반환 (덱이 비어있는 경우 null 반환)

    변수 이름.peekLast() : 마지막 원소를 반환 (덱이 비어있는 경우 null 반환)

// 기타

    변수 이름.removeFirstOccurrence(x) : 덱의 맨 앞부터 탐색하여 x와 동일한 첫 원소를 제거

                                                                 동일한 원소가 없을 시 덱이 변경되지 않음

    변수 이름.removeLastOccurrence(x) : 덱의 마지막부터 탐색하여 x와 동일한 첫 원소를 제거

                                                                 동일한 원소가 없을 시 덱이 변경되지 않음

    변수 이름.contains(x)

    변수 이름.size()

    변수 이름.isEmpty() 

 

 

참조 : https://coding-factory.tistory.com/602