Stack vs Queue

이 글은 책 알고리즘 도감에서 Stack, Queue 부분을 정리한 글입니다.

 

Stack vs Queue

Stack

데이터를 1열로 나열하지만 새롭게 추가한 데이터에만 접근

LIFO(Last in, First Out) 후입 선출 구조

단방향으로만 조작해 최신 데이터만 접근 가능

Stack

Queue

데이터를 1열로 나열, Stack 반대로 선두 데이터에만 접근.

대기행렬이라고 부르기도 함.

FIFO(First in, First Out) 선입 선출 구조.

중간 데이터 접근 X, 필요한 데이터 나올 때까지 dequeue(Queue에서 데이터 꺼내는 작업)

Queue

Queue 구현

Array로 구현

import java.util.Objects;

public class CustomQue {
    
    private final int DEFAULT_CAPACITY = 10;
    
    private int headIdx = 0;
    private int nowIdx = 0;
    
    private Object[] que = null;
    
    public CustomQue () {
        this.que = new Object[DEFAULT_CAPACITY];
    }
    
    public CustomQue (Integer capacity) {
        this.que = new Object[capacity == null ? DEFAULT_CAPACITY : capacity];
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @param obj que에 추가하려는 Element
     * @return add success return true, if not throws Exception
     */
    public boolean add (Object obj) {
        // if que is Full
        if (que.length < this.nowIdx+1) {
            if (this.headIdx != 0) {
                for (int i=this.headIdx; i<this.que.length; i++) {
                    que[i-this.headIdx] = que[i];
                }
                this.nowIdx -= this.headIdx;
                this.headIdx = 0;
            } else {
                throw new IllegalStateException("Impossible Add to Que");
            }
        }
        que[nowIdx++] = obj;
        
        return true;
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @param obj que에 추가하려는 Element
     * @return add success return true, if not return false
     */
    public boolean offer (Object obj) {
     // After add, if que is Full
        if (que.length < nowIdx+1) {
            if (this.headIdx != 0) {
                for (int i=this.headIdx; i<this.que.length; i++) {
                    que[i-this.headIdx] = que[i];
                }
                this.nowIdx -= this.headIdx;
                this.headIdx = 0;
            } else {
                return false;
            }
        }
        que[nowIdx++] = obj;
        
        return true;
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @return Head Element of the que, if que is empty throw Exception
     */
    public Object element () {
        return Objects.requireNonNull(que[this.headIdx]);
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @return Head Element of the que, if que is empty return null
     */
    public Object peek () {
        return que[this.headIdx];
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @return Head Element of the que, if que is empty throw Exception
     */
    public Object remove () {
        Object element = que[this.headIdx];
        if (element == null) throw new IllegalStateException("Que is Empty");
        
        que[this.headIdx++] = null;
        return element;
    }
    
    /*
     * @date 2021.10.03
     * @author swjeong
     * @return Head Element of the que, if que is empty return null
     */
    public Object poll () {
        Object element = que[this.headIdx];
        que[this.headIdx++] = null;
        return element;
    }

}