[자료구조] Stack & Queue (스택과 큐)

스택(Stack)

선형 자료구조의 일종으로 LIFO(Last In First Out) 특징을 가지고 있다. -> 나중에 들어온것이 먼저 나오고,

FILO(First In Last Out) 먼저 들어간 원소가 나중에 나온다.

차곡차곡 쌓이는 구조로 먼저 들어간 원소는 밑에 깔리게 된다.

재귀적인 특징이 있다.

• 언제 사용?

  • 함수의 콜 스택, 깊이 우선 탐색(DFS), 문자열 역순 출력, 후위 표기법, 웹 브라우저 방문 기록

• 스택의 연산

  • 삽입 : push()
  • 데이터 최상위 값삭제 : pop()
  • 비어있는지 확인 : isEmpty()
  • 꽉차있는지 확인 : isFull()

• push pop할 때는 해당 위치를 알고 있어야 하므로 SP(Stack Pointer)가 필요하다. 기본값은 -1

스택 - 자료구조 - 접기/펼치기

• 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있음 (처음 기본값은 -1)

private int sp = -1;

• push

public void push(Object o) {
    if(isFull(o)) {
    return;
    }
    stack[++sp] = o;
}

• 스택 포인터가 최대 크기와 같으면 return , 아니면 스택의 최상위 위치에 값을 넣음

• pop

public Object pop() {

    if(isEmpty(sp)) {
        return null;
    }

    Object o = stack[sp--];
    return o;

}

• 스택 포인터가 0이 되면 null로 return; 아니면 스택의 최상위 위치 값을 꺼내옴

• isEmpty

private boolean isEmpty(int cnt) {
    return sp == -1 ? true : false;
}

• 입력 값이 최초 값과 같다면 true, 아니면 false

• isFull

private boolean isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

• 스택 포인터 값+1이 MAX_SIZE와 같으면 true, 아니면 false

동적 배열 스택

• 최대 크기가 없는 스택을 만드려면?
  • arraycopy를 활용한 동적배열 사용

public void push(Object o) {
    if(isFull(sp)) {
        Object[] arr = new Object[MAX_SIZE * 2];
        System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
        stack = arr;
        MAX_SIZE *= 2; // 2배로 증가
    }

    stack[sp++] = o;
}

• 기존 스택의 2배 크기만큼 임시 배열(arr)을 만들고
• arraycopy를 통해 stack의 인덱스 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다
• 복사 후에 arr의 참조값을 stack에 덮어씌운다
• 마지막으로 MAX_SIZE의 값을 2배로 증가시켜주면 된다.

스택을 연결리스트로 구현해서도 동적 배열 구현 가능

public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Stack {
    private Node head;
    private Node top;

    public Stack() {
        head = top = null;
    }

    private Node createNode(int data) {
        return new Node(data);
    }

    private boolean isEmpty() {
        return top == null ? true : false;
    }

    public void push(int data) {
        if (isEmpty()) { // 스택이 비어있다면
            head = createNode(data);
            top = head;
        }
        else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
            Node pointer = head;

            while (pointer.next != null)
                pointer = pointer.next;

            pointer.next = createNode(data);
            top = pointer.next;
        }
    }

    public int pop() {
        int popData;
        if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
            popData = top.data; // pop될 데이터를 미리 받아놓는다.
            Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터

            if (head == top) // 데이터가 하나라면
                head = top = null;
            else { // 데이터가 2개 이상이라면
                while (pointer.next != top) // top을 가리키는 노드를 찾는다.
                    pointer = pointer.next;

                pointer.next = null; // 마지막 노드의 연결을 끊는다.
                top = pointer; // top을 이동시킨다.
            }
            return popData;
        }
        return -1; // -1은 데이터가 없다는 의미로 지정해둠.

    }

}

큐(queue)

선형 자료구조. FIFO(First In First Out) 먼저 들어간 데이터가 먼저 나온다.

스택과는 반대로 동작한다.

• 시간복잡도, 공간복잡도 : O(n)

  • 삽입 및 삭제 : O(1) -> 맨뒤에 데이터를 추가하거나, 맨앞에서 꺼내기만 하면 됌
  • 탐색 : O(n)

• 언제 사용?

  • Cache, 프로세스, 스레드 행렬, 너비우선탐색(bfs), 버퍼(buffer) 등

• 큐의 연산

  • 삽입 : enqueue()

  • 삭제 및 추출 : dequeue()

  • 비어있는지 확인 : isEmpty()

  • 꽉차있는지 확인 : isFull()

데이터를 넣고 뺄 때 해당 값의 위치를 기억해야 하므로 스택의 스택포인터와 비슷한 역할을 하는 애들이다.

• front : dequeue 할 위치를 기억하는 변수

• rear : enqueue 할 위치를 기억하는 변수

• 구현 방법

  • Array-Based : 배열을 기반으로 구현.
    • 배열을 기반으로 구현하면 인큐, 디큐 하는 과정에서 남는 메모리가 생기고 낭비가 생긴다.
    • 낭비를 줄이기 위해 Circular Queue(원형 큐) 형식으로 구현할 수 있다.
  • List-Based : Linked List 방식으로 구현하면 재할당이나 메모리 낭비를 방지할 수 있다.

Queue 구현방법 Code - 접기/펼치기

기본값

class Queue {
  private int size = 0;
  private int rear = -1;
  private int front = -1;
  private Object[] queue;

  Queue(int size) {
    this.size = size;
    this.queue = new Object[size];
  }

}

• enQueue

public void enQueue(Object o) {
    if(isFull()) {
        return;
    }
    queue[++rear] = o;
}

• enQueue 시, 가득 찼다면 꽉 차 있는 상태에서 enQueue를 했기 때문에 overflow
• 아니면 rear에 값 넣고 1 증가

• deQueue

public Object deQueue(Object o) {

    if(isEmpty()) { 
        return null;
    }

    Object o = queue[front];
    queue[front++] = null;
    return o;
}

• deQueue를 할 때 공백이면 underflow
• front에 위치한 값을 object에 꺼낸 후, 꺼낸 위치는 null로 채워줌

• isEmpty

public boolean isEmpty() {
    return front == rear;
}

• front와 rear가 같아지면 비어진 것

• isFull

public boolean isFull() {
    return (rear == queueSize-1);
}

• rear가 사이즈-1과 같아지면 가득찬 것

• 일반 큐의 단점 : 큐에 빈 메모리가 남아 있어도, 꽉 차있는것으로 판단할 수도 있음
  • (rear가 끝에 도달했을 때)

이를 개선한 것이 '원형 큐'

• 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함!

• 원형 큐는 초기 공백 상태일 때 front와 rear가 0

• 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠

• (index + 1) % size로 순환시킨다

class Queue {
  private int size = 0;
  private int rear = -1;
  private int front = -1;
  private Object[] queue;

  Queue(int size) {
    this.size = size;
    this.queue = new Object[size];
  }

}

• enQueue

public void enQueue(Object o) {
    if(isFull()) {
        return;
    }

    rear = (++rear) % size;
    queue[rear] = o;
}

• enQueue 시, 가득 찼다면 꽉 차 있는 상태에서 enQueue를 했기 때문에 overflow

• deQueue

public Object deQueue(Object o) {
    if(isEmpty()) { 
        return null;
    }
    front = (++front) % size;
    Object o = queue[front];
    return o;
}

• deQueue를 할 때 공백이면 underflow

• isEmpty

public boolean isEmpty() {
    return front == rear;
}

• front와 rear가 같아지면 비어진 것

• isFull

public boolean isFull() {
  return ((rear+1) % size == front);
}

• rear + 1 % size가 front와 같으면 가득찬 것

• 원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한

이를 개선한 것이 '연결리스트 큐'

• 연결리스트 큐는 크기가 제한이 없고 삽입, 삭제가 편리

• enqueue 구현

public void enqueue(E item) {
    Node oldlast = tail; // 기존의 tail 임시 저장
    tail = new Node; // 새로운 tail 생성
    tail.item = item;
    tail.next = null;
    if(isEmpty()) head = tail; // 큐가 비어있으면 head와 tail 모두 같은 노드 가리킴
    else oldlast.next = tail; // 비어있지 않으면 기존 tail의 next = 새로운 tail로 설정
}

• 데이터 추가는 끝 부분인 tail에 한다.
• 기존의 tail는 보관하고, 새로운 tail 생성
• 큐가 비었으면 head = tail를 통해 둘이 같은 노드를 가리키도록 한다.
• 큐가 비어있지 않으면, 기존 tail의 next에 새로만든 tail를 설정해준다.

• dequeue 구현

public T dequeue() {
    // 비어있으면
    if(isEmpty()) {
        tail = head;
        return null;
    }
    // 비어있지 않으면
    else {
        T item = head.item; // 빼낼 현재 front 값 저장
        head = head.next; // front를 다음 노드로 설정
        return item;
    }
}

• 데이터는 head로부터 꺼낸다. (가장 먼저 들어온 것부터 빼야하므로)

• head의 데이터를 미리 저장해둔다.

• 기존의 head를 그 다음 노드의 head로 설정한다.

• 저장해둔 데이터를 return 해서 값을 빼온다.

• 이처럼 삽입은 tail, 제거는 head로 하면서 삽입/삭제를 스택처럼 O(1)에 가능하도록 구현이 가능하다.

• 조금 확장한 자료구조들로는 양쪽에서 enqueue와 dequeue가 가능한 deque(double-ended queue)와
• 시간순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 priority queue가 있다

Queue 두개를 이용한 Stack - 접기/펼치기

• queue 두 개를 사용하여 stack의 push와 pop를 구현하는 것에 초점을 맞춰서 문제를 해결하면 됩니다

• 편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠습니다.
  두 개의 queue로 stack을 구현하는 방법은 다음과 같습니다.

  1. push() :: q1으로 enqueue()를 하여 데이터를 저장합니다.
  2. pop() ::
     3. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
     4. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
     5. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

• 시간복잡도

  • push() : q1.enqueue()를 한번만 하면 되기 때문에 O(1)의 시간 복잡도.
  • pop() : q1에 저장되어잇는 n개의 원소중 n-1개를 q2로 옮겨야 하므로 O(n)

Queue vs priority queue 비교 설명 - 접기/펼치기

• Queue는 먼저 집어 넣은 데이터가 먼저 나오는 선입 선출 (FIFO) 자료구조

• Priority Queue(우선순위 큐)는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

• 시간복잡도

  • Queue : enqueue - O(1), dequeue - O(1)
  • Priority Queue : Push - O(log N), Pop - O(log N)

• 우선순위 큐는 Heap으로 구현할 수 있다.

  • Heap 자료구조는 이진 완전 트리를 활용하는것.

• Heap - 링크

  • 우선순위 큐의 구현과 일치
  • 완전 이진 트리 조건
  • 힙이 되기 위한 조건
    • 각 node에 저장된 값은 child node(자식 노드)들에 저장된 값보다 작거나 같다 -> 최소힙(min heap)
      • 루트 노드가 가장 작은 값이 된다.
    • * [이미지 출처](https://dsbook.tistory.com/255)
    • 반대로 각 node에 저장된 값이 child node들에 저장된 값보다 크면 최대 힙(max heap)

​

• Heap 구현
  • 트리는 보통 Linked list로 구현
  • 그러나 Heap은 tree임에도 불구하고 배열을 기반으로 구현.
    • 새로운 노드를 힙의 마지막 위치에 추가해야 하는데 그 과정이 수월해짐.
  • 구현의 편의를 위해 보통 0번째 인덱스는 사용하지 않는다.
  • 완전 이진트리의 특성을 활용하여 배열의 index만으로 부모 자식 관계를 정의
    • n번째 node의 왼쪽 자식 노드 = 2n
    • n번째 node의 오른쪽 자식 노드 = 2n + 1
    • n번째 노드의 부모 노드 = n / 2

Stack 두개를 이용한 Queue 구현 - 접기/펼치기

• 

• 이미지 출처

#

1. inbox에 데이터를 삽입 - Push -> 순서는 A, B
2. inbox에 있는 데이터를 Pop 하여 outbox에 Push -> 순서는 B, A가 된다.
3. outbox에 있는 데이터를 pop 하면 -> A, B 순으로 나오게 된다

• A 스택에 데이터를 쌓고, Pop 하면서 B스택에 데이터를 쌓는데, B스택에서 데이터를 pop 하면 순서대로 나오게 된다.

import java.util.Stack;

/**
 * created by victory_woo on 2020/05/06
 * Stack 2개를 이용해서 Queue 구현하기.
 */
public class StackWithQueue {
    public static void main(String[] args) {
        StackQueue<String> queue = new StackQueue<>();
        queue.enQueue("A");
        queue.enQueue("B");
        queue.enQueue("C");

        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }

    static class StackQueue<T> {
        private Stack<T> inBox;
        private Stack<T> outBox;

        StackQueue() {
            inBox = new Stack<>();
            outBox = new Stack<>();
        }

        void enQueue(T item) {
            inBox.push(item);
        }

        Object deQueue() {
            if (outBox.isEmpty()) {
                while (!inBox.isEmpty()) {
                    outBox.push(inBox.pop());
                }
            }

            return outBox.pop();
        }
    }
}