[JAVA] 스택(Stack)과 큐(Queue)

Stack

 

위 그림과 같이 같은 타입의 데이터를 정해진 방향으로만 쌓을 수 있고, top으로 정해진 곳을 통해서만 접근 가능한 자료 구조를 말합니다. top은 가장 최근에 들어온 데이터를 의미하며, 데이터를 추가하는 push 연산과 데이터를 제거하는 pop 연산이 있습니다. 따라서 스택은 후입선출(Last-In First-Out) 구조를 가집니다.

 

스택 활용 예제를 보면 다음과 같습니다.

- 웹 브라우저 방문 기록(뒤로 가기)

- 역순 문자열 만들기

- 실행 취소(undo)

- 후위 표기법 계산

- 수식의 괄호 검사

 

1. Array(배열)을 사용하여 스택 구현

package study;

public class StackByArray {
    private static final int MAX_STACK_NUM = 5;  // stack의 최대 크기
    private static int[] stack;  // stack으로 사용할 배열
    private static int top = -1;  // stack의 마지막을 가리키는 인덱스

    public static void main(String[] args) {
        // int 타입 데이터를 5개까지 담을 수 있는 stack
        stack = new int[MAX_STACK_NUM];

        // 숫자 1부터 5까지 stack에 추가
        for (int i = 1; i <= 5; i++) {
            push(i);
            print();
        }

        // stack의 크기를 벗어나는 경우 stack overflow
        push(6);

        // 뒤에 추가된 숫자부터 제거
        for (int i = top; i >= 0; i--) {
            System.out.println("delete num: " + pop());
            print();
        }

        // stack이 비어 있는 경우 stack underflow
        pop();
    }

    private static void push(int num) {
        // stack에 데이터가 모두 찬 경우
        if (top == MAX_STACK_NUM - 1) {
            System.out.println("Stack overflow");
            return;
        }

        // 데이터가 저장된 마지막 인덱스를 하나 증가시키고 그 위치에 데이터 저장하기
        stack[++top] = num;
    }

    private static int pop() {
        // stack이 비어 있는 경우
        if (top == -1) {
            System.out.println("Stack underflow");
            return top;
        }

        // stack에서 최신 데이터를 제거하고 최신 데이터를 가리키는 인덱스 감소
        int deleteNum = stack[top];
        top--;
        return deleteNum;
    }

    // stack에 들어있는 데이터 하나씩 출력하기
    private static void print() {
        for (int i = 0; i < top + 1; i++) {
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }
}


// 출력
// 1 
// 1 2 
// 1 2 3 
// 1 2 3 4 
// 1 2 3 4 5 
// Stack overflow
// delete num: 5
// 1 2 3 4 
// delete num: 4
// 1 2 3 
// delete num: 3
// 1 2 
// delete num: 2
// 1 
// delete num: 1
// 
// Stack underflow

 

2. LinkedList를 사용하여 스택 구현

LinkedList를 사용한 스택 구현은 이전 글에서 생성한 LinkedListManager를 사용하도록 하겠습니다.

package study;

public class StackByLinkedList {
    // LinkedList add, remove 메소드를 제공하는 manager 생성
    private static LinkedListManager stack;

    public static void main(String[] args) {
        stack = new LinkedListManager();

        // 1부터 5까지 데이터 추가
        for (int i = 1; i <= 5; i++) {
            push(i);
            stack.printListNode();
        }

        // 가장 마지막 데이터부터 삭제
        for (int i = 0; i < 5; i++) {
            pop();
            stack.printListNode();
        }

        // 스택이 비어있는 경우 stack underflow
        pop();
    }

    // LinkedList 가장 마지막에 데이터 추가
    private static void push(int num) {
        stack.add(new ListNode(num));
    }

    // LinkedList 가장 마지막 데이터 삭제
    private static int pop() {
        // stack이 비어 있는 경우 stack underflow
        if (stack.size() == 0) {
            System.out.println("stack underflow");
            return -1;
        }

        // 가장 마지막 데이터를 삭제
        ListNode deleteNode = stack.remove(stack.size() - 1);
        return deleteNode.value;
    }
}

// 출력
// 1 
// 1 2 
// 1 2 3 
// 1 2 3 4 
// 1 2 3 4 5 
// 1 2 3 4 
// 1 2 3 
// 1 2 
// 1 
// 
// stack underflow

 

LinkedListManager의 add, remove 메소드는 다음과 같습니다.

package study;

public class LinkedListManager {
    public ListNode head = null;  // LinkedList의 가장 앞에 있는 노드
    private int size = 0;  // 연결된 노드의 수

    // 노드 리스트의 가장 마지막에 노드 추가
    public void add(ListNode nodeToAdd) {
        // LinkedList에 데이터가 없는 경우
        if (head == null) {
            head = nodeToAdd;  // 가장 앞 head에 데이터를 추가
            size++;  // 연결된 노드 수 증가
            return;
        }

        // LinkedList의 마지막 데이터를 찾아서
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }

        // 마지막 데이터의 다음 노드로 추가하고 연결된 노드 수 증가
        tail.next = nodeToAdd;
        size++;
    }

    // 특정 인덱스의 데이터를 삭제
    public ListNode remove(int positionToRemove) {
        // 인덱스가 음수이거나 size 보다 큰 경우는 에러!!!!!
        if (positionToRemove < 0 || positionToRemove > size - 1) {
            // TODO: 에러 처리
            return null;
        }

        // 삭제해야 할 노드를 변수에 저장
        ListNode deleteNode = head;
        // 처음 데이터를 삭제하는 경우
        if (positionToRemove == 0) {
            head = head.next;  // head가 가리키던 node의 다음 node를 head가 가리키도록 변경
        } else {
            // 삭제하려고 하는 노드의 이전 노드를 찾아서
            ListNode before = head;
            int cnt = 1;
            while (cnt < positionToRemove) {
                before = before.next;
                cnt++;
            }

            deleteNode = before.next;  // 이전 노드가 가리키는 다음 노드를 삭제 노드 변수가 가리키도록 하고
            before.next = deleteNode.next;  // 삭제 노드가 가리키는 다음 노드를 이전 노드의 다음 노드로 지정
        }

        deleteNode.next = null;  // 삭제할 노드가 원래 가리키던 다음 노드에 대한 관계를 끊고
        size--;  // 노드가 삭제되므로 연결된 노드 수 감소
        return deleteNode;  // 삭제되는 노드 반환
    }

    // 연결되어 있는 노드의 수를 반환
    public int size() {
        return size;
    }

    // 연결된 노드들을 순서대로 출력
    public void printListNode() {
        ListNode node = head;
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }

        System.out.println();
    }
}

 

Queue

 

큐는 한쪽 끝에서 삽입 작업이 일어나고, 한쪽 끝에서는 삭제 작업이 일어나는 자료 구조를 의미합니다. 이때 삭제 연산만 일어나는 쪽을 프론트(front), 삽입 연산만 일어나는 쪽을 리어(rear)라고 합니다. 따라서 큐는 선입선출(First-In First-Out) 구조를 가집니다.

 

큐를 활용한 예제는 다음과 같습니다.

- 우선순위가 같은 작업 예약

- 은행 업무

- 콜센터 고객 대기 시간

- 프로세스 관리

- 너비우선탐색

- 캐시 구현

 

1. Array(배열)을 사용하여 큐 구현하기

package study;

import java.util.Arrays;

public class QueueByArray {
    private static final int MAX_QUEUE_SIZE = 5;  // 큐의 최대 크기
    private static int[] queue;  // 큐로 사용할 int 타입 배열
    private static int rear = -1;  // 큐에 담은 마지막 수의 인덱스

    public static void main(String[] args) {
        queue = new int[MAX_QUEUE_SIZE];  // Max 크기의 배열 생성
        Arrays.fill(queue, -1);  // 해당 큐에는 음수는 담을 수 없다는 가정하에 모두 음수로 초기화 하였습니다.

        // 1부터 5까지 수를 큐에 저장
        for (int i = 1; i <= MAX_QUEUE_SIZE; i++) {
            offer(i);
            System.out.println(Arrays.toString(queue));
        }

        // 큐가 int 배열로 선언되어 있기 때문에 최대 크기를 넘어 저장하려고 할 떄 에러
        offer(6);

        // 큐의 앞에서부터 데이터 삭제
        for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
            System.out.println(poll());
            System.out.println(Arrays.toString(queue));
        }

        // 큐에 데이터가 없는 상태에서 삭제하려고 할 때 에러
        poll();
    }

    // 큐에 데이터 추가하기
    private static void offer(int num) {
        // 큐의 최대 크기를 벗어나는 경우 추가 불가 에러
        if (rear == MAX_QUEUE_SIZE - 1) {
            System.out.println("Queue가 가득 찼습니다.");
            return;
        }

        // 큐의 마지막에 데이터를 추가하고 마지막 데이터를 가리키는 rear 증가
        queue[++rear] = num;
    }

    // 큐에서 데이터 삭제하기
    private static int poll() {
        // 큐가 비어 있는 경우 더 이상 삭제할 데이터가 없으므로 에러
        if (queue[0] == -1) {
            System.out.println("Queue가 비어있습니다.");
            return -1;
        }

        // 가장 처음 데이터를 삭제 데이터로 저장하고
        int deleteNum = queue[0];
        // 뒤에 있는 수들을 하나씩 앞으로 이동
        for (int i = 1; i <= rear; i++) {
            queue[i - 1] = queue[i];
        }

        // 데이터가 비는 부분의 값을 -1로 지정
        queue[rear--] = -1;

        return deleteNum;
    }
}


// 출력
// [1, -1, -1, -1, -1]
// [1, 2, -1, -1, -1]
// [1, 2, 3, -1, -1]
// [1, 2, 3, 4, -1]
// [1, 2, 3, 4, 5]
// Queue가 가득 찼습니다.
// 1
// [2, 3, 4, 5, -1]
// 2
// [3, 4, 5, -1, -1]
// 3
// [4, 5, -1, -1, -1]
// 4
// [5, -1, -1, -1, -1]
// 5
// [-1, -1, -1, -1, -1]
// Queue가 비어있습니다.

 

2. LinkedList를 사용하여 큐 구현하기

package study;

public class QueueByLinkedList {
    // LinkedList의 add, remove 메소드를 제공하는
    private static final LinkedListManager queue = new LinkedListManager();

    public static void main(String[] args) {
        // 1부터 5까지 큐에 저장하기
        for (int i = 1; i <= 5; i++) {
            offer(i);
            queue.printListNode();
        }

        // 큐에서 데이터 하나씩 삭제하기
        for (int i = 0; i < 5; i++) {
            poll();
            queue.printListNode();
        }

        // 큐가 비어 있는 경우 에러
        poll();
    }

    // 큐에 데이터 추가하기
    private static void offer(int num) {
        // LinkedList 마지막에 데이터 추가
        queue.add(new ListNode(num));
    }

    // 큐에서 데이터 삭제하기
    private static int poll() {
        // 큐가 비어 있는 걍우 에러
        if (queue.size() == 0) {
            System.out.println("Queue가 비어있습니다.");
            return -1;
        }

        // LinkedList에서 가장 처음 데이터 삭제
        ListNode deleteNode = queue.remove(0);
        return deleteNode.value;
    }
}


//출력
// 1 
// 1 2 
// 1 2 3 
// 1 2 3 4 
// 1 2 3 4 5 
// 2 3 4 5 
// 3 4 5 
// 4 5 
// 5 
// 
// Queue가 비어있습니다.

 

자바에서는 Stack, Queue 인터페이스를 제공하기 때문에 직접 구현할 필요없이 제공되는 인터페이스를 사용할 수 있습니다.

 

참고

devuna.tistory.com/22