Stack으로 Queue 구현하기

20230601 9:00 - 10:10

 

# 문제점 : 

오늘 튜터님의 알고리즘 특강을 들었는데, stack 2개를 갖고 queue를 구현하는 코드가 이해가 안됐다.

특강을 마치고 30분 정도 혼자 코드를 치며 공부해보았다.

 

내가 아는 부분들..

peek() : 맨 앞(혹은 위) 의 요소를 조회한다.

enqueue() : 요소 넣기

dequeue() : 요소 빼기

 

 

# 시도 :

 

그림을 그려가면서 하나하나 천천히 이해했다.

 

 

<<Stack>>
- peek
    - Stack의 Top(맨 위) 데이터를 보는 것
- push
    - Stack에 원소를 삽입합니다. Top에 들어감.
- pop
    - Stack의 Top에서 원소를 제거하며 가져옴

    - Peek와 다르게 조회가 아니라 조회 및 삭제

 

 

<<Queue>>
- peek
    - Queue의 Front(맨 앞) 데이터를 조회
- enqueue
    - Queue에 원소를 삽입합니다.

    - 원소는 Rear(맨 뒤)에 들어갑니다.
- dequeue
    - FIFO 자료구조니 Front(맨 앞)에 위치한 원소를 뽑아오게(제거 및 조회) 됩니다.

 

 

 

그런 후에 코드를 따라치고, 다시 지웠다가 혼자 코드를 작성해보았다.

package org.example.LL;

import java.util.Stack;

public class QueueWithStacks<E> {
    private Stack<E> inputStack;
    private Stack<E> outputStack;

    // 생성자 메서드로 Stack 생성.
    public QueueWithStacks() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }

    // Queue에 원소 삽입.
    // Queue에서 원소는 Rear(맨 뒤)에 들어갑니다.
    public void enqueue(E element) {
        inputStack.push(element);
    }

    // Front(맨 앞)에 위치한 원소를 뽑아오게(제거 및 조회) 됩니다.
    public E dequeue() {
        if(isEmpty()){
            throw new IllegalStateException("Queue is Empty.");
        }
        if(outputStack.isEmpty()){ //
            while(!inputStack.isEmpty()){
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.pop();
    }

    // 맨 앞위 요소를 가져오는 메서드
    // pop과 peek는 삭제 여부 관점에서의 차이점이 있음.
    public E peek() {
        if (isEmpty()){
            throw new IllegalStateException("Queue is Empty.");
        }
        if(outputStack.isEmpty()){
            while(!inputStack.isEmpty()){
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek();
    }

    private boolean isEmpty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }

    public int size() {
        return inputStack.size() + outputStack.size();
    }
}

혼자 코드를 따라치고 나니, 이해가 안되는 부분이 생겨 튜터님께 질문을 했다.

아래 peek() 메서드에서 왜 return outputStack 에서 pop() 이 아닌 peek() 를 해야 하는지 이해가 안됐다.

코드가 잘못 된건줄 알고 튜터님께 pop()이 아닌지 질문했다가 내가 제대로 이해하지 못했다는 사실을 깨달았다.

잘못 알고 있는 부분을 넘어가지 않고 제대로 학습하고 넘어가서 정말 다행이다.

    public E peek() {
        if (isEmpty()){
            throw new IllegalStateException("Queue is Empty.");
        }
        if(outputStack.isEmpty()){
            while(!inputStack.isEmpty()){
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek();
    }

 

# 새롭게 깨달은 점

peek()는 맨앞의 요소를 가져온 후에 삭제하는 pop()과는 엄연히 차이가 있다.

peek()는 그냥 맨 앞의 요소를 조회하는 메서드

pop()은 요소를 가져와서 삭제하는 메서드이다.

삭제 여부의 차이점이 있는 것이다.

 

 

List - Tim Sort를 활용하는데 이를 찾아보고 공부하기

merge sort, quick sort 등도 잘 알아둬야 함!!!

 

LinkedList<E> -> 데이터 타입이 아무거나 될 수가 있다. Generic 사용

 

HashSet은 Set Interface를 구현한 클래스로, 중복을 허용하지 않음.

순서가 없는 자료구조로 내부적으로 해시 테이블을 사용하여 요소들을 저장한다.

조회 : 해시테이블을 이용해서 O(1)내에 조회를 할 수 있다.

 

HashMap : 키를 기반으로 값 조회 가능

해시테이블 성격을 이해하기 (조회 검색,삽입삭제정렬의 시간복잡도는 O(1)

 

List, Set Map Queue Stack 과 같은 자료구조에 대한 이해도를 향상시켜야 함!!

 

<<정렬 시각화 사이트>>

https://visualgo.net/en/list

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

 

책읽는건 언제나 설렌다.

자바로 배우는 핵심 자료구조와 알고리즘 - YES24