컬렉션 프레임웍 Collection Framework : Stack, Queue

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out) 구조이고,큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어있다.

예를 들자면 스택은 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이고, 큐는 양 옆만 막혀있고 위아래로 뚫려 있어서 한 방향으로 넣고 한 방향으로 빼는 구조로 되어 있다.

 

그렇다면 스택과 큐를 구현하기 위해서 어떤 컬랙션 클래스를 사용하는 것이 좋을까?

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList를 사용하면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 삭제/추가가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

 

import java.util.*;

class StackQueueEx{
	public static void main(String[] args){
    	Stack st = new Stack();
        Queue q = new 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

 

스택과 큐의 활용

스택의 활용 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

import java.util.*;

public class StackEx1{
	public static Stack back = new Stack();
    public static Stack forward = new Stack();
    
    public static void main(String[] args){
    	goURL("1.네이트");
        goURL("2.야후");
        goURL("3.네이버");
        goURL("4.다음");
        
        printStatus(); // 1
        
        goBack();
        System.out.println("=뒤로가기 버튼을 누른 후=");
        printStatus();
        
        goBack();
        System.out.println("=뒤로가기 버튼을 누른 후=");
        printStatus();
        
        goForward();
        System.out.println("앞으로 버튼을 누른 후");
        printStatus();
        
    }
    public static void printStatus(){
    	System.out.println("back:"+back);
        System.out.println("forward:"+forward);
        System.out.println("현재화면은"+back.peek()+"입니다");
        System.out.println();
    }
    public static void goURL(String url){
    	back.push(url);
        if(!forward.empty)
        	forward.clear();
    }
    public static void goForward(){
    	if(!forward.empty())
        	back.push(forward.pop());
    }
    public static void goBack(){
    	if(!back.empty())
        	forward.push(back.pop());
    }
}

 

큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼

import java.util.*;

class QueueEx1{
	static Queue q = new LinkedList();
    static final int MAX_SIZE = 5; // Queue에 최대 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();
                
                if("".equals(input))
                	continue;
                if(input.equlsIgnoreCase("q"))
                	System.exit(0);
                else if(input.equalsIgnoreCase("help")){
                	System.out.println("help - 도움말을 보여줍니다");
                    System.out.println("q 또는 Q - 프로그램을 종료합니다");
                    System.out.println("history - 최근 입력한 명령어를 보여줍니다");
                }
                else if(input.equalsIgnoreCase("history")){
                	int i = 0;
                    save(input); // 저장받은 명령어를 저장한다
                    //Queue 내용을 보여준다.
                    LinkedList tmp = (LinkedList)q;
                    ListIterator it = tmp.listIterator();
                    while(it.hasNext())
                    	System.out.println(++i+"."+it.next());
                } else{
                	save(input);
                    System.out.println(input);
                }
            }
        } // 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