#2-1 자료구조 - Stack, Queue

자료 구조의 종류와 구분

자바에서 자료 구조라 함은 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것이다.

위의 자료구조의 종류 중 가장 많이 사용하는 대표적인 4가지. Stack, Queue, Tree, Graph 에 대해 알아보자.

 

1. [Stack] // ex) 프링글스 통

Stack은 데이터를 넣을 공간을 생성함에 있어 그 공간이 다음과 같은 특이성을 가진다.

Stack은 Stack 클래스를 이용해 객체를 생성하여 사용할 수 있다.

Stack<Integer/String> stack = new Stack<>();

 

[1] FILO (선입후출) / LIFO (후입선출) 

[2] 데이터는 하나씩 넣고 뺄 수 있다.

[3] 하나의 입출력 방향을 가지고 있다.

[4] 그래프 탐색 중 깊이우선탐색(DFS)에 사용된다.

 

[Stack 메소드]

메소드	기능	예시
.push() .add(int)	데이터 1개씩 추가 / .add()는 int만 가능.	N.push();
.pop()	가장 최근에 추가된 데이터 삭제 //	System.out.println( N.pop());
.size()	스택안의 데이터 개수	System.out.println( N.size());
.peek()	맨 마지막에 추가된 값 출력	System.out.println( N.peek());
.clear()	스택의 모든 데이터 삭제	N.clear();
.empty() .isEmpty()	스택이 비었는지 아닌지 boolean 리턴	System.out.println( N.empty());
.contains(값)	스택이 특정 데이터 포함 유무 boolean 리턴	System.out.println( N.contains(값));
.search(값)	(값)이 뒤에서 몇번째 위치인지 나옴	System.out.println( stack.search(값));

 

2. [Queue] // 구멍뚫린 프링글스통

Queue는 인터페이스이므로, Stack과는 다르게 자체 객체선언을 할 수 없으며, LinkedList<>();를 통해 사용 가능하다.

Queue<Integer/String> queue = new LinkedList<>();

 

[1] FIFO (선입선출) / LILO (후입후출)

[2] 데이터는 하나씩 넣고 뺄 수 있다.

[3] 두 개의 입출력 방향을 가지고 있다.

[4] 중간에 값 추가가 불가능하며, 맨 뒤로만 데이터가 들어올 수 있다.

[5] 그래프의 넓이 우선 탐색(BFS)에 사용된다.

 

[Queue 메소드]

메소드	기능	예시
.offer() / .add()	데이터 추가, 순차적으로	N.offer(); / N.add();
.poll() / .remove()	앞쪽부터 데이터 삭제	N.poll(); / N.remove();
* .remove(값/index)	값/index 지우며 중복의 경우 앞쪽에 있는 값을 지운다.	*.remove(값/index)
.clear()	모든 데이터를 지운다.	N.clear();
.size()	Queue 안의 데이터 개수 구함.	System.out.println( N.size());
.peek()	맨 처음 넣은 값 확인.	System.out.println( N.peek());
is.Empty()	Queue가 비었는지 확인	N.isEmpty(); / !N.isEmpty();

[실제 코드 예시]

class Queue<T> { //객체를 만들때 데이터타입을 명시하도록 할 예정

    class Node<T> {
        private T data;     // 데이터를 선언하고
        private Node<T> next; // 다음 노드도 선언.

        public Node(T data) { // 생성자에서 해당타입의 데이터를 받아서
            this.data = data; // 내부 변수에 저장한다.
        }
    }

    private Node<T> first; // Queue는 앞 뒤로 주소를 알고있어야 하므로
    private Node<T> last; // 멤버 변수를 선언한다.

    public void add(T item) { // 추가할 T타입의 item을 매개변수로 받는다.
        Node<T> t = new Node<T>(item); // 그 item을 가지고 Node를 생성한다.

        if (last != null) { // 마지막 노드가 있다면
            last.next = t; // 그 뒤에 새로 생성한 노드를 붙이고
        }
        last = t; // t가 마지막 노드
        if ( first == null){  // 데이터가 없을 경우, 첫 노드도 null이므로 조건문 작성
            first = last;   // 처음 노드, 마지막 노드 같은 값을 할당.
        }
    }
    public T remove (T item) {
        if (first == null) { // Queue가 비어있을 경우
            throw new NoSuchElementException(); // Exception error 선언
        }

        //맨 앞에있는 데이터를 반환하기전에 그 다음 주소에 있는애들 first 만들어야하므로
        T data = first.data; // data 를 백업하고
        first = first.next; // 다음오는 애를 first로 선언.

        if ( first == null) { // first 가 비어있을때,
            last = null;      // last 도 같이 변경해줘야 한다.
        }
        return data;
    }
    public T peek() {           // T 타입을 반환한다.
        if (first == null) {    // 마찬가지로 null 체크.
            throw new NoSuchElementException();
        }
        return first.data;      // 현재 first가 가르키는 값을 반환.
    }

    public boolean isEmpty() {  // 마지막으로
        return first == null;   // first가 null 인지 반환
    }
}