[Java] LinkedList로 구현한 Stack과 Queue

LinkedList

https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.boardinfinity.com%2Fblog%2Flinkedlist-in-java%2F&psig=AOvVaw0pywsDsy5RdKBM6n_VNJs1&ust=1715264254075000&source=images&cd=vfe&opi=89978449&ved=0CBIQjRxqFwoTCLjdyrmf_oUDFQAAAAAdAAAAABA1

Queue를 구현할 때 Head(front) Tail(rear)가 필요합니다.
Stack은 Head만 필요합니다.

class LinkedNode<E> {
    E value;
    LinkedNode<E> next;

    public LinkedNode(E value, LinkedNode<E> next) {
        this.value = value;
        this.next = next;
    }
}

(Java에 기본적으로 LinkedList가 있어 LinkedNode로 선언했습니다.)

배열과 다르게 길이 제한 없이 사용가능한 자료구조입니다.
레퍼런스 값 next를 통해 같은 형태의 다음 값으로 이동합니다.
저장하고 탐색하는 방법에 따라 Stack, Queue, Deque등을 만들때 활용할 수 있습니다.
Type을 유연하게 사용하고 싶어 제네릭을 활용했습니다.

---

Stack

https://www.google.com/url?sa=i&url=https%3A%2F%2Fko.wikipedia.org%2Fwiki%2F%25EC%258A%25A4%25ED%2583%259D&psig=AOvVaw22ACMbbNBhkVvlSrtkGnr3&ust=1715264700627000&source=images&cd=vfe&opi=89978449&ved=0CBIQjRxqFwoTCOCo8Yqh_oUDFQAAAAAdAAAAABAE

Java의 메모리 영역 중 Stack.  (https://goldenrabbit.co.kr/2021/11/03/자바-코드와-메서드-스태틱-변수-등은-메모리의-어디/)

class LinkedStack<E> {
    LinkedNode<E> head;

    public LinkedStack() {
    }

    public LinkedStack(LinkedNode<E> head) {
        this.head = head;
    }

    public void push(E value) {
        head = new LinkedNode<>(value, head);
    }

    public E peek() {
        if (this.empty()) {
            System.out.println("stack is empty");
            return null;
        }
        return head.value;
    }

    public E pop() {
        if (this.empty()) {
            System.out.println("stack is empty");
            return null;
        }
        E value = head.value;
        head = head.next;
        return value;
    }

    public boolean empty() {
        return head == null;
    }

    public boolean isEmpty() {
        return this.empty();
    }
}

LIFO, 후입선출, 나중에 들어간 것이 먼저 나오는 자료구조 Stack 입니다. 위의 Java 메모리 영역으로도 사용되는데, 간단하게 설명하면 프링글스, 하노이탑입니다.

---

Queue

https://namu.wiki/w/큐%28자료구조%29

class LinkedQueue<E> {
    LinkedNode<E> front, rear;

    public LinkedQueue() {

    }

    public LinkedQueue(LinkedNode<E> node) {
        this.front = node;
        this.rear = node;
    }

    public void offer(E value) {
        if (front == null) {
            this.front = new LinkedNode<>(value, null);
            this.rear = this.front;
        } else {
            this.rear.next = new LinkedNode<>(value, null);
            this.rear = this.rear.next;
        }
    }

    public void add(E value) {
        this.offer(value);
    }

    public E peek() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return null;
        }
        return front.value;
    }

    public E poll() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return null;
        }
        E value = front.value;
        front = front.next;
        return value;
    }

    public boolean isEmpty() {
        return front == null;
    }
}

FIFO, 선입선출, 먼저 넣은 것이 먼저 나오는 자료구조 Queue입니다. 게임을 할 때에 "큐를 돌린다" 그러한 말이 있는데, 대기열이 큐 입니다. 버퍼, 캐시를 구현할 때 큐를 활용합니다.

테스트 코드 및 Java 기본 제공 자료구조

@Test
@DisplayName("stackAndQueue")
void test() {
    LinkedStack<Integer> stack = new LinkedStack<>();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    while (!stack.empty()) {
        System.out.println(stack.pop());
    }
    System.out.println();

    Stack<Integer> javaStack = new Stack<>();
    javaStack.push(Integer.valueOf(1));
    javaStack.push(Integer.valueOf(2));
    javaStack.push(Integer.valueOf(3));
    javaStack.push(Integer.valueOf(4));
    while (!javaStack.empty()) {
        System.out.println(javaStack.pop().intValue());
    }
    System.out.println();

    LinkedQueue<Integer> queue = new LinkedQueue<>();
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    queue.offer(4);
    while (!queue.isEmpty()) {
        System.out.println(queue.poll());
    }

    Queue<Integer> javaQueue = new LinkedList<>();
    javaQueue.offer(1);
    javaQueue.offer(2);
    javaQueue.offer(3);
    javaQueue.offer(4);
    while (!javaQueue.isEmpty()) {
        System.out.println(javaQueue.poll());
    }
}

주의할 점으로, Java의 Stack은 Stack class가 있는데, Queue등은 inteface로, LinkedList 등으로 구현해야 합니다.