[DS] Stack & Queue

1. Stack

 

스택은 선형 자료구조의 하나로 LIFO (Last In First Out) 또는 FILO (First In Last Out)라 불리는 구조로 이루어져 있다.

데이터 삽입시에 삽입되는 순서대로 스택 안에 차곡차곡 쌓이고, 출력시에는 마지막에 삽입된 데이터부터 역순으로 출력되는 식으로 데이터가 운영된다.

 

수식의 계산이나 서브 함수 실행 후의 복귀 등 재귀적인 상황에서 많이 사용한다.

 

- Stack 자바 구현

import java.util.Arrays;
import java.util.EmptyStackException;

public class CustomStack<E> {
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;

    private int size;

    public CustomStack(int size) {
        this.elementData = new Object[size];
    }

    public CustomStack() {
        this(DEFAULT_CAPACITY);
    }

    public int size() {
        return this.size;
    }

    public Object[] grow() {
        // elementData 의 크기를 두배로 늘려준다.
        return this.elementData = Arrays.copyOf(this.elementData, elementData.length * 2);
    }
    
    public E push(E item) {
        if(this.elementData.length <= this.size) {
            this.elementData = grow();
        }
        this.elementData[size] = item;
        this.size++;
        return item;
    }

    public E pop() {
        E element = peek();
        this.size--;
        this.elementData[this.size] = null;
        return element;
    }

    public E peek() {
        if(this.size == 0) {
            throw new EmptyStackException();
        }
        return elementData(this.size - 1);
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) this.elementData[index];
    }
}

 

2. Queue

큐 또한 스택 과 같이 선형 자료구조의 일종이다. 스택과는 달리 FIFO (First In First Out) 구조로 삽입된 순서대로 출력된다.

자바의 경우 주로 linked list로 구현하여 사용한다.

 

작업 실행 시에 대기 버퍼로 주로 사용한다. 실행을 기다리는 작업들이 버퍼에서 대기하다가 순서대로 작업 실행할 수 있도록 한다.

 

- Queue 자바 구현

public class CustomQueue<E> {
    private Node<E> front;

    private Node<E> rear;

    private int size;

    public CustomQueue() {}

    private static class Node<E> {
        E item;
        Node<E> next;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    public int size() {
        return this.size;
    }

    public boolean offer(E e) {
        Node<E> last = rear;
        Node<E> newNode = new Node<E>(rear, e, null);
        rear = newNode;
        if(last == null) {
            front = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    public E poll() {
        E element = peek();
        if(element != null) {
            this.size--;
            this.front = this.front.next;
        }
        return element;
    }

    public E peek() {
        if(this.size == 0) {
            return null;
        }
        return front.item;
    }
}

 

[reference]

- https://www.geeksforgeeks.org/stack-data-structure/

- https://www.geeksforgeeks.org/queue-data-structure/