💡Stack<E> 클래스

---

✔️ Stack 클래스

• List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공

스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료 구조이다.

즉, 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조이다.

Stack을 좀 더 알아보자.

📎 Stack

✔️ Stack
: LIFO(Last In First Out)구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

위에 그림을 보면서 상자가 하나 있다고 생각해보자.

여기에 0이라는 물건을 먼저 넣고 1을 넣고 2을 넣었다. 먼저 넣은게 바닥에 깔리고 그 다음 차곡차곡 쌓여질 것이다.

그리고 꺼낼때는 마지막에 넣었던 물건 2부터 꺼내게 된다.

✔️ 저장(push)
: 0 ➡️ 1 ➡️ 2

✔️ 추출(pop)
: 2 ➡️ 1 ➡️ 0

Stack과 Queue는 컴퓨터에서 가장많이 활용되는 기본적인 구조이다.
여러곳에서 활용도가 젤 높은 것이 Stack이다.

📎 Stack의 메서드

✏️ boolean empty()

• Stack이 비어있는지 알려준다.

✏️ Object peek()

• Stack의 맨 위에 저장된 객체를 반환한다. (맨 위에 뭐가 있는지 보는 것)
• pop()과 달리 Stack에서 객체를 꺼내지는 않는다.
• 비었을 때는 EmptyStackException 발생

✏️ Object pop()

• 삭제
• Stack의 맨 위에 저장된 객체를 꺼낸다.
• 비었을 때는 EmptyStackException 발생

✏️ Object push(Object item)

• 추가
• Stack에 객체(item)를 저장한다.

✏️ int search(Object o)

• Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다.
• 못찾으면 -1을 반환한다.
• 배열과 달리 위치는 0이 아닌 1부터 시작한다.

💡Queue 인터페이스

---

✔️ Queue 인터페이스

• 클래스로 구현된 스택과는 달리 자바에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다.

이러한 Queue 인터페이스를 상속받는 하위 인터페이스는 다음과 같다.

1. Deque<E>
2. BlockingDeque<E>
3. BlockingQueue<E>
4. TransferQueue<E>

이 중에서 Deque 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는 데 가장 많이 사용된다.

✔️ Queue 인터페이스를 구현한 class들

Queue는 인터페이스이기 때문에 객체 생성을 할 수 없다.
따라서 Queue 인터페이스를 구현한 class들을 활용해야 한다.

이중에 우리에게 익숙한 LinkedList 가 있다. 이 class를 써서 Queue의 기능을 활용할 수 있다.

Queue q = new LickedList();
g.offer("0");

Queue에 대해서 좀 더 자세히 알아보자.

📎 Queue

✔️ Queue
: FIFO(First In First Out)구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

위에 사진을 보듯이 이것은 줄서기라고 생각하면 된다.

계산대에 줄을 설때 먼저 선 사람이 먼저 하듯이 이 구조도 마찬가지이다.

저장할때도 0, 1, 2 순으로 저장했다면 꺼낼때도 0, 1, 2 순으로 꺼내진다.

✔️ 저장(offer)
: 0 ➡️ 1 ➡️ 2

✔️ 추출(poll)
: 0 ➡️ 1 ➡️ 2

📎 Queue의 메서드

✏️ boolean add(object o)

• 추가
• 지정된 객체를 Queue에 추가한다.
• 성공하면 true를 반환한다.
• 저장공간이 부족하면 IllegalStateException 발생

✏️ Object remove()

• 삭제
• Queue에서 객체를 꺼내 반환한다.
• 비어있으면 NoSuchElementException 발생

✏️ Object element()

• 삭제없이 요소를 읽어온다.
• peek와 달리 Queue가 비었을 때 NoSuchElementException 발생

✏️ boolean offer(Object o) ⭐️

• 추가
• Queue에 객체를 저장한다.
• 성공하면 true, 실패하면 false를 반환한다. (예외발생 X)

✏️ Object poll() ⭐️

• 삭제
• Queue에서 객체를 꺼내서 반환한다.
• 비어있으면 null을 반환한다. (예외발생 X)

✏️ Object peek() ⭐️

• 삭제없이 요소를 읽어온다.
• Queue가 비어있으면 null을 반환한다.

💡 Stack과 Queue 활용

---

❓ 배열과 LinkedList중에 뭐가 더 적합할까

✔️ Stack: 배열

• 순차적으로 저장되고 추출할때도 순차적으로 뒤에서 나가기 때문

✔️ Queue: LinkedList

• 저장하는 것을 배열을 해도 상관없겠지만 꺼낼때가 문제이다.
• index[0]부터 꺼내지기 때문에 배열을 쓰게 된다면 나머지 뒤에 있는 데이터가 다 이동을 해야되기 때문에 비효율적이다.
• 반면 LinkedList는 자리이동이 필요없기 때문에 삭제할 때 더 효율적이다.

✏️ 예시

public class StackAndQueue {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList(); // Queue인터페이스의 구현체인 LinkedList

        st.push("0");
        st.push("1");
        st.push("2");

        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println("==Stack==");
        while(!st.empty()) {
            System.out.println(st.pop()); // 스택에서 요소를 하나하나 꺼냄
        }
        System.out.println("==Queue==");
        while(!q.isEmpty()) {
            System.out.println(q.poll()); // 큐에서 요소를 하나하나 꺼냄
        }

    }
}

==Stack==
2
1
0
==Queue==
0
1
2

---

✔️ Stack의 활용 예

• 수식계산
• 수식괄호검사
• 워드프로세서의 undo / redo
• 웹브라우저의 뒤로 / 앞으로

✔️ Queue의 활용 예

• 최근 사용 문서
• 인쇄작업 대기목록
• 버퍼(buffer): 작업이 쌓임

✏️ 알맞는 괄호 판단 예제_Stack

import java.util.*;

public class StackTest {
    public static void main(String[] args) {

       Stack st = new Stack();
       Scanner sc = new Scanner(System.in);
       
       System.out.println("수식을 적으시오: ");
       String expression = sc.next();

        System.out.println("expression" + expression);

        try {
            for(int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);

                if(ch == '(') {
                    st.push(ch + "");
                } else if (ch == ')') {
                    st.pop();
                }
            }
            if(st.isEmpty()) {
                System.out.println("괄호가 일치합니다.");
            } else {
                System.out.println("괄호가 일치하지 않습니다.");
            }
        } catch (EmptyStackException e) {
            System.out.println("괄호가 일치하지 않습니다. Exception");
        }
    }
}

✏️ Queue를 활용한 최근 사용문서 예제

import java.util.*;

public class QueueTest {
    static Queue q = new LinkedList();
    static final int MAX_SIZE = 5;

    public static void save(String input) {
        // Queue에 저장한다.
        if(!"".equals(input)) { // if(input == null && !input.equals(""))
            q.offer(input);
        }
        // Queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제한다.
        if(q.size() > MAX_SIZE) {
            q.remove();
        }
    }

    public static void main(String[] args) {
        System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");

        // 무한반복을 일으켜서 입력을 시킴
        while(true) {
            System.out.println(">>");
            try{
                Scanner sc = new Scanner(System.in);
                String input = sc.nextLine().trim(); // 앞뒤 공백 없앰

                if("".equals(input)) {
                    continue; // 아예 빠져나와서 반복문 while부터 다시 시작
                }
                if(input.equalsIgnoreCase("q")) {
                    System.exit(0);
                } else if(input.equalsIgnoreCase("help")) {
                    save(input);
                    System.out.println("help - 도움말을 보여줍니다.");
                    System.out.println("q 또는 Q - 프로그램을 종료합니다.");
                    System.out.println(
                            "history - 최근에 입력한 명령어를 " + MAX_SIZE + "개를 보여줍니다."
                    );
                } else if (input.equalsIgnoreCase("history")) {
                    // 입력받은 명령어 저장
                    save(input);

                    // LinkedList의 내용을 보여준다.
                    LinkedList list = (LinkedList) q;

                    //list.size는 바뀌지 않으므로 상수로 둔다. (반복횟수가 많을 수록 이렇게 둬야 한다.)
                    final int SIZE = list.size();
                    for(int i = 0; i < SIZE; i++)
                        System.out.println((i + 1) + ". " + list.get(i));
                } else {
                    save(input);
                    System.out.println(input);
                }
            } catch (Exception e) {
                System.out.println("입력오류입니다.");
            }
        } // while end
    }
}

help를 입력하면 도움말을 볼 수 있습니다.
>>
help
help - 도움말을 보여줍니다.
q 또는 Q - 프로그램을 종료합니다.
history - 최근에 입력한 명령어를 5개를 보여줍니다.
>>
history
1. help
2. history
>>
hello
hello
>>
hi
hi
>>
oh!
oh!
>>
history
1. history
2. hello
3. hi
4. oh!
5. history
>>
q

---

References
: https://cafe.naver.com/javachobostudy