[ch11 컬렉션 프레임웍] Stack과 Queue의 메서드 (add vs offer)

 

Stack과 Queue

 

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

즉) 스택은 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이고, 큐는 양 옆만 막혀 있고 위 아래는 뚫려 있어 한 방향으로 빼는 파이프와 같은 구조로 되어있다. 

 

예를 들어 스택에 0, 1, 2의 순서로 데이터를 넣었다면 꺼낼 때는 2, 1, 0 순서로 꺼내게 된다. 즉) 넣은 순서와 꺼낸 순서가 뒤집어지게 되는 것이다. 이와 반대로 큐에 0, 1, 2 순서대로 데이터를 넣었다면 꺼낼 때 역시 0, 1, 2의 순서로 꺼내게 된다. 순서의 변경 없이 먼저 넣은 것을 먼저 꺼내게 되는 것이다.

 

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

 

 

Stack의 메서드

 

메서드	설 명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지 않는다.  (비었을 때는 EmptyStackException발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다.  (비었을 때는 EmptyStackException발생)
Object push(Object item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환 (배열과 달리 위치는 0이 아닌 1부터 시작. 맨 위의 요소가 1)

 

 

Queue의 메서드

 

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

 

 

 

📌 add()와 offer()의 차이는 반환형에 따라 구분되는데, add는 값을 추가했을 때 큐가 꽉찼다면 llegalStateException 예외를 발생시키고 offer는 값 추가를 실패하면 false를 반환한다. 

 

📌remove()와 poll()의 차이는, 둘다 객체를 꺼내서 반환하는 것은 같으나 만약 remove했을 때 큐가 비어있다면 NoSuchElementException 예외를 발생시키고 poll은 null을 반환한다. 

 

📌 element()와 peek()은 모두 삭제 없이 요소를 읽어오나, element()는 큐가 비어 있는 경우 NoSuchElementException 예외를 발생시키고 peek은 null을 반환한다. 

 

 

 

---

 

 

<예제 1번>

package ch11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Ex11_2 {

	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList(); //큐 인터페이스의 구현체인 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()); //스택에서 요소 하나를 꺼내서 출력
			//peek를 하면 맨 위에 요소 "2" 계속 출력
		}
		
		System.out.println("=Queue=");
		while(!q.isEmpty()) {
			System.out.println(q.poll()); //큐에서 요소 하나를 꺼내서 출력
		}

	}

}

예제 1번 출력 값

 

스택과 큐에 각각 요소들을 "0", "1", "2"를 같은 순서로 넣고 꺼냈을 때 다른 값이 나온 걸 알 수 있다. 스택은 Stack 클래스로 구현해서 제공하고 있지만 큐는 Queue 인터페이스로만 정의해 놓아서 별도의 클래스는 제공하지 않는다. 대신! 구현할 클래스들이 있어 이 들 중 선택하면 된다.

 

 

 

Stack과 Queue의 활용

 

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

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

 

 

---

 

< 예제 2번 >

package ch11;

import java.util.EmptyStackException;
import java.util.Stack;

public class Ex11_3 {

	public static void main(String[] args) {
	
		Stack st = new Stack();
		String expression = "((8+3)*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("괄호가 일치하지 않습니다.222");
		}
		
	}

}

예제 2번 출력 값

 

expression에서 글자 하나씩 출력하는 charAt() 메서드로인해  '(' 여는 괄호를 만나면 스택에 넣고(push) ')' 닫는 괄호를 만나면 스택에서 꺼낸다.(pop) 만약! 스택이 비어있는 상태에서 pop()을 실행할 경우 EmptyStackException이 발생하므로 try-catch문을 이용해서 에러 메시지를 출력하도록 하였다.

 

try-catch 문 사용 안 했을 때 나오는 에러 메시지

 

 

---

 

 

<예제 3번 >

package ch11;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Ex11_4 {
	
	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(">>");
		
		try {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine().trim();
		
		if("".equals(input)) continue; //입력값이 공백이면 아래 문장 건너뛰고 while 처음으로 돌아간다.
		
		if(input.equalsIgnoreCase("q")) {
			System.out.println("프로그램 종료합니다.");
			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로 형변환 후 list 메서드 사용
			LinkedList list = (LinkedList)q;
			
			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); //저장된 값
		}
		}catch(Exception e) {
			System.out.println("입력 오류입니다.");
		}
		}
	}
	
	public static void save(String input) {
		//queue에 저장한다.
		if(!"".equals(input))
			q.offer(input);

		//queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제한다.
		if(q.size()>MAX_SIZE)
			q.remove();
	}

}

예제 3번 출력 값

 

history를 입력하면 최근 명령어 MAX_SIZE 만큼 보여 준다. 여기서는 5로 설정해놔서 5개까지 보여주는데 크게 설정하면 더 많이 보여줄 수 있다. offer()메서드로 값을 저장하고 remove()로 맨처음 저장한 값을 꺼내온다. 

 

 

 

인터페이스에 있는 메서드가 궁금할 때

 

 

만약 Queue에 있는 메서드가 궁금하다면 Queue 위에서 오른쪽 버튼 클릭 후 Open Declaration 선택

 

 

Queue 선택 후 Ctrl + o를 누르면 메서드 목록이 나온다!