스택이란?

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

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

자바에서 Stack 사용하기

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

Stack st = new Stack();

메서드

메서드 설명

empty()	Stack이 비어있는지 알려줌
비어있으면 true, 아니라면 false를 반환

peek()	Stack의 맨 위에 저장된 객체를 반환
Stack에서 객체를 꺼내지는 않음, Stack이 비었다면 null을 반환

pop()	Stack의 맨 위에 저장된 객체를 꺼냄

push()	Stack에 지정한 객체를 저장

search()	Stack에서 주어진 객체를 찾아 위치를 반환
(배열과 다르게 0이 아닌 1부터 시작)

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();

메서드

add()	지정된 객체를 Queue에 추가
성공하면 true 반환, 저장공간이 부족하면 IllegalStateException 발생

remove()	Queue에서 객체를 꺼내 반환
Queue가 비어있다면 NoSuchElementException 발생

element()	삭제없이 저장된 요소를 읽어옴
Queue가 비어있다면 NoSuchElementException 발생

offer()	Queue에 지정한 객체를 저장
성공하면 true, 실패하면 false 반환

poll()	Queue에서 객체를 꺼내 반환
Queue가 비어있다면 null 반환

peek()	삭제없이 요소를 읽어옴
Queue가 비어있다면 null 반환

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 출력
    }
}