Stack & Queue with Java

Stack과 Queue는 배열 혹은 연결 리스트로 구현할 수 있지만 배열로 구현하였다.

Stack은 Java에서 클래스 형태로 제공하지만 Queue는 인터페이스로 제공하기 때문에 구현을 해줘야한다.

---

[Stack]

Stack은 리스트의 특수한 형태로 데이터를 리스트의 맨 앞, 맨 뒤에서만 작업할 수 있다. 

맨 앞에서는 삽입, 맨 뒤에서는 삭제만 할 수 있는 Last in First Out 구조로 되어있다. 즉 제일 먼저 넣은 원소는 제일 마지막에 꺼낼 수 있다.

 

[Implemented Methods]

• push : 데이터를 삽입
• pop : 데이터를 삭제
• peek : 맨 위에 있는 데이터를 읽기
• isEmpty : 스택이 비어있는지 확인
• size : 스택의 크기를 반환

[생성자]

public class MyStack<E> {
    private int size;
    private int top;
    private Object[] stackArray;

    public MyStack(int size) {
        this.size = size;
        this.top = -1;
        stackArray = new Object[size];
    }

    public MyStack() {
        this.size = 64;
        this.top = -1;
        stackArray = new Object[size];
    }
}

• size : 스택의 크기
• top : 스택의 제일 윗쪽 인덱스
• stackArray : 스택을 배열의 형태로 구현

생성자를 통해서 크기를 지정하지 않으면 크기가 64인 스택을 생성하게 했다.

 

push(E value)

    public void push(E value) throws StackOverflowError {
        if (isFull()) {
            throw new StackOverflowError();
        }
        stackArray[++top] = value;
    }

• 데이터를 삽입하는 메소드
• 스택이 꽉 찼다면 더 이상 넣을 수 없다. ArrayList를 사용하거나 배열의 크기를 동적으로 늘리는 방법이 있지만 간단하게 구현해 보기 위해서 사이즈를 정해놨다.
• 스택에 push 할 수 있다면 ++top한 인덱스에 값을 넣는다. (처음에 top = -1로 초기화 했음)

E pop()

    public E pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            return (E) stackArray[top--];
        }
    }

• 데이터를 제거하는 메소드다. 제일 마지막에 들어간 데이터를 제거한다
• 스택이 비어있으면 pop할 데이터가 없다
• top--인 이유는 먼저 데이터를 제거하고 인덱스를 줄여야하기 때문이다. 줄이고 pop 해버리면 다음 값이 제거된다

E peek()

    public E peek() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            return (E)stackArray[top];
        }
    }

• 원소를 제거하지 않고 맨 위의 값을 읽어온다

isEmpty() & isFull()

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

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

• 배열이 비어있거나 꽉 차있는지 확인
• size - 1은 top을 0이 아닌 -1부터 시작했기 때문

테스트해보기

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

        try {
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);

            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack.isFull() = " + stack.isFull());
            stack.printStack();
            System.out.println();

            System.out.println("stack.peek() = " + stack.peek());
            System.out.println("stack.pop() = " + stack.pop());
            System.out.println("stack.peek() = " + stack.peek());
            System.out.println("stack.pop() = " + stack.pop());
            stack.printStack();
        } catch (Exception e) {
            System.out.println("error");
        }
    }

stack.isEmpty() = false
stack.isFull() = false
1 
2 
3 
4 
5 

stack.peek() = 5
stack.pop() = 5
stack.peek() = 4
stack.pop() = 4
1 
2 
3

전체코드

package datastructure;

import java.util.EmptyStackException;

public class MyStack<E> {
    private int size;
    private int top;
    private Object[] stackArray;

    public MyStack(int size) {
        this.size = size;
        this.top = -1;
        stackArray = new Object[size];
    }

    public MyStack() {
        this.size = 64;
        this.top = -1;
        stackArray = new Object[size];
    }

    public void push(E value) throws StackOverflowError {
        if (isFull()) {
            throw new StackOverflowError();
        }
        stackArray[++top] = value;
    }

    public E pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            return (E) stackArray[top--];
        }
    }

    public E peek() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            return (E)stackArray[top];
        }
    }

    public void printStack() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            for (int i=0; i<=top; i++) {
                System.out.println(stackArray[i] + " ");
            }
        }
    }

    public void clear() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        else {
            top = -1;
            System.out.println("Stack Cleared");
        }
    }

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

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

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

        try {
            stack.push(1);
            stack.push(2);
            stack.push(3);
            stack.push(4);
            stack.push(5);

            System.out.println("stack.isEmpty() = " + stack.isEmpty());
            System.out.println("stack.isFull() = " + stack.isFull());
            stack.printStack();
            System.out.println();

            System.out.println("stack.peek() = " + stack.peek());
            System.out.println("stack.pop() = " + stack.pop());
            System.out.println("stack.peek() = " + stack.peek());
            System.out.println("stack.pop() = " + stack.pop());
            stack.printStack();
        } catch (Exception e) {
            System.out.println("error");
        }
    }
}

 

---

[Queue]

Queue는 Stack과 다르게 먼저 들어간 데이터가 먼저 나오는 First in First Out 구조를 갖고 있다.

Stack과 다르게 배열의 양쪽 끝에서 작업을 할 수 있다.

 

[Implemented Methods]

• offer(enqueue) : 데이터를 삽입
• poll(dequeue) : 데이터를 삭제
• peek : 제일 마지막 데이터 읽기
• isEmpty : 비어있는지 확인
• size : 크기를 반환

[생성자]

public class MyQueue<T> {
    private T[] array;
    private int size;
    private int front;
    private int rear;

    public MyQueue(int size) {
        array = (T[]) new Object[size];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }

    public MyQueue() {
        array = (T[]) new Object[64];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }
}

• array : 배열을 사용해서 구현
• size : Queue의 사이즈
• rear : rear은 -1로 초기화한다. 즉 -1이라는 것은 Queue가 비어있다는 뜻이다. 그리고 처음으로 데이터가 삽입이 된다면 0으로 바뀌고 첫번째 원소를 가리키게 된다.

offer(T value)

    public void offer(T value) {
        if (size == array.length) {
            throw new IllegalStateException("Queue Full");
        }
        // rear = (rear + 1) % array.length;
        array[rear++] = value;
        size++;
    }

주석으로 처리한 부분은 Queue를 링버퍼의 형식으로 구현하게 된다면 사용하는 코드이다.

하지만 간단하게 이번 코드에서는 배열로 처리해볼것이다.

 

T poll()

   public T poll() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is Empty");
        }
        T value = array[front++];
        // front = (front + 1) % array.length;
        size--;
        return value;
    }

• 데이터를 삭제하는 것이기 때문에 front의 인덱스를 증가시킨다

T peek()

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is Empty");
        }
        return array[front];
    }

isEmpty() & size()

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

    public int size() {
        return size;
    }

 

테스트해보기

    public static void main(String[] args) {
        MyQueue<Integer> mq = new MyQueue<>();
        mq.offer(1);
        mq.offer(2);
        mq.offer(3);
        mq.offer(4);
        System.out.println("mq.peek() = " + mq.peek());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());
    }

stack.isEmpty() = false
stack.isFull() = false
1 
2 
3 
4 
5 

stack.peek() = 5
stack.pop() = 5
stack.peek() = 4
stack.pop() = 4
1 
2 
3

전체코드

package datastructure;

public class MyQueue<T> {
    private T[] array;
    private int size;
    private int front;
    private int rear;

    public MyQueue(int size) {
        array = (T[]) new Object[size];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }

    public MyQueue() {
        array = (T[]) new Object[64];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }

    public void offer(T value) {
        if (size == array.length) {
            throw new IllegalStateException("Queue Full");
        }
        // rear = (rear + 1) % array.length;
        array[rear++] = value;
        size++;
    }

    public T poll() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is Empty");
        }
        T value = array[front++];
        // front = (front + 1) % array.length;
        size--;
        return value;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is Empty");
        }
        return array[front];
    }

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

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        MyQueue<Integer> mq = new MyQueue<>();
        mq.offer(1);
        mq.offer(2);
        mq.offer(3);
        mq.offer(4);
        System.out.println("mq.peek() = " + mq.peek());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());
        System.out.println("mq.poll() = " + mq.poll());

    }
}