11장 컬렉션프레임워크 20201029

스택과 큐 p.604~

 

스택

 

LIFO구조

마지막에 저장한 데이터를 가장 먼저 꺼냄

 

순차적으로 데이터를 추가하고 삭제하기 때문에

ArrayList와 같은 배열기반의 컬렉션클래스가 구현하기에 적합

 

 

큐

 

FIFO구조

처음에 저장한 데이터를 가장 먼저 꺼냄

 

데이터를 꺼낼 때 항상 첫번째 저장된 데이터를 꺼내므로

LinkedList로 구현하는 것이 적합 (데이터의 추가/삭제가 쉬움)

(ArrayList로 구현하면 데이터를 꺼낼 때마다 빈공간 채우기 위해 데이터 복사 발생, 비효율)

 

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 
public class StackQueueEx {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();    // LinkedList는 Queue인터페이스의 구현클래스
        
        // 스택에 요소 추가
        st.push("0");
        st.push("1");
        st.push("2");
        
        // 큐에 요소 추가
        q.offer("0");
        q.offer("1");
        q.offer("2");
        
        // 스택과 큐의 가장 맨 위에 있는 요소를 반환, 꺼내진 않음
        System.out.println("= Stack Queue Peek");
        System.out.println(st.peek());
        System.out.println(q.peek());
        
        // 스택에 저장되어 있는 요소 삭제
        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 Queue Peek
2
0
= Stack =
2
1
0
= Queue =
0
1
2

 

 

스택은 Stack클래스로 구현해 제공

큐는 Queue인터페이스로 정의, 별도의 클래스로 구현해 제공하진 않음

Queue인터페이스를 구현한 클래스들을 사용 ( ex. 8행 )

 

 

 

 

스택 직접 구현하기

 

스택은 컬렉션 프레임워크 이전부터 존재해서 ArrayList가 아닌 Vector를 상속받아 구현되어 있음

 

import java.util.EmptyStackException;
import java.util.Vector;
 
public class MyStack extends Vector {
    // 요소를 추가하는 메소드
    public Object push(Object item) {
        addElement(item);            // 매개변수로 지정된 요소를 벡터 끝에 추가, 크기 1증가
        return item;
    }
    
    // 요소를 삭제하는 메소드
    public Object pop() {
        Object obj = peek();        // 마지막 요소를 불러옴
        removeElement(size()-1);    // 마지막 요소를 삭제
        return obj;
    }
    
    // 마지막 요소를 반환하는 메소드
    public Object peek() {
        int len = size();
        
        // 스택이 비어있으면 예외발생
        if(len==0) 
            throw new EmptyStackException();
        return elementAt(len-1);    // 마지막 요소를 반환
    }
    
    // 스택이 비었는지 체크하는 메소드
    public boolean empty() {
        return size() == 0;
    }
    
    // 요소를 검색하는 메소드
    public int search(Object o) {
        int i = lastIndexOf(o);        // 끝에서부터 매개변수로 지정된 요소를 찾음
        
        if(i>=0)                    
            return size()-i;
        
        return -1;                    // 찾은 요소의 위치가 정수가 아니면 -1반환
    }
}
 

 

 

 

 

 

 

 

스택과 큐의 활용

 

 

스택 - 수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로 등

큐 - 최근사용문서, 인쇄작업 대기목록, 버퍼 등

 

 

스택(1)

import java.util.Stack;
 
public class StackEx1 {
    // 뒤로, 앞으로의 요소를 담아놓은 스택 구성
    public static Stack back = new Stack();
    public static Stack forward = new Stack();
    
    // 뒤로, 앞으로의 요소와 현재화면이 무엇인지 보여주는 메소드
    public static void printStatus() {
        System.out.println("back: " + back);
        System.out.println("forward: " + forward);
        System.out.println("현재화면은 '" + back.peek() + "' 입니다.");
        System.out.println();
    }
    
    // 매개변수로 지정된 url로 이동하는 메소드
    public static void goURL(String url) {
        back.push(url);
        if(!forward.empty())
            forward.clear();
    }
    
    // 앞의 url으로 이동하는 메소드
    public static void goForward() {
        if(!forward.empty())    // forward가 비어있지 않다면 forward의 마지막값을 back에 넣음
            back.push(forward.pop());
    }
    
    // 뒤의 url으로 이동하는 메소드
    public static void goBack() {
        if(!back.empty())        // back이 비어있지 않다면 back의 마지막값을 forward에 넣음
            forward.push(back.pop());
    }
    
    public static void main(String[] args) {
        goURL("네이버");
        goURL("네이버 웹툰");
        goURL("하이브");
        goURL("1화");
        
        printStatus();
        
        goBack();
        System.out.println("'뒤로가기'버튼 누른 후");
        printStatus();
        
        goBack();
        System.out.println("'뒤로가기'버튼 누른 후");
        printStatus();
        
        goForward();
        System.out.println("'앞으로가기'버튼 누른 후");
        printStatus();
        
        goURL("10화");
        System.out.println("새로운 주소로 이동 후");
        printStatus();
        
    }
 
}
 

출력

back: [네이버, 네이버 웹툰, 하이브, 1화]
forward: []
현재화면은 '1화' 입니다.

'뒤로가기'버튼 누른 후
back: [네이버, 네이버 웹툰, 하이브]
forward: [1화]
현재화면은 '하이브' 입니다.

'뒤로가기'버튼 누른 후
back: [네이버, 네이버 웹툰]
forward: [1화, 하이브]
현재화면은 '네이버 웹툰' 입니다.

'앞으로가기'버튼 누른 후
back: [네이버, 네이버 웹툰, 하이브]
forward: [1화]
현재화면은 '하이브' 입니다.

새로운 주소로 이동 후
back: [네이버, 네이버 웹툰, 하이브, 10화]
forward: []
현재화면은 '10화' 입니다.

 

 

--> 두개의 스택을 사용해 '뒤로', '앞으로'버튼의 기능을 구현

 

 

 

 

 

스택(2)

package stackqueue;
 
import java.util.EmptyStackException;
import java.util.Stack;
 
public class ExpValidCheck {
    public static void main(String[] args) {
        if(args.length!=1) {        
            System.out.println("Usage : java ExpValidCheck \"EXPRESSION\"");
            System.out.println("Example : java ExpValidCheck \"((2+3)*1)+3\"");
            System.exit(0);
        }
        
        Stack st = new Stack();
        String expression = args[0];    // args로 입력받은 값을 String변수에 저장
        
        System.out.println("expression : " + expression);
        
        // 스택이 비어있으면 EmptyStackException이 발생하므로 이에 대한 예외처리
        try {
            // String변수에 저장된 문자열을 char형으로 변환해 검사
            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("괄호가 일치하지 않습니다.");
        }
    }
}
 

 

 

 

 

 

 

 

 

 

큐(1)

package stackqueue;
 
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Scanner;
 
public class QueueEx1 {
    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.print(">>");
            Scanner scanner = new Scanner(System.in);
            String input = scanner.nextLine().trim();
            
            if("".equals(input)) continue;
            
            if(input.equalsIgnoreCase("q")) {
                System.exit(0);
            } else if(input.equalsIgnoreCase("help")) {
                System.out.println(" helf - 도움말을 보여줍니다.");
                System.out.println(" q 또는 Q - 프로그램을 종료합니다.");
                System.out.println(" history - 최근에 입력한 명령어를 " 
                                        + MAX_SIZE + "개 보여줍니다.");
            } else if(input.equalsIgnoreCase("history")) {
                int i=0;
                save(input);
                
                LinkedList tmp = (LinkedList)q;
                ListIterator it = tmp.listIterator();
                
                while(it.hasNext())
                    System.out.println(++i + "." + it.next());
            } else {
                save(input);
                System.out.println(input);
            }    
        }
    }
    
    public static void save(String input) {
        if(!"".equals(input))
            q.offer(input);
        
        if(q.size() > MAX_SIZE)
            q.remove();
    }
 
}
 

출력

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

 

 

--> 큐를 이용해서 구현 ( history는 사용자가 입력한 명령어를 순서대로 보여줌 )

 

 

 

 

 

우선순위 큐 (PriorityQueue)

 

Queue인터페이스의 구현체 중 하나

저장한 순서에 관계없이 우선순위가 높은 것 부터 꺼냄

null저장불가

저장공간으로 배열을 사용

각 요소를 '힙(heap)'이라는 자료구조로 저장

 

package stackqueue;
 
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueEx {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.offer(3);    // pq.offer(new Integer(3)); 오토박싱
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        System.out.println(pq);
        
        Object obj = null;
        
        while((obj = pq.poll())!=null)
            System.out.println(obj);    
    }
}
 

출력

[1, 2, 5, 3, 4]
1
2
3
4
5

 

 

--> 우선순위는 숫자가 작을수록 높은 것이므로 1이 가장 먼저 출력

참조변수 pq를 출력하면, 우선순위 큐가 내부적으로 가지고 있는 배열의 내용이 출력되는데,

저장한 순서와 다르게 출력됨

 

 

 

 

 

 

 

 

데크(Deque) Double-Ended Queue

 

큐의 변형

양쪽 끝에 추가/삭제가 가능

데크의 조상은 큐

구현체로는 ArrayDeque, LinkedList등이 있음

스택과 큐를 하나로 합쳐놓은 것과 같음