자료구조(스택, 큐, 데크)

Yunsung·2025년 1월 15일

1. 스택(Stack)

스택은 "후입선출" (LIFO: Last In First Out) 원칙을 따르는 자료구조입니다. 스택에서는 데이터가 한쪽 끝(top)에서만 삽입(push)과 삭제(pop)이 이루어집니다.

주요 특징

LIFO(Last In, First Out): 마지막에 삽입된 데이터가 먼저 나옵니다.
데이터 삽입(push)과 삭제(pop): 한쪽 끝에서만 이루어집니다.
활용 예: 웹 브라우저의 뒤로 가기, 함수 호출 관리, 문자열 뒤집기 등
Stack을 구현할 때는, 원소를 제거해야 하는 ArrayList보다는 index를 조정하고, 초기화 하는 방식과 함께 Array를 사용하는 것이 유리합니다.

스택 (Stack) 구현

public class Stack {
	private int[] stack;
    private int top;
    
    // 생성자
    public Stack(int capacity) {
    	stack = new int[capacity];
        top = -1; // 스택이 비어있다면 top은 -1
    }
    
    // 스택이 비어있는지 확인
    public boolean isEmpty() {
    	return top == -1; 
    }
    
    // 스택이 가득 찼는지 확인(현재 차있는 위치가 꼭대기인지 확인)
    public boolean isFull() {
    	return top == stack.length-1;
    }
    
    // 데이터를 스택에 추가
    public void push(int value) {
    	if(isFull()) {
        	System.out.println("스택이 가득 찼습니다!!");
        } else {
        	stack[++top] = value;
        }
    }
    
    // 스택에서 데이터 제거(논리적 제거)
    public int pop() {
    	if(isEmpty()) {
        	System.out.println("스택이 비어 있습니다!!");
            return -1;
        } else {
        	return stack[top--];
        }
    }
    
    // 스택 top 값 확인
    public int peek() {
    	if(isEmpty()) {
        	System.out.println("스택이 비어 있습니다!!");
            return -1;
        } else {
        	return stack[top];
        }
    }
}

2. 큐(Queue)

큐는 "선입선출" (FIFO: First In First Out) 원칙을 따르는 자료구조입니다. 큐에서는 한쪽 끝(rear)에서 삽입(enqueue)이, 다른 쪽 끝(front)에서 삭제(dequeuq)가 이루어집니다.

주요 특징

FIFO(First In, First Out): 가장 먼저 들어간 데이터가 가장 먼저 나옵니다.
데이터 삽입(enqueue)과 삭제(dequeue): 두 끝에서 처리됩니다.
활용 예: 프린터 대기열, 은행 창구 대기 시스템 등

큐 (Queue) 구현

import java.util.LinkedList;

public class Queue {
    private LinkedList<Integer> list;

    // 생성자
    public Queue() {
        this.list = new LinkedList<>();
    }

    // 큐에 데이터 추가 (enqueue)
    public void enqueue(Integer value) {
        this.list.addLast(value);  // 데이터를 뒤쪽에 추가
    }

    // 큐에서 데이터 제거 (dequeue)
    public Integer dequeue() {
        if (this.list.isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return this.list.removeFirst();  // 첫 번째 데이터 제거
    }

    // 큐의 첫 번째 값 확인 (peek)
    public Integer peek() {
        if (this.list.isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return this.list.getFirst();  // 첫 번째 값 반환
    }

    // 큐가 비었는지 확인
    public boolean isEmpty() {
        return this.list.isEmpty();
    }

    public static void main(String[] args) {
        Queue queue = new Queue();

        // 데이터 추가
        queue.enqueue(1);
        queue.enqueue(2);

        // 데이터 제거
        System.out.println(queue.dequeue()); // 1
        System.out.println(queue.dequeue()); // 2
        System.out.println(queue.dequeue()); // Queue is empty, -1
    }
}