스택이란?

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 상단의 원소 확인이 O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

• LIFO(Last-in, First-Out)가 기본 원리.
• 대표 내장함수 : PUSH, PEEK, POP

자바에서 Stack 사용하기

자바에서 스택은 Stack 클래스를 구현하여 제공하고 있다.

Stack st = new Stack();

메서드

push(E item) 스텍의 맨 위에 지정된 요소를 추가합니다.
pop() 스텍의 맨 위에서 요소를 제거하고 반환합니다. 스텍이 비어 있으면 예외가 발생합니다.
peek() 스텍의 맨 위에서 요소를 반환합니다. 스텍이 비어 있으면 예외가 발생합니다.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> S = new Stack<>();
        
        // 요소 추가
        S.push(10); // 10
        S.push(20); // 10 20
        S.push(30); // 10 20 30
        
        // 스택 크기 출력
        System.out.println(S.size()); // 3
        
        // 스택이 비었는지 확인
        if (S.isEmpty()) {
            System.out.println("S is empty");
        } else {
            System.out.println("S is not empty"); // S is not empty
        }
        
        // 요소 제거 및 출력
        S.pop(); // 10 20
        System.out.println(S.peek()); // 20
        
        S.pop(); // 10
        System.out.println(S.peek()); // 10
        
        S.pop(); // 스택이 비어 있음
        
        // 스택이 비었는지 확인
        if (S.isEmpty()) {
            System.out.println("S is empty"); // S is empty
        }
    }
}

큐란?

큐의 성질
1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

• 프로그래밍에서 목록 혹은 리스트에서 접근이 양쪽에서 가능한 구조.
• FIFO(First-in, First-out)가 기본 원리.(선착순 방식 고집)

큐
큐는 대기 줄에 비유할 수 있습니다. 흔히 입국수속에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 이러한 구조를 선입선출 구조라고 한다.

자바에서 Queue 사용하기

자바에서 큐는 인터페이스로만 정의해놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 따라서 Queue 클래스 인스턴스를 생성하기 위해 Queue의 인터페이스 구현체인 LinkedList() 생성자를 호출해준다.

Queue q = new LinkedList();

메서드

offer(E e)큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 false를 반환합니다.
add() 큐의 맨 뒤에 지정된 요소를 추가합니다. 큐가 가득 차서 요소를 추가 할수 없는 경우 IllegalStateException 예외를 발생시킵니다.
poll() 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다.
peek() 큐의 맨 앞에서 요소를 반환합니다. 큐가 비어 있으면 null을 반환합니다.
clear() 큐의 모든 요소를 제거합니다.

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

public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        q.add(10); // 10
        q.add(20); // 10 20
        q.add(30); // 10 20 30
        
        System.out.println("Queue size: " + q.size()); // 큐의 크기 출력

        if (q.isEmpty()) {
            System.out.println("Queue is empty");
        } else {
            System.out.println("Queue is not empty");
        }

        q.remove(); // 20 30
        System.out.println("Front element: " + q.peek()); // 큐의 첫 번째 요소 20 출력
        System.out.println("Last element: " + ((LinkedList<Integer>) q).getLast()); // 큐의 마지막 요소 30 출력
        
        q.add(40); // 20 30 40
        q.remove(); // 30 40
        System.out.println("Front element after removal: " + q.peek()); // 큐의 첫 번째 요소 30 출력
    }
}