자료구조 - 스택(Stack) / 큐(Queue)에 관하여...

스택 (Stack) /큐 (Queue)

스택과 큐는 각각 한쪽 끝에서만 데이터를 추가하고 제거하는 자료구조

데이터를 저장하고 관리하는 방식에 차이가 있음

 

스택 (Stack)

스택의 특징

• LIFO (Last In, First Out) : 마지막에 추가된 요소가 먼저 제거
• 데이터를 넣는 작업을 푸시 (Push) 
• 데이터를 빼는 작업을 팝 (Pop)

 

스택의 동작

• 스택의 최상단에 요소를 추가하거나 최상단에 요소를 제거할 수 있음
• 주로 함수 호출이나 재귀 알고리즘 등에 사용

 

스택의 예

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 정수를 저장하는 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소 추가 (푸시)
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // 스택의 최상단 요소 조회
        System.out.println("Top element of the stack: " + stack.peek());

        // 스택에서 요소 제거 (팝)
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);

        // 스택의 현재 크기 출력
        System.out.println("Size of the stack: " + stack.size());

        // 스택이 비어있는지 확인
        System.out.println("Is the stack empty? " + stack.isEmpty());
    }
}

 

 

큐 (Queue) / 덱 or 덱크(Deque)

큐의 특징

• FIFO (First In, First Out) : 처음에 추가된 요소가 가장 먼저 제거
• 데이터를 넣는 작업을 인큐 (Enqueue)
• 데이터를 빼는 작업을 디큐 (Dequeue)

 

큐의 동작

• 큐의 뒤쪽에 요소를 추가하거나 앞쪽에서 요소를 제거할 수 있음
• 대기열이나 작업 처리, 네트워크 버퍼 등에 사용

 

큐의 예

Java에서는 java.util.Queue 인터페이스를 사용하며, 이를 구현한 클래스로는 LinkedList나 ArrayDeque 등이 있습니다.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 정수를 저장하는 큐 생성
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 요소 추가 (인큐)
        queue.add(10);
        queue.add(20);
        queue.add(30);

        // 큐의 첫 번째 요소 조회
        System.out.println("Front element of the queue: " + queue.peek());

        // 큐에서 요소 제거 (디큐)
        int dequeuedElement = queue.poll();
        System.out.println("Dequeued element: " + dequeuedElement);

        // 큐의 현재 크기 출력
        System.out.println("Size of the queue: " + queue.size());

        // 큐가 비어있는지 확인
        System.out.println("Is the queue empty? " + queue.isEmpty());
    }
}

 

덱(Deque)의 형태

큐의 확장된 형태로, 양쪽 끝에서 요소의 추가와 제거가 모두 가능한 자료 구조입니다.

 

1. 양방향 큐

• 양쪽에서 요소를 추가하거나 제거하는 형태
• 큐의 맨 앞과 맨 뒤에서 모두 추가(Enqueue) 및 제거(Dequeue) 작업이 가능

 

2. 양방향 스택

• 양쪽에서 데이터를 추가하거나 제거할 수 있는 스택
• 스택의 맨 위와 맨 아래에서 모두 추가(Push) 및 제거(Pop) 작업이 가능

덱의 예

Java에서는 java.util.Deque 인터페이스를 사용하여 Deque를 구현합니다. 

구체적으로는 ArrayDeque나 LinkedList 클래스 등이 Deque 인터페이스를 구현한 클래스입니다.

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        // Deque 생성
        Deque<Integer> deque = new ArrayDeque<>();

        // 양쪽에서 데이터 추가 (Enqueue)
        deque.addFirst(10);   // 맨 앞에 추가
        deque.addLast(20);    // 맨 뒤에 추가

        // 데이터 조회
        System.out.println("Front element: " + deque.getFirst());
        System.out.println("Rear element: " + deque.getLast());

        // 양쪽에서 데이터 제거 (Dequeue)
        int removedFront = deque.removeFirst();   // 맨 앞에서 제거
        int removedRear = deque.removeLast();     // 맨 뒤에서 제거

        // 큐의 현재 크기 출력
        System.out.println("Size of the deque: " + deque.size());

        // Deque가 비어있는지 확인
        System.out.println("Is the deque empty? " + deque.isEmpty());
    }
}