Stack, Queue 구현

Stack 이란 ?

Stack 은 후입선출(Last in First Out) 구조로 나중에 들어온 값이 먼저 나가게 되는 박스형 구조입니다.

출처 : https://yoongrammer.tistory.com/45

Java 에서 Stack 은 Stack 클래스를 사용할 수 있습니다.

Java 에서 제공하는 Stack 클래스는 Stack 내 원소에 접근하는 연산에 synchronized 키워드가 붙어있습니다.

Stack 클래스의 pop

즉 멀티스레드 환경에서 안전하게 사용할 수 있지만 코딩테스트 환경에서는 멀티스레드 환경이 아니기에 이를 고려할 필요가 없습니다.

따라서 코딩테스트나 단일 스레드 환경에서는 Stack 클래스가 아닌 ArrayDeque 을 사용해서 Stack 처럼 사용하는 것이 권장됩니다.

 

구현한 메서드는 다음과 같습니다.

• push : 원소를 Stack에 삽입
• pop : Stack의 가장 위에 위치한 원소를 제거하고 반환
• peek : Stack의 가장 위에 위치한 원소를 반환
• size : Stack 의 사이즈를 반환
• isEmpty : Stack이 비었는지 확인
• isFull : Stack이 가득찼는지 확인

class ArrayStack {
    private int capacity;
    private int top;
    private int[] stack;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.top = -1;
        this.stack = new int[capacity];
    }

    public void push(int value) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full");
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public int size() {
        return top + 1;
    }
}

 

---

Queue 란 ?

Queue 는 선입선출(First In First Out) 구조로 먼저 들어온 값이 먼저 나가게 되는 원통형 구조입니다.

출처 : 나무위키

 

Java 에서는 Queue 인터페이스가 있고 대표적인 구현체로 LinkedList 가 있습니다.

Queue 의 특징은 끝에서는 삽입하는 연산만을 하고, 다른 끝에서는 삭제하는 연산만을 합니다.

 

구현한 메서드는 다음과 같습니다.

• enqueue : 원소를 Queue에 삽입
• dequeue : 원소를 Queue에서 꺼내어 반환
• peek : Queue 의 가장 앞에 있는 원소를 반환
• isEmpty : Queue 가 비었는지 확인
• isFull : Queue 가 가득 찼는지 확인
• size : Queue 의 사이즈를 반환

class ArrayQueue {
    private int size;
    private int[] queue;
    private int front;
    private int rear;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        rear = (rear + 1) % capacity;
        queue[rear] = value;
        size++;
    }

    public int dequeue () {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    public int peek() {
        if(isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        return queue[front];
    }

    public int size() {
        return this.size;
    }

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

    public boolean isFull() {
        return size == capacity;
    }
}