21-11-21 Stack & Queue

Stack

Last In First Out(LIFO) - 저장할 때 순서와 호출할 때 순서가 반대 

-> 나오는 구멍이 한 개인 상자를 생각하면 된다. 가장 먼저 넣는(Push) 자료는 상자의 가장 바닥으로 들어가게 되므로 이 자료를 꺼내려면(Pop) 위에 있는 모든 자료를 꺼내야만 꺼낼 수 있다. 

 

순차적으로 자료가 저장, 역방향으로 삭제되므로 stack을 구현하는데 적합한 자료구조는 배열이다.

 

Stack st = new Stack();

 

위와 같이 작성하여 stack을 구현할 수 있다. 

 

Stack 클래스의 메서드 

 

메서드	설명
boolean isEmpty()	Stack이 비어있는지 확인한다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환. pop()와는 달리 Stack에서 객체를 꺼내지 않음.(Stack이 비었을 경우 EmptyStackException 발생)
Object pop()	Stack의 맨위에 저장된 객체를 꺼낸다. (Stack이 비었을 경우 EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다. 못찾으면 -1을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작)

 

stack의 생성과 push, pull

 

Stack st = new Stack();

st.push("0");
st.push("1");
st.push("2");

System.out.println("== Stack ==");
while(!st.empty()) System.out.println(st.pop());

 

 

 

Stack의 활용 

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

 

*수식 괄호 검사 

 

import java.util.*;

public class CollectionFramework03 {

	public static void main(String[] args) {

		Stack st = new Stack();
		String expression = "((3+5)*8-2)";

		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("괄호가 일치하지 않습니다.");
		}

	}

}

 

수식을 String 변수로 선언하고 반복문을 통해 String의 문자 하나하나를 검사하여 ' ( '와 ' ) '를 찾는다. ' ( '를 발견하면 stack에 push하고 ' ) '를 찾는다면 반대로 pop한다. ' ( '와 ' ) '의 갯수가 딱 맞는다면 push된 만큼 pop되기 때문에 stack이 비게된다. 이 경우 괄호가 일치한다는 결과를 출력한다.

' ) '가 모자라게 되면 ' ( '에 의해 push 된 데이터가 stack 에 남아있기 때문에 isEmpty 메소드에서 falus를 반환받게 되고else문의 문장이 출력된다. 

' ) '가 더 많은 경우에는 push된 데이터가 모두 pop되어 stack이 비어 있는데도 불구하고 남아있는 ' ) '에 의해 빈 stack에 pop메소드를 시행하게 되므로 EmptyStatckException이 발생하고 catch 구문의 출력문이 출력된다.

 

 

 

 

Queue

First In First Out(FIFO) - 저장할 때 순서와 호출할 때 순서가 같다.

-> 양끝이 뚫려있는 터널 같은 구조로 들어가는 곳과 나오는 곳이 따로 있다. 터널에 먼저 들어가는 차가 먼저 터널을 나오게  되는 것과 같이 가장 처음 저장(Offer)된 데이터가 가장 먼저 추출(Poll)된다. 

 

자료가 순방향으로 추출되므로 Linked List를 사용하여 구현하는 것이 바람직하다. 

 

Queue는 인터페이스로 Stack처럼 Queue q = new Queue(); 형식으로 선언할 수는 없고 Queue를 직접 구현하거나 Queue인터페이스를 구현한 클래스를 통해 Queue를 사용할 수 있다.

 

Queue인터페이스를 구현한 클래스

 

Queue q = new LinkedList();

 

와 같이 선언한다. 

 

Queue 조작 메서드 

 

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true반환. (저장공간이 부족하면 IllegalStateException 발생)
Object remove()	Queue에서 객체를 꺼내 반환. Queue가 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어온다. peek와 달리 Queue가 비어있으면 NoSuchElementException 발생
boolean offer(Object o)	Queue에 객체를 저장. 성공하면 true 반환
Object poll()	Queue에서 객체를 꺼내서 반환. Queue가 비어있으면 null 반환 (예외 발생 x)
Object peek()	삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환

 

 

Queue의 생성과 push, pull

 

Queue q = new LinkedList();

q.offer("0");
q.offer("1");
q.offer("2");

System.out.println("== Queue ==");
while(!q.isEmpty()) System.out.println(q.poll());

 

 

Queue의 활용

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

 

*최근 사용 명령어 

 

import java.util.*;

public class CollectionFramework04 {

	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.print(">>");
			try {
				// 화면으로 부터 라인단위로 입력받기
				Scanner sc = new Scanner(System.in);
				String input = sc.nextLine().trim();

				if ("".equals(input))
					continue;
				// 공백을 입력하면 While문 조건절로 돌아감

				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;
					//Queue 클래스에 사용할 수 있는 메서드가 별로 없기 때문에 LinkedList로 형변환 해줌

					for (int i = 0; i < list.size(); i++)
						System.out.println((i + 1) + ". " + list.get(i));
				} else {
					save(input);
					System.out.println(input);
				}
			} catch (Exception e) {
				System.out.println("입력오류입니다.");
			}
		}

	}
	
	public static void save(String input) {
		//queue에 저장한다. 
		if(!"".equals(input)) // == if(input!=null && !input.equals("")) 
			q.offer(input);
		
		//queue의 최대 크기를 넘으면 제일 처음 입력된 것을 삭제한다.
		if(q.size() > Max_size) q.remove(); // == q.poll();
		
	}

}

 

queue를 전역변수로 선언(메인과 메소드에서 사용해야 하므로)하고 보여주고 싶은 내역의 최대 갯수를 final변수로 지정한다. 사용자의 입력에 따라 결과를 출력하는데

1. help를 입력하면 명령어 안내

2. q는 프로그램 종료

3. history를 입력하면 최근 입력한 명령어를 5개까지(final Max_size로 지정한 변수에 따라 다름) 출력

4. 다른 문자열을 입력했을 경우 입력한대로 출력

5. 공백을 입력한 경우 다시 입력받는다.

 

3,4 번의 경우 입력받은 문자열을 저장하는데 이때 사용한 메소드 save는 입력받은 문자열 input이 공백이 아니라면 input을 queue에 저장하고 queue의 최대갯수(Max_size)를 초과한 경우 가장 처음에 입력된 데이터를 삭제한다. (Queue는 FIFO방식이므로 그냥 poll 혹은 remove하면 가장 오래된 자료부터 삭제된다.) 

 

Queue 클래스의 객체가 사용할 수 있는 메소드는 아래 6개 뿐이므로 q를 LinkedList로 형변환 해준다.

 

LinkedList의 데이터를 반복문을 돌며 get(i)를 통해 출력해주면 끝! 

 

save메소드를 통해 queue에 offer된 문자열들을 내역을 확인 할 수 있다.