자료구조 - 스택 , 큐 , 데크(Stack , Queue, Deque) Java

Java 에서는 스택 ,큐, 데크 와 같이 라이브러리를 제공해 주고 있으며 Java에 ArrayList 를 활용하면  스택,큐,데크와 같이 기능을 만들어 낼 수 있다.

 

 

스택 ( Stack ) 

• 스택 자료 구조는 후입선출(First in Last out) (Last In First Out) 이라고도 하는 자료구조이다
• 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용한다.

스택 기본 구조

• 후입 선출 구조
• 기본적으로 데이터 추가(push), 꺼내기(pop), 스택 공간 확인 동작이 이루어짐

 

 

JAVA 소스코드 (Stack 라이브러리)

public class stack {
    public static void main(String[] args) {
        Stack stack = new Stack();
        IntStream.range(1,6).forEach(x->stack.push(x));


        System.out.println(stack);

        System.out.println(stack.pop());
        System.out.println(stack);

        System.out.println(stack.peek());
        System.out.println(stack);

        System.out.println(stack.contains(3));
        System.out.println(stack.size());
        System.out.println(stack.empty());
        stack.clear();
        System.out.println(stack);
    }
}

 

출력 결과

출력결과

Stack.push () : Stack 구조에 데이터 삽입

Stack.pop()  : Stack 의 맨 마지막 데이터 제거

Stack.peek() : Stack 의 맨마지막 데이터 출력 (제거 X)

Stack.contains(data) : Stack 안에 데이터 존재 여부 return T/F

Stack.size() : Stack 사이즈

Stack.empty() : Stack의 empty 여부

Stack.clear() : 모두 제거

 

 

 

 

---

 

큐 (Queue) 

• 선입선출 ( First in First Out : FIFO) 자료 구조이다.
• 입력순서대로 데이터 처리가 필요할 때 사용 (BFS, 대기 순)

 

 

Java 소스코드(Queue 라이브러리)

 

public static void main(String[] args) {
        Queue queue = new LinkedList<>();
        IntStream.range(1,6).forEach(x->queue.add(x)); // 큐 데이터 추가


        System.out.println(queue);

        System.out.println(queue.poll()); // 큐 데이터 제거
        System.out.println(queue);

        System.out.println(queue.peek()); // 큐 peek 
        System.out.println(queue);

        System.out.println(queue.contains(3)); // 큐 존재 여부
        System.out.println(queue.size()); //큐 사이즈
        System.out.println(queue.isEmpty()); // 큐 Empty 여부
        queue.clear(); // 큐 제거
        System.out.println(queue);
    }

 

출력결과

 

 

큐에서 조심해야 할 점

Queue queue = new LinkedList<>();

 

자바에서 Queue 라이브러리를 사용할려면 LinkedList<> 를 사용하여 다향성을 이용해 Queue를 사용해야한다

Queue que = new Queue(); 

이런 식의 Queue사용을 하려면 Queue가 인터페이스로 정의되어있어 재정의가 필요로 하다.

---

데크 (DeQue)

• 양방향 삽입 삭제 모두가 가능한 Queue 자료구조 (Stack + Queue)

 

Java 소스코드 (Deque 라이브러리)

 

 

public static void main(String[] args) {
        Deque deque = new ArrayDeque();


        IntStream.range(1,4).forEach(x -> deque.addFirst(x)); // 데이터 왼쪽으로추가  (Front 추가)
        System.out.println(deque);
        IntStream.range(10,13).forEach(x -> deque.addLast(x)); // 데이터 오른쪽에 추가 (Rear 추가)
        System.out.println(deque);

        System.out.println(deque.removeFirst()); // 데이터 Front 삭제
        System.out.println(deque);
        System.out.println(deque.removeLast()); // 데이터 Rear 삭제
        System.out.println(deque);
    }

 

출력결과

 

Deque 도 마찬가지로 Deque 자료구조를 생성할때

Deque deq = new Deque(); 

를 한다면 재정의가 필요하므로  ArrayDeque();를 사용해준다.

 

 

 

---

ArrayList 활용 코드

class MakeArrayListSQD{
    ArrayList list;

    MakeArrayListSQD(){
        this.list = new ArrayList();
    }
    public boolean isEmpty(){
        if(this.list.size() == 0){
            return true;
        }
        else{
            return false;
        }

    }
    public void push(int data){
        this.list.add(data);
    }
    public Integer pop(){
        if(this.isEmpty()){
            return null;
        }
        int data = (int)this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
    }
    public Integer peek(){
        int data = (int)this.list.get(this.list.size()-1);
        return data;
    }
    public void printStack(){
        System.out.println(this.list);
    }
}

 

Stack , Queue , Deque 는 자바에서 ArrayList 를 활용하여 같은 기능을 만들어 줄 수 있고 위에 소스코드는 Stack 을 기반으로 만들어진 소스 코드이다.

Queue , Deque도 비슷하게 ArrayList 로 구현할 수 있다.