1. Stack

데이터 삽입 : push
데이터 최상위 값 빼기 : pop
비어있는 지 확인 : empty
꽉 차있는지 확인 : isFull

• 입력과 출력이 한 곳으로 제한된 자료구조
• LIFO(Last In First Out, 후입선출)

Stack이 쓰이는 곳

• 웹페이지 뒤로가기
• 후위 표기법 계산
• 스택 메모리
• DFS
• 역순 문자열 생성

🎯JAVA 코드로 보는 stack의 함수

+)

private int sp = -1; // 스택 포인터(sp)는 기본값이 -1

1) push

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

2) pop

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

3) isEmpty

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

4) isFull

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

+) 위처럼 Array이외의 Linked List나 arraycopy를 활용하면 동적 배열 스택을 만들 수도 있다.

2. Queue

데이터 삽입 : enQueue
데이터 빼기 : deQueue
비어있는 지 확인 : isEmpty
꽉 차있는지 확인 : isFull

• 입력과 출력이 한 쪽 끝(front, rear)으로 제한된 방식
• FIFO(First In First Out, 선입선출)
• 들어올 때가 rear, 나올 때는 front부터 빠지기

Queue가 쓰이는 곳

• 버퍼
• BFS
• 줄서기
• FCFS (프로세스 스케줄링 방식 중 하나)

🎯JAVA 코드로 보는 Queue의 함수

+)

// 기본값
private int size = 0; 
private int rear = -1; 
private int front = -1;

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

1) enQueue

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

2) deQueue

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

3) isEmpty

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

4) isFull

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

+) rear가 끝에 도달하기만 해도 Full상태로 되기 때문에 원형 큐를 이용하면 해결할 수 있다.

원형 큐: 배열의 처음과 끝이 연경되어 있는 것으로 간주한 자료구조

// (index + 1) % size로 순환시킨다
public boolean isFull() {
    return ((rear+1) % size == front);
}