스택 클래스와 큐 인터페이스

[스택과 큐 비교]

1. 스택

- LIFO(Last In First Out)

- 밑이 막힌 상자

- 마지막에 저장(push)된 것을 제일 먼저 꺼내게(pop) 되는 구조

- 배열로 구현하는 것이 효율적이다. 순방향/역방향 접근이 빠르기 때문이다.

2. 큐

- FIFO(First In First Out)

- 밑이 뚫린 상자

- 제일 먼저 저장(offer)된 것을 먼저 꺼내게(poll) 되는 구조

- 링크드 리스트로 구현하는 것이 효율적이다. 맨 앞 삭제시 자리 이동이 필요 없기 때문이다.

 

[스택과 큐의 메서드]

1. 스택

boolean empty()
// 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을 반환한다.
// 배열과 달리 인덱스는 1부터 시작한다.
// Stack의 맨 위에 있는 객체의 인덱스가 1이다.

2. 큐

boolean add(Object o)
// 지정된 객체를 Queue에 추가한다.
// 성공하면 true를 반환한다.
// 저장공간이 부족하면 IllegalStateException 발생

Object remove()
// Queue에서 객체를 꺼내서 반환한다.
// 빈 Queue면 NoSuchElementException 발생

Object element()
// 삭제 없이 요소를 읽어온다.
// peek()와 달리 빈 Queue면 NoSuchElementException 발생

boolean offer(Object o)
// Queue에 객체를 저장한다.
// 성공하면 true, 실패하면 false를 반환한다.

Object poll()
// Queue에서 객체를 꺼내 반환한다.
// 빈 Queue면 null을 반환한다.

Object peek()
// 삭제 없이 요소를 읽어온다.
// 빈 Queue면 null을 반환한다.

 

[스택, 큐 선언]

// 스택 클래스
Stack s = new Stack();

// 큐 인터페이스
// 1) Queue를 직접 구현한 클래스를 작성해서 쓴다.
// 2) Queue를 구현해놓은 클래스를 쓴다. - LinkedList 클래스 등
Queue q1 = new LinkedList(); // Queue에 있는 메서드만 사용했기 때문에
                             // LinkedList 말고 다른 클래스를 써도 상관 없다.
LinkedList q2 = new LinkedList(); // Queue를 구현한 다른 클래스로 코드를 바꿀 경우 검토가 필요하다.

 

[스택, 큐 사용예시]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
// main()
Stack s = new Stack();
Queue q = new LinkedList();

// 스택과 큐에 0,1,2 추가
s.push("0"); s.push("1"); s.push("2");
q.offer("0"); q.offer("1"); q.offer("2");

// 하나씩 꺼내서 출력
System.out.print("Stack -> ");
while(!s.empty()) // 스택이 비어있지 않은지 확인
    System.out.print(s.pop() + " "); // 스택에서 요소 하나를 꺼내서 출력
System.out.print("\nQueue -> ");
while(!q.isEmpty()) // 큐가 비어있지 않은지 확인
    System.out.print(q.poll() + " "); // 큐에서 요소 하나를 꺼내서 출력

// 결과
// Stack -> 2 1 0
// Queue -> 0 1 2

 

[스택과 큐의 활용]

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

// 수식 괄호 검사 – 마지막에 스택이 비어있으면 괄호가 맞게 작성된 식
Stack s = new Stack();
String expression = "여기에 검사하고자 하는 수식 입력";
try {
    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        if (c == '(') s.push(c + "");
        else if (c == ')') s.pop();
    }
    if (s.isEmpty()) System.out.println("괄호가 일치합니다.");
    else System.out.println("여는 괄호 '('가 더 많습니다.");
} catch (EmptyStackException e) {
    System.out.println("닫는 괄호 ')'가 더 많습니다.");
}

// expression = "(1+2)*3*(5+6)" 일 경우 결과
// "괄호가 일치합니다."
// expression = "(1+2)*3*5+6)" 일 경우 결과
// "닫는 괄호 ')'가 더 많습니다."

2. 큐: 최근 사용 문서, 인쇄 작업 대기 목록, 버퍼(buffer)