스택(Stack) & 큐(Queue)

스택 (Stack)이란?

스택(stack)이란 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택의 특징

스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고,
top으로 정한 곳을 통해서만 접근할 수 있다.
가장 위에 있는 자료(top)는 가장 최근에 들어온 자료를 가리키고 있으며,
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
스택에서 top을 통해 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'이라고 한다.

따라서 스택은 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 갖게 된다.
이러한 스택 구조를 후입선출(LIFO, Last-In-First-Out) 구조라 한다.

여기서 비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며,
스택이 넘치는 경우 stack overflow라고 한다.

스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 여러 분야에서 활용이 가능하다.

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

스택의 실제 사용 예시

• 자바의 Stack 메모리 영역

지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 매모리에 할당되고 종료되면 메모리가 해제된다.
LIFO(Last In First Out)구조를 갖는다.

---

큐(Queue)란?

Queue의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미한다.
따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람의 업무를 창구에서 처리하는 것과 같이
선입선출(FIFO, First in First Out) 방식의 자료구조를 말한다.

큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입이, 다른 쪽 끝에서 삭제가 양쪽으로 이루어진다.
이때 삭제연산이 수행되는 곳을 프론트(front), 삽입연산이 이루어지는 곳을 리어(rear)로 정하여
각각의 연산 작업만 수행된다.
큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
큐의 프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나갈때는 front부터 빠지는 특성
• 접근방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 프론트는 가장 먼저 큐에 들어왔던 첫 번째 원소, 리어는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

큐의 실제 사용 예시

• Queue는 OS의 스케쥴러

자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가,
그 순서를 결정하는 것이 자원의 효율적인 사용에 있고,
가장 단순한 형태의 스케쥴링 정책이 선입선처리(FCFS, First Come First Served) 즉, 큐라고 볼 수 있다.

---

Stack과 Queue 간단 예제

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackAndQueue {
    public static void main(String[] args) {
        Stack<Character> stack = new Stack<>();
        Queue<Character> queue = new LinkedList<>();

        stack.push('A');
        stack.push('B');
        stack.push('C');

        queue.offer('A');
        queue.offer('B');
        queue.offer('C');

        System.out.println("--- Stack ---");
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
        System.out.println("--- Queue ---");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

--- Stack ---
C
B
A
--- Queue ---
A
B
C

Process finished with exit code 0

---

reference : devuna.tistory.com/22