스택과 큐(Stack & Queue)

1. 스택

• 스택(Stack) : LIFO(Last int first out)구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
• 스택은 늦게 들어온 값을 먼저 빼내는 구조로 배열에 적합하다.
• Stack 클래스를 호출하여 사용

  

메서드

2. 큐

• 큐(Queue) : FIFO(First in first out)구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
• 큐는 먼저 들어온 것을 먼저 빼내야 하므로 배열을 사용하면 빈 공간을 다시 채워넣어야 하므로 비효율적이므로 LinkedList가 적합하다.
• 큐는 인터페이스로 구현되어 있기때문에 호출이 불가능 즉, 큐 인터페이스를 상속받은 클래스를 호출하여 사용

  

메서드

스택/큐 간단 예제

    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList(); // Queue인터페이스의 상속을 받은 클래스

        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)	수식계산, 수식괄호검사, 웹브라우저 뒤로/앞으로 즉, 이전 실행값을 호출할 때 사용
큐(Queue)	최근사용문서, 인쇄작업 대기목록, 버퍼 즉, 최근 작업문서의 리스트 처럼 최근 값 리스트 구할 때 사용

스택 활용예제(괄호 구분)

  public static void main(String[] args) {
      Stack st = new Stack();
      String expression = "((3+5)*8-2";

      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("괄호가 일치하지 않습니다.");
      }
  }

큐 활용예제(이전 입력값 리스트 출력)

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

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

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

        while(true){
            System.out.println(">>");
            try{
                Scanner s = new Scanner(System.in);
                String input = s.nextLine().trim(); // trim() 문자열 공백 제거

                if("".equals(input))
                    continue;
                if(input.equalsIgnoreCase("q")){  // equalsIgnoreCase() 대소문자 구분 안함
                    System.exit(0);
                }else if(input.equalsIgnoreCase("help")){
                    System.out.println("help - 도움말을 보여줍니다.");
                    System.out.println("q 또는 Q - 프로그램을 종료합니다");
                    System.out.println("history - 최근에 입력한 명령어를"+MAX_SIZE+"개 보여줍니다.");
                }else if(input.equalsIgnoreCase("history")){
                    save(input);

                    LinkedList list = (LinkedList)q;

                    for(int i =0; i<list.size(); i++){
                        System.out.println((i+1)+"."+list.get(i));
                        }
                }else{
                    save(input);
                    System.out.println(input);
                }
            }catch (Exception e){
                System.out.println("입력오류 입니다.");
            }
        }
    }
    public static void save(String input){
        if(!"".equals(input))   // 공백이 아니라면
            q.offer(input);     // 큐에 추가한다

        if(q.size()>MAX_SIZE)   // 큐의 크기가 5초과할경우
            q.remove();         // 큐의 제일 먼저 들어온 값 제거한다
    }
}

출처 : 자바의 정석