03. stack, queue

스택은 LIFO, 큐는 FIFO 라는 것만 알아도 다 이해했다해도 무관할 정도로 스택과 큐는 구현도, 사용도 너무나 쉬운 자료구조이다. 그만큼 자주 쓰이기도 하니 꼭 알아두자.

 

스택은 Last in First out 으로, 후입선출의 구조이다. 아래 그림처럼 먼저 들어간 값이 가장 아래에 쌓이기 때문이다.

이러한 구조는 웹 브라우저의 뒤로가기, 텍스트 에디터의 ctrl+z, JVM의 chain of method call(ex. recursion call) 등에 사용이 된다. 스택을 사용하기 위해서 자바에서 제공해주는 클래스 java.util.stack을 사용하여도 좋다. 스택 클래스에서 제공하는 메소드는 아래와 같다.

method	description
boolean isEmpty()	스택이 비었는지를 확인하고 참이면 True, 아니면 False 리턴
void push(Object e)	스택의 top 다음에 element e 삽입
Object pop()	스택의 top에 있는 값 삭제 후 리턴
Object peek()	스택의 top에 있는 값 리턴
Object search(Object e)	스택에서 e가 저장된 index 리턴

위 메소드 사용예시는 아래와 같다.

public class Stack1 {
    public static void main(String[] args){
        Stack st = new Stack();
        Object test = 'b';

        if(st.isEmpty()){
            st.push('a');
            st.push('b');
            st.push('c');
        }

        System.out.println(st.peek());
        System.out.println(st.search(test));
        st.pop();
        System.out.println(st);
    }
}

참고로 스택 클래스를 사용하면 스택 객체의 이름만 가지고도 스택의 element들을 출력할 수 있다. 하지만 사용자가 배열을 이용해서 직접 구현한 스택에서는 동일하게 적용할 수 없다.

---

큐는 First in First out으로 선입선출의 구조를 갖는다. 아래 그림을 보면 스택에는 top과는 달리 front와 rear가 존재한다. 각각 가장 앞의 값과 마지막 값을 가리킨다.

가장 대표적으로 RoundRobin 스케줄링에 사용이 되며 CPU time sharing, packet switcing network 등의 작업을 한다. 큐는 자바에서 제공하는 클래스를 사용하려면 2개의 클래스를 알아야한다. java.util.Queue, java.util.LinkedList 이 두 가지로 큐 객체를 생성해야 한다. 큐 클래스에서 제공하는 메소드는 다음과 같다.

method	description
Boolean isEmpty()	큐가 비었는지를 확인하고 참이면 True, 아니면 False 리턴
void offer(Object e)	큐의 rear 다음에 element e 삽입
Object poll()	큐의 front에 있는 값 삭제 후 리턴
Object peekFirst()	큐의 front에 있는 값 리턴
Object peekLast()	큐의 rear에 있는 값 리턴

아래 사용 예시를 보자.

public class Queue1{
    public static void main(String[] args){
        Queue que = new LinkedList();

        if(que.isEmpty()){
            que.offer('a');
            que.offer('b');
            que.offer('c');
        }
        System.out.println(((LinkedList) que).peekFirst());
        System.out.println(((LinkedList) que).peekLast());
        que.poll();
        System.out.println(que);
    }

사실 큐는 priority queue, wrapped around queue 처럼 용도가 다양한 종류가 있기 때문에 사용자가 직접 구현해서 사용하는 경우가 더 많다.

 

 

(이 글이 도움이 됐다면 광고 한번씩만 클릭 해주시면 감사드립니다, 더 좋은 정보글 작성하도록 노력하겠습니다 :) )

---

https://github.com/srtktx/DataStructure_java

srtktx/DataStructure_java