본문
Stack과 Queue(JAVA)
프로그래밍/Java 2016. 1. 5. 15:26
반응형
# Stack과 Queue(List 기반)
Stack - LIFO(Last In First Out) : ArrayList 적합
Queue - FIFO(First In First Out) : LinkedList 적합
순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedLIst로 구현하는 것이 더 적합하다.
Stack은 컬렉션 프레임웍 이전부터 존재하던 것이기 때문에 ArrayList가 아닌 Vector로부터 상속받아 구현하였다.
Source 01) StackEx01.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | package stackEx; import java.util.EmptyStackException; import java.util.Vector; public class StackEx01 extends Vector { public Object push(Object item) { addElement(item); return item; } public Object pop() { Object obj = peek(); // Stack에 저장된 마지막 요소를 읽어온다. // 만일 Stack이 비어있으면 peek() 메서드가 EmptyStackException을 발생시킨다. // 마지막 요소를 삭제한다. 배열의 index가 0부터 시작하므로 1을 빼준다. removeElement(size() - 1); return obj; } public Object peek() { int len = size(); if (len == 0) throw new EmptyStackException(); // 마지막 요소를 반환한다. 배열의 index가 0부터 시작하므로 1을 빼준다. return elementAt(len - 1); } public boolean empty() { return size() == 0; } public int search(Object o) { int i = (lastIndexOf(o)); // 끝에서부터 객체를 찾는다. // 반환값은 저장된 위치 (배열의 index)이다. if (i >= 0) { // 객체를 찾은 경우 return size() - i; // Stack은 맨 위에 저장된 객체의index를 1로 정의하기 때문에 // 계산을 통해서 구한다 } return -1; // 해당 객체를 찾지 못하면 -1을 반환한다. } } | cs |
※ 참고 : Stack이 가득 차있을 때 데이터를 넣기 위해push()를 호출하면 스택 오버플로우(Stack Overflow)가 되고,
Stack이 비어있을 때데이터를 꺼내기 위해 pop()을 호출하려면 스택 언더플로우(Stack underflow)가 된다.
- 스택의 활용 예
수식계산, 수식괄호검사, 워드프로세서의 undo redo, 웹브라우저의 뒤로 앞으로
Source 02) StackEx02.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | package stackEx; import java.util.Stack; public class StackEx02 { 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(); goBack(); System.out.println("= '뒤로' 버튼을 누른 후 ="); printStatus(); goForward(); System.out.println("= '앞으로' 버튼을 누른 후 ="); printStatus(); goURL("java_home.com"); 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()); } } | cs |
Result)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | back : [1. 네이트, 2. 야후, 3. 네이버, 4. 다음] forward : [] 현재화면은 : '4. 다음' 입니다. = '뒤로' 버튼을 누른 후 = back : [1. 네이트, 2. 야후, 3. 네이버] forward : [4. 다음] 현재화면은 : '3. 네이버' 입니다. = '앞으로' 버튼을 누른 후 = back : [1. 네이트, 2. 야후, 3. 네이버, 4. 다음] forward : [] 현재화면은 : '4. 다음' 입니다. = 새로운 주소로 이동 후 = back : [1. 네이트, 2. 야후, 3. 네이버, 4. 다음, java_home.com] forward : [] 현재화면은 : 'java_home.com' 입니다. | cs |
※ Object peek()
Stack의 맨 위에 저장된 객체를 반환한다. Stack에서 꺼내지는 않는다. 비었을 때null을 반환한다.
- 큐의 활용 예
최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)
Source 03) QueueEx01.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | package QueueEx; import java.util.LinkedList; import java.util.ListIterator; import java.util.Queue; import java.util.Scanner; public class QueueEx01 { 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(); /* ※ equals과 equalsIgnoreCase의 차이점 equals : 대소문자를 구별, equalsIgnoreCase : 대소문자를 구별하지 않음 */ if ("".equals(input)) continue; if (input.equalsIgnoreCase("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; // 입력받은 명령어 "history"를 저장하고, 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); } } catch (Exception e) { System.out.println("입력오류입니다."); } } } public static void save(String input) { // queue에 저장한다. // boolean offer(Object o) : Queue에 객체를 저장한다 // 성공하면 true, 실패하면 false를 반환한다. if (!"".equals(input)) q.offer(input); // queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제한다. if (((LinkedList) q).size() > MAX_SIZE) q.remove(); } } | cs |
Result)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | help를 입력하면 도움말을 볼 수 있습니다. >> help help - 도움말을 보여줍니다. q 또는 Q - 프로그램을 종료합니다. history - 최근에 입력한 명령어를5개 보여줍니다. >> history 1.history >> cd cd >> cd.. cd.. >> history 1.history 2.cd 3.cd.. 4.history >> q | cs |
이 예제는 리눅스의 history명령어를 Queue를 이용해서 구현한 것이다.
history 명렁어는 사용자가 입력한 명령어의 이력을 순서대로 보여준다.
여기서는 최근 5개의 명령어만을 보여주는데 MAX_SIZE의 값을 변경함으로써 더 많은 명령어 입력기록을 남길 수 있다.
- 출처 및 참고자료 : JAVA의정석(남궁성 저)
반응형
댓글