자바(Java) - 컬렉션 프레임워크(6) (Stack)LIFO, (Queue)FIFO

Stack?

• LIFO(Last in First Out) 구조, 스택을 이용한 대표적인 예시로 JVM의 스택 메모리를 들 수 있습니다.
• 스택 메모리에 저장된 변수는 나중에 저장된 것 부터 먼저 제거 됩니다.
• 스택은 내부적으로 Vector 클래스를 상속 받아 만들어 졌습니다.
•  프로그램 내에서 메소드의 호출이 쌓이는 구조에 사용 됩니다.
• 입력과 출력이 한 곳에서만 일어납니다.

관련 메소드

1. push() : 객체를 저장 합니다.
   public E push(E item)
2. peek() : 스택 맨 위의 값 확인
3. pop() : 스택의 맨 위의 값을 추출하면서 보여줌
   public E pop() 
   ➡️ Removes the object at the top of this stack and returns that object as the value of this function.
4. empty() : 스택이 비어 있는지 확인 후 boolean으로 반환
5. size() : 스택에 포함된 객체 개수 반환(int)
6. contains(Object o) : 해당 값(Object o)이 스택 안에 있는지 boolean으로 반환
   public boolean contains(Object o)

🐶기본 예제1

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.empty());
        System.out.println(stack.size());
        System.out.println(stack.contains(1));
    }
}

3
3
false
2
true

🐶응용 예제(동전)

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Coin> coinBox = new Stack<>();
        coinBox.push(new Coin(100));
        coinBox.push(new Coin(50));
        coinBox.push(new Coin(500));
        coinBox.push(new Coin(10));
        while(!coinBox.isEmpty()) {
            Coin coin = coinBox.pop();
            System.out.println("꺼내 온 동전 : " + coin.getValue());
        }
    }
}

class Coin {
    private int value;

    public Coin(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }
}

꺼내 온 동전 : 10
꺼내 온 동전 : 500
꺼내 온 동전 : 50
꺼내 온 동전 : 100

🐶응용 예제2 (괄호)

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Character> st = new Stack<>();
        Scanner sc = new Scanner(System.in);
        System.out.print("수식 입력 : ");
        String exp = sc.next();
        for(int i = 0; i < exp.length(); i++) {
            char ch = exp.charAt(i);
            if (ch == '(') { // 열림 괄호일 때 push
                st.push(ch);
            } else if (ch == ')') { // 닫힘 괄호일 때
                if (!st.isEmpty()) st.pop(); // stack이 비어있지 않으면 pop
                else {
                    System.out.println("괄호가 일치하지 않습니다.");
                    return;
                }
            }
        }
        if(st.isEmpty()) {
            System.out.println("괄호가 일치 합니다.");
        } else {
            System.out.println("괄호가 일치 하지 않습니다.");
        }
    }
}

수식 입력 : ((3+4)*6)
괄호가 일치 합니다.

수식 입력 : ((3+4) *6))
괄호가 일치 하지 않습니다.

Queue?

• FIFO(First In First Out) 구조
• LinkedList 구조를 사용하고 있으며, LinkedList 기능 중 Queue 관련 기능으로 제한됨

관련 메소드

Summary of Queue methods

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

(1) Parameters: e

    the element to add

💡 In a FIFO queue, all new elements are inserted at the tail of the queue.

1. add(e) : 맨 뒤 위치에 요소를 삽입(중간 삽입 X) - 예외 발생
   ✅ Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
2. offer(e) : 맨 뒤 위치에 요소를 삽입
   ✅ The offer method inserts an element if possible, otherwise returning false.
   ✅ The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.

(2) Retrieves and removes the head of this queue.

    return the head of this queue

1. remove() - 비어있으면 예외 발생
2. poll() - 비어있으면 null 반환

💡The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

 

(3) Retrieves, but does not remove, the head of this queue.

    return the head of this queue

1. element() - 맨 앞의 요소를 읽어옴 - 예외 발생
   ✅ This method differs from peek only in that it throws an exception if this queue is empty.
2. peek() - 맨 앞의 요소를 읽어옴 - 비어 있으면 null 반환
   ✅ the head of this queue, or null if this queue is empty

🐶기본 예제1

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

public class Main {
    public static void main(String[] args) {
        Queue<Message> msgQ = new LinkedList<>();
        msgQ.offer(new Message("Mail", "홍길동"));
        msgQ.add(new Message("SMS", "한석봉"));
        msgQ.offer(new Message("Kakao", "오재미"));
        while(!msgQ.isEmpty()) {
            Message msg = msgQ.poll(); // 큐에서 한개의 메시지를 꺼냄(맨앞)
            switch(msg.command) {
                case "Mail" : System.out.println(msg.to + "에게 메일을 보냅니다."); break;
                case "SMS" : System.out.println(msg.to + "에게 문자를 보냅니다."); break;
                case "Kakao" : System.out.println(msg.to + "에게 카카오톡을 보냅니다."); break;
            }
        }
    }
}

class Message {
    String command;
    String to;

    public Message(String command, String to) {
        this.command = command;
        this.to = to;
    }
}

홍길동에게 메일을 보냅니다.
한석봉에게 문자를 보냅니다.
오재미에게 카카오톡을 보냅니다.

🐶응용 예제(명령 이력 조회)

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

public class Main {
    Queue<String> queue = new LinkedList<>();
    final static int MAX_SIZE = 10;

    public static void main(String[] args) {
        Main history = new Main();
        System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");
        while(true) {
            System.out.print("$ ");
            Scanner sc = new Scanner(System.in);
            String cmd = sc.nextLine().trim(); // 입력 받은 문자열의 앞뒤의 공백 제거
            if(cmd.equalsIgnoreCase("q")) {
                System.exit(0); // 프로그램 강제종료 (return 보다 강력)
            } else if(cmd.equalsIgnoreCase("help")) {
                System.out.println("help - 도움말을 보여줍니다.");
                System.out.println("q/Q - 프로그램 종료");
                System.out.println("history - 최근 입력한 명령어를 " + MAX_SIZE + "개 보여줍니다.");
            } else if(cmd.equalsIgnoreCase("history")) {
                history.save(cmd);
                int cnt = 0;
                for(String e : history.queue) {
                    cnt++;
                    System.out.println(cnt + " " + e);
                }
            } else {
                history.save(cmd);
                System.out.println(cmd);
            }
        }
    }
    void save(String cmd) {
        queue.offer(cmd);
        if(queue.size() > MAX_SIZE) queue.remove(); // 큐의 개수가 넘어가면 맨 앞의 요소 제거
    }
}