자료구조 - 스택과 큐

스택(Stack)

---

스택(Stack)은 삽입과 삭제 연산이 후입선출(LIFO, Last In First Out)로 이루어진 선형 자료구조이다.

가장 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조로 삽입과 삭제가 한쪽에서만 일어난다.

- 스택은 DFS(깊이 우선 탐색), 백트레킹 종류의 코딩 테스트에 사용된다. 

햄버거

요리를 배웠던 기억을 되살려 햄버거를 가지고 스택을 표현해보려고 한다.

우리가 햄버거를 만든다고 상상해보자.

햄버거 재료들을 차곡차곡 쌓아서 맛있게 만들었지만, 만약 중간에 들어갈 토마토를 까먹었다고 하면 어떻게 해야 될까?

토마토가 위치해야 되는 자리까지 위에서부터 하나씩 뺄 것이다. 빵에서부터 치즈까지 빼고 난 후 토마토를 다시 쌓고 뺏던 재료들을 다시 쌓는다.

 

스택에서 사용되는 주요 메서드

- top(): 삽입과 삭제가 일어나는 위치를 뜻하며 스택의 가장 최상위 요소를 반환해 준다.

- push(): top위치에 새로운 데이터를 삽입하는 연산이다.

- pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.

- peek(): top 위치에 현재 있는 데이터를 단순 확인하는 연산

- isEmpty(): 현재 스택이 비어있는지 확인하는 연산으로 비어 있으면 true, 그렇지 않으면 false를 반환해 준다.

 

코드로 보는 스택 자료구조

---

import java.util.Arrays;

public class MyStack<E> {
    private Object[] stack;
    private int top = -1;
    private final int DEFAULT_SIZE = 5;

    public MyStack() {
        this.stack = new Object[DEFAULT_SIZE];
    }

    public MyStack(int stackSize) {
        this.stack = new Object[stackSize];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public E peek() {
        if (top == -1) {
            return null;
        } else {
            return (E)stack[top];
        }
    }

    public void push(E value) {
        if (!isFull()) {
            top++;
            stack[top] = value;
        } else {
            stack = Arrays.copyOf(stack, stack.length + DEFAULT_SIZE);
            top++;
            stack[top] = value;
        }
    }

    public E pop() {
        if (isEmpty()) {
            return null;
        } else {
            E topValue = (E)stack[top];
            top--;
            stack = Arrays.copyOf(stack, stack.length - 1);
            return topValue;
        }
    }

    public void display() {
        for (int i = 0; i <= top; i++) {
            System.out.print("[" + stack[i] + "]");
        }
        System.out.println();
    }

    public int size() {
        return stack.length;
    }
}

 

스택 자료구조를 구현해 본 코드이다.

코드에서 핵심을 살펴보자.

아무런 초기값을 설정하지 않고 스택을 생성한다면 DEFAULT_SIZE로 5를 설정해서 생성자를 통해 스택이 생성되게 구현했다.

배열은 Object로 설정했는데 그 이유는 스택으로 들어오는 값이 어떤 데이터 타입을 가질지 모르기 때문이다.

push, pop, peek 메서드들은 제네릭을 사용하여 타입 변수로 지정된 데이터 타입을 매개변수로 받거나, 반환하게 구현하였다.

여기서 중요하게 봐야 되는 부분은 push와 pop 메서드인데 데이터를 삽입하거나 삭제하는 연산을 어느 한쪽만 반복해서 한다면 스택이 꽉 차는 경우 혹은 비어 있는 경우가 발생할 수 있다. 이때 배열을 사용하기 때문에 배열의 특징을 고려하여 copyOf 메서드를 사용해 길이를 늘여주었다.

스택에서 마지막으로 삽입된 데이터의 위치를 확인할 수 있는 top 변수는 처음에 -1로 설정하였다. 스택에 데이터가 들어가게 된다면 배열에서 0번째부터 들어가기 때문에 비어있을 경우 -1로 설정하여 인덱스 문제가 발생하지 않도록 설정하였다.

 

스택 자료구조의 장단점

장점

1. 단순성

스택의 개념을 살펴보면 컴퓨터에 대한 지식이 전무한 사람도 쉽게 이해할 수 있다. 물론 스택을 어디서 사용하느냐는 모를 수 있겠지만 핵심이라 할 수 있는 후입선출 개념은 쉽게 이해가 가능하다.

 

2. 효율성

스택에서 사용되는 연산 중에서 데이터를 삽입 및 삭제하는 push()와 pop() 연산은 O(1)의 시간 복잡도를 가지게 된다. 따라서 데이터에 대한 효율적인 액세스를 제공한다.

 

3. 제한된 메모리 사용량

스택 자료구조에서는 push() 연산을 통해 삽입된 데이터만 저장하게 된다. 한 마디로 특정 데이터를 넣기 위해서 다른 불필요한 데이터를 추가로 삽입되는 것 없이 원하는 데이터만 스택에 저장할 수 있다.

 

단점

1. 제한된 액세스

스택 자료구조는 후입선출 구조로 이뤄지기 때문에 항상 top 위치에 해당하는 데이터에만 접근이 가능하다. 따라서 사용자가 원하는 데이터를 얻기 위해서는 pop() 연산을 반복적으로 해야 되는 불필요한 작업이 발생한다.

 

2. overflow 가능성

스택이 저장할 수 있는 크기 보다 더 많은 양의 데이터가 push()되면 더 이상 저장하지 못하고 overflow 오류가 발생하게 된다.

예를 들어 스택의 사이즈가 5라고 가정했을 때 사용자가 1 ~ 6까지의 정수 데이터를 push()하게 되면 1 ~ 5까지만 저장되고 나머지 6은 손실되게 된다.

 

3. 무작위 액세스에 적합하지 않음

1번과 비슷한 이유로 스택은 데이터를 탐색하려면 항상 top의 위치에서부터 시작되어야 하기 때문에 무작위 액세스를 허용하지 않는다.

 

스택은 주로 어디에 사용될까?

1. 웹 브라우저의 앞, 뒤로 가기 기능

2. 프로그램이 실행되기 위해서는 메모리에 올라가야 되는데 이때 스택을 사용한다.

3. 함수 호출을 구현하는데 도움이 된다. 마지막으로 호출된 함수는 항상 먼저 완료돼야 한다.

 

큐(Queue)

---

큐(Queue)는 삽입과 삭제 연산이 선입선출(FIFO, First In First Out)로 이루어진 선형 자료구조이다.

처음으로 삽입되는 요소가 가장 먼저 삭제되는 구조로 한쪽에서는 삽입이 이루어지고, 다른 한 쪽에서는 삭제가 이루어진다.

컨베이어 벨트

전공으로 요리를 배울 때 가장 먼저 재고관리에 관해서 배웠다.

식당에서도 식자재를 관리할 때 FIFO 방식을 많이 사용한다.

보통의 가정집에서도 식재료를 구매하면 유통기한이 얼마 안 남은 것을 앞에 둬서 먼저 소비하고, 방금 산 재료는 맨 뒤로 배치시킬 것이다.

지금 공부하는 큐도 마찬가지로 먼저 들어온 데이터는 먼저 처리되고, 이제 막 들어온 데이터는 마지막에 위치한다.

 

큐의 연산들

- rear(): 큐에서 가장 끝을 가리키는 연산으로 가장 마지막에 삽입된 데이터를 반환해 준다.

- front() : 큐에서 가장 앞의 데이터를 가리키는 연산으로 가장 처음에 삽입된 데이터를 반환해 준다.

- add() : rear 부분에 새로운 데이터를 삽입하는 연산이다.

- poll() : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.

- peek() : 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산이다.

- isEmpty(): 큐가 비어 있는지 확인하는 연산이다.

 

코드로 보는 큐 자료구조

---

public class MyQueue<E> {
    private Object[] queue;
    private int front = 0;
    private int rear = 0;
    private final int DEFAULT_SIZE = 5;

    public MyQueue() {
        this.queue = new Object[DEFAULT_SIZE];
    }

    public MyQueue(int stackSize) {
        this.queue = new Object[stackSize];
    }

    public boolean isEmpty() {
        System.out.println("비어 있음");
        return front == rear;
    }

    public boolean isFull() {
        System.out.println("가득 차 있음");
        return rear == queue.length;
    }

    public E peek() {
        if (isEmpty()) {
            return null;
        } else {
            return (E)queue[front];
        }
    }

    public void add(E value) {
        if (!isFull()) {
            queue[rear] = value;
            rear++;
        } else {
            resize(value);
        }
    }

    public E pool() {
        if (isEmpty()) {
            return null;
        } else {
            E frontValue = (E) queue[front];
            queue[front] = null;
            front++;
            return frontValue;
        }
    }

    public void display() {
        for (int i = front; i < rear; i++) {
            System.out.print("[" + queue[i] + "]");
        }
        System.out.println();
    }

    public int size() {
        return queue.length;
    }

    private void resize(E value) {
        rear /= front;

        queue[rear] = value;
    }
}

코드로 구현해 본 큐 자료구조를 살펴보면 데이터 삽입과 삭제 외에는 스택과 비슷하다.

큐는 스택과 다르게 FIFO 구조로 되어있기 때문에 맨 앞에 위치한 데이터부터 차례대로 삭제된다. 그렇기 때문에 큐의 앞부분을 확인할 수 있는 front 변수와 가장 끝 부분을 확인하는 rear 변수를 설정해줘야 한다.

최초에 둘 다 0으로 저장하고 데이터가 add 되면 rear의 위치를 한 칸씩 이동시킨다. 그 후 poll 메서드가 실행되면 front에 위치한 데이터를 가져와서 임시 변수에 저장시킨다. 그리고 front에 위치한 데이터를 삭제해 주고 front의 위치를 한 칸 이동시켜 주게 된다.

resize 메서드는 큐가 가득 찼다면 rear의 위치를 갱신하고 해당 위치에 받아온 데이터를 다시 넣어주는 기능으로 원형 큐를 고려하여 만들어본 기능이다.

 

큐의 장단점

장점

1. 데이터 삽입 및 삭제 연산이 빠르다.

스택 자료구조와 마찬가지로 데이터를 삽입하거나 삭제 연산의 시간 복잡도가 O(1)이므로 빠르다.

2. 데이터를 받는 순서대로 저장된다.

데이터를 순서대로 받아서 저장한다는 것이 스택과 똑같다고 느낄 수 있지만, 반대로 저장한 데이터를 다시 꺼낸다고 생각을 해보면 스택은 순서가 반대로 바뀌게 되고 큐는 처음 저장된 순서를 지킬 수 있다.

 

단점

1. 큐의 빈 메모리가 남은 메모리가 있어도 rear의 위치에 따라 큐가 가득 차 있는 것으로 판단할 수 있다.

FIFO 구조로 인하여 큐에서는 데이터를 삭제할 때 항상 front 위치에 있는 데이터를 삭제하게 된다. 하지만 큐가 가득 찼다는 것은 rear의 위치로 판단하기 때문에 삭제된 곳의 빈 메모리가 존재하지만 데이터를 더 이상 삽입할 수 없는 상황이 발생할 수 있다.

 

2. 요소를 검색하는데 O(N)이 걸린다.

특정 데이터를 찾기 위해서는 큐에 저장된 모든 데이터를 순회하면서 찾기 때문에 비효율적이다.

 

큐는 주로 어디서 사용될까?

1. 순서가 중요한 대기열 시스템에서 사용된다.

2. 대기열 시스템과 비슷하게 프로세스 스케줄링에서 사용된다.