Stack 과 Queue의 활용 (스택 / 큐)

ch11 - 19 ~ 21 스택과 큐 의 활용 (Stack & Queue)

 

[ 스택 ]

 

 

스택의 활용 예

 

1) 수식 계산

( (3 + 2) * 8 ) / 2

 

2) 수식 괄호 검사

 

3) 워드프로세서의 undo / redo (작업한것을 취소 / 직전 행동을 되돌리기)

 

4) 웹 브라우저의 뒤로 / 앞으로

 

 

첫 방문을 구글을 했다고 하고,

그 다음 방문을 네이버,

그 다음은 다음을 방문 했다고 치면,

 

스택의 그림은 아래와 같을것이다.

 

 

근데 이때, 웹 브라우저 에서 뒤로가기를 누르면 어떻게 될까 ?

 

또 하나의 스택을 사용 해서, 다음을 새로운 스택에 옮긴다.

 

그러면 현재 페이지가 네이버 가 될것 이고,

 

여기서 만약에 앞으로 가기 버튼을 누르면 새로운 스택 으로 옮긴

다음을 기존 스택에 다시 옮기는 개념 이다.

 

 

근데 사실은 스택 한개로만 사용 하고, 현재를 가리키는 " 포인터 " 라는 개념을 사용 한다.

 

하지만 그림으로 나타내기 위해서 위와 같이 표현 했다.

 

그렇지만 위의 그림 처럼 스택 두개를 사용 해서 구현 해도 되긴 하지만,

 

" 포인터 " 개념을 사용하는게 효율적이기 때문에 스택 1개와 포인터 개념을 사용 한다.

 

 

 

[ 큐 ]

 

 

큐의 활용 예

 

1) 최근 사용 문서

 

 

최근 사용 문서를 임시로 저장해줌으로써, 문서 작업을 편리하게 도와주는 기능이 있다.

 

하지만, 최근 사용 문서 개수를 무제한으로 할 수는 없고, 5개나 7개 정도로 해서 보여준다.

 

만약에 1부터 5개의 최근 파일 목록이 있는데, 새로운 파일을 열게 되면,

 

제일 오래된 파일을 추출 (제거) 하게 된다.

 

즉, 1번 파일을 제거 한다.

 

2, 3, 4, 5, 6 파일만 남게 된다.

 

 

2) 인쇄 작업 대기 목록

 

3) 버퍼 (buffer)

 

 

 

예제 01 )

 

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()) {	//	괄호가 일치하다는것은, 여는 괄호와 닫는 괄호의 개수가 동일 하고, 1 대 1 이라는 말이 된다. (비어있는 스택)
            System.out.println("괄호가 일치합니다.");
        } else {
            System.out.println("괄호가 일치하지 않습니다.");	//	스택이 비어있지 않으면 괄호가 일치 하지 않음.
        }
    } catch (EmptyStackException e) {

        //	여는 괄호보다 닫는 괄호가 더 많으면 그 만큼 더 맨 위에 저장된 객체를 꺼내야 하는데, 꺼낼 객체가 없어서 예외가 발생 한다.

        System.out.println("괄호가 일치하지 않습니다. EmptyStackException 발생 !");

    }	//	try

}

 

String expression = "((3 + 5) * 8 - 2)";

 

( 

여는 괄호의 개수가 총 2개 이고,

 

)

닫는 괄호의 개수가 총 2개 이다.

 

expression :((3 + 5) * 8 - 2)

괄호가 일치합니다.

 

 

결과는 위와 같다.

 

만약에, 

 

String expression = "(((3 + 5) * 8 - 2)";

 

(

여는 괄호의 개수가 닫는 괄호의 개수보다 한개 라도 많게 되면,

 

스택에 ( 를 한개 이상 더 저장 하게 되고,

 

그러면 

 

if (st.isEmpty())

 

이 조건이 일치 하지 않으니까 ( 안 비어 있으니까 )

 

expression :(((3 + 5) * 8 - 2)

괄호가 일치하지 않습니다.

 

 

괄호가 일치 하지 않는다고 결과를 보여 준다.

 

마지막으로,

 

String expression = "((3 + 5) * 8 - 2)))";

 

위와 같이 닫는 괄호의 개수가 더 많으면 어떻게 될까 ?

 

스택에는 여는 괄호가 2개 니까 ( 가 2개 저장 되고,

 

닫는 괄호가 총 4개 니까 4번을 추출 하게 된다.

 

근데, ( 를 2개 빼고 나서, 2번을 더 추출 해야 하는데,

 

추출할 ( 가 없어서 예외를 반환 하게 된다.

 

expression :((3 + 5) * 8 - 2)))

괄호가 일치하지 않습니다. EmptyStackException 발생 !

 

 

 

예제 02 )

 

import java.util.*;

class Ex11_4 {

	static Queue q = new LinkedList();	//	Queue는 인터페이스 이기 때문에 객체화 하는 대상은 Queue를 구현한 클래스 중에 하나를 선택 하면 된다.

	static final int MAX_SIZE = 5;	// Queue에 최대 5개까지만 저장되도록 한다.

	public static void main(String[] args) {

		System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");

		while(true) {

			System.out.print(">>");

			try {
				// 화면으로부터 라인단위로 입력받는다.
				Scanner s = new Scanner(System.in);  
				String input = s.nextLine().trim();

				if("".equals(input)) continue;

				if(input.equalsIgnoreCase("q")) {	//	q 또는 Q 를 입력 하면 프로그램을 종료 한다.
					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")) {
					int i=0;
					// 입력받은 명령어를 저장하고,
					save(input);    

					// LinkedList의 내용을 보여준다.
					LinkedList tmp = (LinkedList) q;
					ListIterator it = tmp.listIterator();

					while(it.hasNext())
						System.out.println(++i + "." + it.next());
				} else {
					save(input);    
					System.out.println(input);
				} // if(input.equalsIgnoreCase("q")) {
			} catch(Exception e) {
				System.out.println("입력오류입니다.");
			}

		} // while(true)

	} //  main()

	public static void save(String input) {

		// 빈 문자열이 아니면 queue에 저장한다.
		if(!"".equals(input))
			q.offer(input);

		// queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제한다.
		if(q.size() > MAX_SIZE)  // size()는 Collection 인터페이스에 정의
			q.remove();
	}

} // end of class

 

help를 입력하면 도움말을 볼 수 있습니다.

>>

>> help

help - 도움말을 보여줍니다.

q 또는 Q - 프로그램을 종료합니다.

history - 최근에 입력한 명령어를 5개 보여줍니다.

>>테스트

테스트

>>아이오에우

아이오에우

>>큐

큐

>>스택

스택

>>history

1.테스트

2.아이오에우

3.큐

4.스택

5.history

>>

>>큐&스택

큐&스택

>>history

1.큐

2.스택

3.history

4.큐&스택

5.history

>>

 

[ 참고 ]

 

static Queue q = new LinkedList();

 

Queue 인터페이스의 참조변수 q는 LinkedList 객체의 주소값을 가리킨다.

 

이는, 인터페이스 이기 때문에, Queue 자신으로 객체화가 불가능 해서,

Queue 인터페이스를 구현한 클래스 중에 하나를 선택 해서 객체화를 하는 개념 이다.

 

이때, 참조변수 q가 사용 할 수 있는 메서드는 무엇이 있을까 ?

 

 

여기에서, Queue에 마우스를 올리고 ctrl + o 를 누르면 Queue 인터페이스의 메서드를 볼 수 있다.

 

 

위와 같은 메서드가 있는것을 확인 할 수 있는데, 뭔가 사용하기 마땅한 메서드가 없다.

 

LinkedList tmp = (LinkedList) q;

ListIterator it = tmp.listIterator();

 

while(it.hasNext())

System.out.println(++i + "." + it.next());

 

위의 코드를 보면, 그래서 참조변수 q에다가 LinkedList 자료형으로 다운캐스팅 한다.

 

그러면 참조변수 q는 LinkedList 타입이 되고, 그 주소값을 tmp 변수에 저장 한다.

 

이렇게 되면 참조변수 tmp는 LinkedList가 사용 할 수 있는 모든 메서드를 사용 할 수 있게 된다.

 

listIterator() 메서드는 잘 사용 하는 메서드는 아닌듯 하다..