📌 Node를 이용한 Stack 구현

🔥 코드

public class StackStructure {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);

        stack.pop();

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }
    static class Stack<T>{
        class Node<T>{
            private T data;
            private Node<T> next;

            public Node(T data){
                this.data =data;
            }
        }
        private Node<T> top;

        public T pop(){
            if( top == null ) throw new EmptyStackException();

            T item = top.data;
            top = top.next;
            return item;
        }
        public void push(T item){
            Node<T> t = new Node<T>(item);
            t.next = top;
            top=t;
        }
        public T peek(){
            if(top == null){
                throw new EmptyStackException();
            }
            return top.data;
        }
    }
}

📌 Node를 이용한 Queue 구현

🔥 코드

public class QueueStructure {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.offer(1);
        q.offer(2);

        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.poll());

    }
    static class Queue<T>{
        class Node<T>{
            private T data;
            private Node next;

            public Node(T data){
                this.data=data;
            }
        }

        private Node<T> first;
        private Node<T> last;

        public void offer(T item){
            Node<T> t = new Node<T>(item);

            if(last!=null){
                last.next=t;
            }
            last = t;
            if(first==null){
                first=last;
            }
        }

        public T poll(){
            if(first==null) throw new NoSuchElementException();

            T data = first.data;
            first=first.next;

            if(first==null){
                last=null;
            }
            return data;
        }
        public T peek(){
            if(first==null){
                throw new NoSuchElementException();
            }
            return first.data;
        }
        public boolean isEmpty(){
            return first==null;
        }
    }
}

📌 두 개의 스택으로 큐 구현하기

• 값을 일단 new stack에 담는다.

• peek() 이나 poll() 메소드가 호출되면 new에 있는 값들을 old로 옮긴다.

• peek() 이나 poll() 이 호출되면 old에 있는 것으로 수행한다.

• old에 값이 없는데 호출이 됐다면 ?

• new에서 다시 old로 값을 옮긴다.

🔥 코드

public class QueueWithTwoStacks {
    public static void main(String[] args) {
        CustomQueue q= new CustomQueue();

        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);
        q.offer(6);

        System.out.println(q.peek());
        System.out.println(q.poll());
        System.out.println(q.poll());
        System.out.println(q.peek());

    }

    static class CustomQueue {
        Stack<Integer> firstStack = new Stack<>();
        Stack<Integer> secondStack = new Stack<>();

        void offer(int k) {
            firstStack.push(k);
        }

        Integer poll() {
            if (secondStack.isEmpty()) {
                while(!firstStack.isEmpty()){
                    secondStack.push(firstStack.pop());
                }
            }
            return secondStack.pop();
        }

        Integer peek() {
            if (secondStack.isEmpty()) {
                while(!firstStack.isEmpty()){
                    secondStack.push(firstStack.pop());
                }
            }
            return secondStack.peek();
        }
    }
}