Stack & Queue

Stack

LIFO(Last in Frist out)구조

마지막에 저장된 것을 제일 먼저 꺼내게 된다

배열로 구현하는 것이 좋다

Stack st = new Stack();

 

Stack 메서드

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

 

---

Queue

FIFO(First in First out)구조

제일 먼저 저장한 것을 제일 먼저 꺼내게 된다

LinkedList로 구현하는 것이 좋다

Queue는 인터페이스이기 때문에 Queue q = new Queue();는 안된다(인터페이스이기 때문에 객체 생성이 안되기 때문)

 

Queue 메서드

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

 

 

인터페이스를 구현한 클래스 찾기

오라클 공식 문서 링크

Queue q = new LinkedList();

 

코드

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

public class StackLinkedListTest {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();	// Queue인터페이스의 구현체인 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()); // Stack에서 요소 하나를 꺼내서 출력
        }
        System.out.println();

        System.out.println("Queue");
        while(!q.isEmpty()) {
            System.out.println(q.poll()); // Queue에서 요소 하나를 꺼내서 출력
        }
    }
}

Stack
2
1
0

Queue
0
1
2

---

Stack의 활용 예

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

 

Queue의 활용 예

최근 사용문서, 인쇄작업 대기목록, buffer