Java) 큐(Queue) & 스택(stack) 처리 구조 이해하기

[자료구조]

큐(Queue)란?

: FIFO(First In, First Out) 구조

: 먼저 들어온 데이터가 먼저 처리되는 구조

: 처음에 들어온 데이터가 맨 앞에 위치

연산 : enqueue(삽입), dequeue(제거)

public void enqueue(E e){
    Node<E> newNode = new Node<>(e);
    if(top == null){          // top이 null일 때(비어있을 때)
        top = newNode;        // 새 노드를 첫 번째 노드로 설정
        cashNode = newNode;   // 첫 번째 노드가 없다는 건
        size++;               // 처음 데이터가 들어간거임.
        return;               // 그러므로 마지막 노드에도 새 노드를 넣어줌
    }

    cashNode.next(newNode);   // 기존 마지막 노드의 next를 새 노드로 설정
    cashNode = newNode;       // cashNode를 새 노드로 갱신(큐는 새로운 마지막 노드를 가리키게 된다.)
    size++;
}

public E dequeue(){
    if(top == null) return null;
    E res = top.data();      // top 노드의 데이터를 저장
    top = top.next();        // 잴 위에 큐 다음 노드로 이동(잴 위에 큐가 없어짐)
    size--;
    return res;
}

public boolean isEmpty(){
    return size == 0;
}

: cashNode는 현재 큐의 마지막 노드

: top은 현재 큐의 첫 번째 노드

: 구조 파악하는 건 코드 주석 읽어보면서 생각해보면 쉽게 이해될것임!

public static void main(String[] args) {
    _Queue<Integer> queue = new _Queue<>();    // 빈 큐로 초기화
    for (int i = 0; i < 10; i++) {             // top = null, cashNode = null, size = 0
        queue.enqueue(i);
    }

    for (int i = 0; i < 10; i++) {
        System.out.println(queue.dequeue());
    }
}

enqueue : 

: top -> 0, 1, 2, 3 -> ... -> 9 <- cashNode

 

dequeue :

첫 번째 호출

: top -> 0, 1, 2, 3 -> ... -> 9 <- cashNode

두 번째 호출

: top -> 1, 2, 3 -> ... -> 9 <- cashNode

세 번째 호출

: top -> 2, 3 -> ... -> 9 <- cashNode

 

결과 : 

0, 1, 2, 3, 4, 5, 6, 7, 8 ,9

먼저 처리된 순 ----->

---

 

스택(Stack)란?

: LIFO(List In, First Out) 구조

: 마지막에 들어온 데이터가 먼저 처리되는 구조

: 마지막으로 추가된 요소가 스택의 맨 위에 위치

연산 : push(삽입), dequeue(제거)

public void push(E e){

    Node<E> newNode = new Node<>(e); // 새 노드 생성
    if(top != null){                 // 기존 스택이 비어 있지 않으면
        newNode.next(top);           // 새 노드의 next를 현재 top에 연결
    }

    top = newNode;                   // 새 노드를 스택의 가장 위에 추가했으므로, 
    size++;                          // top이 새 노드를 가리키게 된다.
}

public E pop(){
    if(top == null) return null;     // 삭제할 항목이 없으므로 null 반환
    E res = top.data();              // 현재 top 노드 값을 저장
    top = top.next();                // top을 삭제하고 다음 값을 top으로 지정
    size--;
    return res;
}

public E peek(){                     // 스택의 맨 위에 있는 데이터를 반환
    if(top == null) return null;
    return top.data();               // 스택의 맨 위 요소 반환
}

public boolean isEmpty(){            // 스택이 비어 있는지 확인
    return size == 0;
}

: top은 스택에 새 요소를 추가하면, 그 요소가 스택의 맨 위에 위치하므로 top이 이를 가리키도록 갱신

public static void main(String[] args) {
    _Stack<Integer> stack = new _Stack<>();

    for(int i = 0; i < 10; i++){
        stack.push(i);
    }

    for(int i = 0; i < 10; i++){
        System.out.println(stack.pop());
    }
}

 

push 했을 때 상태 변화 :

반복( i )	추가된 값	스택 상태	top의 위치	size
0	0	[0]	top -> 0	1
1	1	[1, 0]	top -> 1 -> 0	2
2	2	[2, 1, 0]	top -> 2 -> 1 -> 0	3
...	...	...	...	...
9	9	[9, 8, 7, ... 2, 1, 0]	top-> 9 -> ... -> 0	10

 

pop 했을 때 상태 변화 :

반복( i )	제거된 값	스택 상태	top의 위치	size
0	9	[8, 7, 6, ... 2, 1, 0]	top -> 8 -> ... -> 0	9
1	8	[7, 6, ... 2, 1, 0]	top -> 7 -> ... -> 0	8
2	7	[6, ... 2, 1, 0]	top -> 6 -> ... -> 0	7
...	...	...	...	...
9	9	[ ] (비어 있음)	top = null	0

 

결과 : 

9, 8, 7, 6, 5, 4, 3, 2, 1, 0

먼저 처리된 순 ----->