자바의 정석 기초편 ch11 - 13 ~ 21 [Stack과 Queue, Stack과 Queue의 활용]

1) 스택(stack)

• LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼냄 (Last In First Out)
• 저장(push) 순서와 추출(pop) 순서가 반대
• 저장 0 -> 1 -> 2 / 추출 2 -> 1 -> 0
• 배열 -> Stack구조가 적합

2) 큐 (Queue)

• FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼냄(First In FIrst Out)
• 저장(offer) 순서와 추출(poll) 순서가 동일
• LinkedList -> 큐(Queue)구조가 적합

 

3) Stack클래스의 메서드

(1) Stack클래스의 사용

• Stack 객체를 직접 생성하여 사용

구분	메서드	설 명
확인	boolean empty()	Stack이 비어있는지 확인
	Object peek()	Stack의 맨 위에 저장된 객체를 조회 / 맨 위에의 데이터를 peek이라 함. pop()과 달리 Stack에서 객체를 꺼내지는 않음. (비었을 때는 EmptyStackException 발생)
삭제	Object pop()	Stack의 맨 위에 저장된 객체를 꺼냄 / (비었을 때는 EmptyStackException 발생)
추가	Object push(Object item)	Stack에 객체(item)를 저장
검색	int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환 / 못찾으면 -1을 반환 (indexOf와 달리 0이 아닌 1에서부터 시작)

4) Queue 인터페이스의 메서드

(1) Queue인터페이스 사용

• Queue를 직접 구현하거나 Queue를 구현한 클래스를 사용
• 대표적으로 LinkedList가 있음 

구분	메서드	설 명
추가(예외발생)	boolean add(Object o)	지정된 객체를 Queue에 추가 / 성공하면 true반환 저장공간이 부족하면 IllegalStateException발생
삭제(예외발생)	Object remove()	Queue에서 객체를 꺼내서 반환 / 비어있으면 NoSuchElementException발생
확인(예외발생)	Object element()	삭제없이 요소를 읽어옴 비어있으면 NoSuchElementException발생
추가	boolean offer(Object o)	Queue에 객체를 저장 / 성공하면 true, 실패하면 false
삭제	Object poll()	Queue에 객체를 꺼내서 반환 / 비어있으면 null 반환
확인	Object peek()	삭제없이 요소를 읽어 옴 / 비어있으면 null 반환

 

(2) Stack, Queue 구현 예제

import java.util.*;

class Ex11_2 {
	public static void main(String[] args) {
		Stack st = new Stack();
        
        // Queue인터페이스의 구현체인 LinkedList객체를 생성 후 Queue타입 참조변수에 저장
		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()); // 큐에서 요소 하나를 꺼내서 출력
		}
	}
}

---

5) Stack과 Queue의 활용

(1) Stack의 활용 예

• 수식계산, 수식괄호검사, undo/redo, 브라우저의 뒤로/앞으로 등

(2) 큐의 활용 예

• 최근사용문서, 인쇄작업대기목록, 버퍼(buffer) 등

(3) 수식괄호검사 예제 (괄호가 모두 잘 사용 되었는지) - Stack

• arguments에 입력하거나 코드에 수식을 직접 입력

// 수식 괄호 검사 예제 -> 여는 괄호(push) 닫는 괄호(pop)
// 수식이 끝나면 스택이 전부 비워짐 -> true,

import java.util.*;

public class Ex11_3 {
	public static void main(String[] args) {
		if (args.length != 1) {
			System.out.println("Usage:java Ex11_3 \"EXPRESSION\"");
			System.out.println("Example:java Ex11_3 \"((2+3)*1)+3\"");
			System.exit(0);
		}

		Stack st = new Stack();
		String expression = args[0];

		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()) {
				System.out.println("괄호가 일치합니다.");
			} else {
				System.out.println("괄호가 일치하지 않습니다.");
			}
		} catch (EmptyStackException e) {
			System.out.println("예외 발생");
		} // try
	}
}

 

(4) 최근입력 목록 출력 예제 - Queue

import java.util.*;

class Ex11_4 {
	static Queue q = new LinkedList(); // Queue인터페이스를 구현한 linkedList 클래스 생성
	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")) {
					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")) {
					// 입력받은 명령어를 저장하고,
					save(input);    

					// LinkedList타입으로 참조변수를 형변환
					LinkedList list = (LinkedList)q;
					
					// listIterator를 활용하여 값을 출력
//					int i=0;
//					ListIterator it = list.listIterator();					
//					while(it.hasNext())
//						System.out.println(++i+"."+it.next());
					
					// ListIterator를 잘 사용하지 않아서 for문으로 값을 출력
					// 성능 향상을 위해 반복횟수가 변하지 않을 때에는 반복횟수를 상수로 지정
					final int SIZE = list.size();
					for(int i=0; i<SIZE; i++)
						System.out.println((i+1)+"."+list.get(i));
					
				} else {
					save(input);    
					System.out.println(input);
				} // if(input.equalsIgnoreCase("q")) {
			} catch(Exception e) {
				System.out.println("입력오류입니다.");
			}
		}
	} //  main()
    
    // 값을 저장하는 save() 메서드
	public static void save(String input) {
		// queue에 저장한다.
		if(!"".equals(input))	//input!=null && !input.equals("")
			q.offer(input);

		// queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제
		if(q.size() > MAX_SIZE) // size()는 Collection인터페이스에 정의
			q.remove();  //q.poll(); 써도 동일한 기능을 하지만 값이 비어있으면 null을 반환
	}
} // end of class

  

 

** 출처 : 남궁성의 정석코딩_자바의정석_기초편 유튜브 강의