Stack, Queue 개념

Stack과 Queue의 개념을 잡기 전 아래의 그림을 먼저 살펴보자.

Stack과 Queue

눈으로 보기에도 확연히 다른 구조를 이루고있다.

 

Stack이란?

LIFO : Last in Fast Out
마지막에 저장된 것을 가장 먼저 꺼낸다. 저장(push), 추출(pop)
한쪽이 막힌상자 : 위쪽으로만 추출이 가능
배열이 적합

 

Queue란?

FIFO : First In First Out
제일 먼저 저장된 것을 제일 먼저 꺼낸다. 저장(offer), 추출(poll)
양쪽이 뚫려있는 상자
링크드 리스트가 적합

 

Stack의 메서드

메서드	설명
boolean empty()	비어있는지 확인
Object peek()	맨 위의 객체를 반환, pop과는 달리 Stack에서 객체를 꺼내지는 않는다.
Object pop()	삭제
Object push(Object item)	추가
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 찾지못하면 -1을 반환 배열과는 달리 위치의 시작은 0이아닌 1부터 시작

 

Queue의 메서드

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

 

 

메서드를 살펴보았으니 코드를 보며 한번 확인해보자

import java.util.*;

class Ex11_2 {
    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()); // 스택에서 요소 하나를 꺼내서 출력
        }

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

=============실행결과============

= Stack =
2
1
0
= Queue =
0
1
2

---

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

위와같이 순서대로 Stack에 요소를 집어넣는다. 

 

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

Queue에도 순서대로 요소를 집어넣는다. 

 

while(!st.empty()) {
    System.out.println(st.pop()); 
}

Stack이 비어있지 않다면 요소를 하나씩 추출한다. 

추출순서는 LIFO구조 이기 때문에 2,1,0 마지막에 추가한 요소부터 차례대로 추출이 되어진다.

 

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

Queue의 경우에도 비어있지 않다면 하나씩 삭제를 하는데

추출순서는 FIFO구조이기 때문에 0,1,2 와같이 가장 먼저 들어온 요소가 가장 먼저 추출이 되어진다.