백, 큐, 스택 [1/1]

백

백은 항목들을 저장하는 컬렉션 ADT 이다.

백은 말 그대로 주머니이다. 주머니 속에 항목들을 집어 넣고 필요할 때 꺼내쓴다. 백의 특징으로는 항목을 삭제 할 수 없고 순서가 중요하지 않다. 우리가 구슬을 주머니에 저장하는 이미지를 상상하면 된다. 마음에 드는 구슬을 주머니에 넣고, 순서없이 하나씩 꺼내볼 수 있다.

선입선출(FIFO) 큐

큐는 first-in first-out 선입선출을 룰로 가지는 컬렉션이다.

큐는 일상에서 흔히 보는 대기줄을 생각하면 된다. 창구에 먼저 줄을 선 사람이 먼저 업무를 본다. 큐도 마찬가지로 먼저 들어온 아이템이 먼저 나온다. foreach 구문으로 순회할때도 항목들이 추가된 순서대로 순회한다.

큐는 항목들의 순서를 보존하고 싶을때 사용하기 좋다.
EX )

//readAllInts 구현, int값들을 배열로 저장하기
public static int[] readAllInts(String name){
	In in = new In(name);
    // 새로운 큐 q 생성
    Queue<Integer> q = new Queue<Integer>();
    //in에서 q에 int값들 저장
    while(!in.empty())
    	q.enqueue(in.readInt());
	// int 배열 N의 크기를 큐의 크기로 지정
    int N = q.size();
    int[] a = new int[N];
    // q에 들어온 순서를 그대로 보존하며 N에 값들 옮기기
    for(int i=0; i<N; i++) a[i] = q.dequeue();
    return a;
}

후입선출(LIFO) 스택

큐는 last-in first-out 후입선출을 룰로 가지는 컬렉션이다.

스택은 이메일함과 책상에 쌓아둔 서류 뭉치를 생각해보면 된다. 가장 최신에 받은 이메일이 이메일함 가장 위에 쌓이고, 오래된 이메일일수록 밑으로 간다. 서류 뭉치도 새로운 서류는 위에 쌓고, 오래된 서류는 밑에 깔린다. 때문에 가장 먼저 꺼내게 되는 서류는 맨 위에 쌓인 가장 최신에 놓은 서류이다.
웹 서핑도 스택 방식이 사용된다. 홈 -> 내 블로그 -> 내가 작성한 글과 같이 차곡차곡 쌓이고 내가 작성한 글페이지에서 뒤로가기를 누르면 내 블로그, 홈 순으로 돌아간다.

foreach 구문으로 스택을 순회하면 들어온 순서의 역순으로 순회한다. 스택 반복자를 사용하는 목적은 컬렉션에 항목들을 추가한 순서를 보존하되 역순으로 순회하는 것이다.

산술 표현식 계산

 ( 1+ ( (2+3) * (4*5) ) )

위의 계산은 2+3과 4*5를 곱하고 1을 더하면 101이 된다.

자바는 이걸 어떻게 계산할까? 이것을 알아보기 위해 간단한 프로그램을 만들어 알아보자! 이 프로그램은 스택을 사용하며 이해하는데 큰 도움을 준다.

1960년대에 E.W. 데이크스트라가 2중 스택 기반의 대단한 알고리즘을 만들어냈다.
표현식은 괄호, 연산자, 피연산자(숫자)로 구성되며, 왼쪽에서 오른쪽으로 하나씩 처리한다. 스택 조작은 아래 네가지 경우에 맞추어서 한다

• 피연산자(숫자)를 만나면 피연산자 스택에 넣는다
• 연산자를 만나면 연산자 스택에 넣는다
• 열림 괄호 ( 는 무시한다.
• 닫힘 괄호 ) 를 만나면 연산자와 그 연산자에 필요한 피연산자들을 스택에서 꺼내 계산한다. 결과값을 구해 피연산자 스택에 넣는다.

이러한 작업 후 마지막 닫힘 괄호를 만나면 피연산자 스택에 표현식 전체의 결과값이 남게 된다!!

public class Evaluate {
	public static void main(String[] args){
    	Stack<String> 연산자들 = new Stack<String>();
        Stack<Double> 피연산자들 = new Stack<Double>();
        while (!Stdln.isEmpty()){
        	String s = Stdln.readString();
            // case1: 열림괄호 '(' 무시
            if(s.equals("("))
            // case2: 연산자는 연산자들 스택에 추가
            else if (s.equals("+")) 연산자들.push(s);
            else if (s.equals("-")) 연산자들.push(s);
            else if (s.equals("*")) 연산자들.push(s);
            else if (s.equals("/")) 연산자들.push(s);
            else if (s.equals("sqrt")) 연산자들.push(s);
            // case3: 닫힘괄호 ')' 피연산자들에서 피연산자,
            //        연산자들에서 숫자 꺼내서 계산 후 
            //        피연산자들 스택에 추가
            else if (s.equals(")")){
            	String 연산자 = 연산자들.pop();
                Double 피연산자 = 피연산자들.pop();
                if (연산자.equals("+")) 피연산자 = 피연산자들.pop() + 피연산자;
                if (연산자.equals("-")) 피연산자 = 피연산자들.pop() - 피연산자;
                if (연산자.equals("*")) 피연산자 = 피연산자들.pop() * 피연산자;
                if (연산자.equals("/")) 피연산자 = 피연산자들.pop() / 피연산자;
                if (연산자.equals("sqrt")) 피연산자 = Math.sqrt(피연산자);
                피연산자들.push(피연산자);
            }
            // case4: 피연산자(숫자)는 피연산자들 스택에 추가
         	else 피연산자들.push(Double.parseDouble(s));
        }
        // while문이 다 돌아가고 마지막 피연산자들 스택에 있는 값 출력
    	StdOut.println(피연산자들.pop());
    }	
}