[TIL] Stack, Queue, HashTable 구현하기

*20221115의 회고

 

   어제 구현했던 연결리스트를 이용하여 오늘은 stack, queue, hashtable을 구현하였다. 구현하는 코드를 보고 한번에 이해하는 데는 어려움이 있었다. 그러나 두 번, 세 번 반복해서 보니 아직 안보고 직접 구현하는 건 자신 없지만, 코드를 보면서 이해하는데는 어렵지 않게 되었다.

 

   스택, 큐, 해시테이블의 정의와 특징, 그리고 구현한 코드에 대해 정리해 보겠다.

 

• 스택(Stack) 
  • 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조
  • Last In, First Out (LIFO)
  • stack.push() : 스택에 맨 위에 데이터를 넣는다.
  • stack.pop() : 스택의 맨 위에 있는 데이터를 꺼내어 반환한다(스택 사이즈 -1).
  • stack.peek() : 스택의 맨 위에 있는 데이터를 꺼내진 않고 값을 반환한다(스택 사이즈 변화X).
  • stack.isEmpty() : 스택이 비어있으면 true, 아니면 false를 반환한다.

import java.util.EmptyStackException;

class MyStack<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; //item 변수에 기존의 맨 위에 있던 데이터를 저장
        top = top.next; //맨 위의 데이터를 그 다음 데이터로 바꿔줌 -> 맨 위 데이터 삭제
        return item;
    }

    public void push(T item) {
        Node<T> newNode = new Node<>(item); //item의 값을 가진 새로운 노드 생성
        newNode.next = top; 새로운 노드의 다음 노드를 현재 맨 위의 데이터로 지정 -> 새로운 노드가 맨 위가 될 수 있음
        top = newNode; //맨 위에 새로운 노드 넣어줌
    }

    public T peek() {
        if (top == null) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null; //top이 null 이면 true, 아니면 false 반환
    }
}

 

 

• 큐(Queue) 
  • 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조
  • First In, First Out (FIFO)
  • queue.add() : 큐에 데이터를 넣는다.
  • queue.remove() : 큐의 맨 앞에 있는 데이터를 꺼내어 반환한다(큐 사이즈 -1).
  • queue.peek() : 큐의 맨 앞에 있는 데이터를 꺼내진 않고 값을 반환한다(큐 사이즈 변화X).
  • queue.isEmpty() : 큐가 비어있으면 true, 아니면 false를 반환한다.

import java.util.NoSuchElementException;

class MyQueue<T> { //큐 구현하기
    class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data) { //생성자
            this.data = data;
        }
    }

    private Node<T> first; //제일 첫번째의 노드
    private Node<T> last; //제일 마지막의 노드

    public void add(T item){ //큐에 데이터 넣기
        Node<T> newNode = new Node<>(item);

        if(last != null) { //큐에 데이터가 있는 경우
            last.next = newNode; //가장 마지막 노드가 본인 다음으로 새로운 노드를 가리킴
        }
        last = newNode; //마지막 노드에 새로운 노드 넣어줌
        if(first == null) { //큐에 데이터가 없는 경우
            first = last; //첫번째 노드와 마지막 노드가 같다고 해줘야함
        }
    }

    public T remove() {
        if(first == null) { //큐가 비어있을 때
            throw new NoSuchElementException();
        }
        T data = first.data; //삭제 전, T형 data 변수에 기존의 first 데이터 미리 저장
        first = first.next; //첫번째 노드에 기존의 첫번째 노드의 다음노드를 넣어줌 -> 첫번째 노드 삭제됨

        if(first == null)
            last = null; //큐가 비게 되면 첫번째 노드와 마지막 노드의 값은 다 null이여야 한다.

        return data;
    }

    public T peek() {
        if(first == null) { //큐가 비어있을 때
            throw new NoSuchElementException();
        }
        return first.data; //첫번째 노드의 data를 보여줌
    }

    public boolean isEmpty() {
        return first == null; //큐가 비면 true, 아니면 false를 반환
    }
}

 

 

• 해시테이블(HashTable) 
  • 컴퓨팅에서 키를 값에 매핑하는 자료구조(key, value 쌍)
  • 해시함수(key) -> HashCode -> Index -> Value
  • 검색하고자 하는 key 값을 입력받아서 해시함수를 돌린 후 받은 해시코드를 배열의 인덱스로 환산(배열의 크기로 나눈 나머지)
  • 그 인덱스로 데이터에 접근하는 방식의 자료구조.
  • key 값을 가진 자료에 바로 접근하기 때문에 검색 속도가 매우 빠르다.
  • 입력받은 key 를 가지고 인덱스를 얼마나 골고루 잘 분배하느냐에 따라 좋은 해시함수 알고리즘인지 결정된다.
  • 해시테이블의 필수조건 중 하나 -> 고정된 크기의 배열을 우선 선언함(HashCode 로 index 값 먼저 구해야 하기 때문)
  • 같은 인덱스를 가진 값 여러개 존재 가능(collision) => 배열 방 안에 LinkedList 로 구현해서 데이터 충돌을 막아줌

import java.util.LinkedList;

class MyHashTable { //해시테이블 구현하기
    class Node {
        String key;
        String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        String getValue() {
            return value;
        }

        void setValue(String value) {
            this.value = value;
        }
    }

    LinkedList<Node>[] data; //(Node(key와 value를 가지는 객체)를 원소로 가지는 LinkedList형) 배열 data 생성

    MyHashTable(int size) { //생성자
        this.data = new LinkedList[size]; //생성과 동시에 크기가 size인 linkedlist형 배열 data 생성(= 리스트를 담는 배열)
    }

    int getHashCode(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c; //key의 각 문자를 아스키코드로 변환 후 다 더해줌
        }
        return hashcode;
    }

    int convertToIndex(int hashcode) {
        return hashcode % data.length; //hashcode를 data배열의 길이만큼 나눠서 인덱스값 구함
    }

    Node searchKey(LinkedList<Node> list, String key) {
        if (list == null) return null;
        for (Node node : list) {
            if (node.key.equals(key)) {
                return node;
            }
        }
        return null;
    }

    void put(String key, String value) {
        int hashcode = getHashCode(key); //해시코드 생성
        int index = convertToIndex(hashcode); //해시코드로 인덱스 생성
        System.out.println("key : " + key + ", hashcode : " + hashcode + ", index : " + index); //키, 해시코드, 인덱스 값 보여줌
        LinkedList<Node> list = data[index]; //기존 배열방의 index에 해당하는 값(리스트)을 가져와서 list변수에 넣어줌

        if (list == null) {
            list = new LinkedList<Node>(); //배열방이 비었다면 Linkedlist 생성
            data[index] = list; //해당 리스트를 배열방에 넣어줌
        }

        Node node = searchKey(list, key); //list에서 key값을 가진 노드 검색해서 가져옴
        if (node == null) {
            list.addLast(new Node(key, value)); //해당 key값을 가진 노드가 없다면 새로 만들어서 넣어줌
        } else {
            node.setValue(value); //해당 key값을 가진 노드가 있다면 기존의 노드를 대체해 주는 걸로 중복키 처리
        }
    }
    String get(String key) {
        int hashcode = getHashCode(key); //key값으로 hashcode 만들어줌
        int index = convertToIndex(hashcode); //hashcode를 인덱스로 만들어줌
        LinkedList<Node> list = data[index]; //data 배열의 index에 해당하는 리스트 가져옴
        Node node = searchKey(list, key); //linkedlist안에서 해당 키를 가지는 노드 검색해옴
        return node == null ? "Not found" : node.getValue(); //노드가 없으면 not found, 있으면 노드의 value값 return
    }

    public static void main(String[] args) {
        MyHashTable h = new MyHashTable(3);
        h.put("사과", "apple");
        h.put("바나나", "banana");
        h.put("딸기", "strawberry");
        h.put("포도", "grape");
        h.put("사과", "APPLE");

        System.out.println(h.get("사과"));
        System.out.println(h.get("바나나"));
        System.out.println(h.get("딸기"));
        System.out.println(h.get("포도"));
        System.out.println(h.get("키위")); //not found 출력

    }
}

 

   스택, 큐, 해시테이블을 구현하는 코드는 유튜브의 '엔지니어대한민국' 채널의 강의를 참고하였다. 내배캠에서 제공해준 강의에서 위의 자료구조의 개념을 먼저 익힌 후, 코드를 구현하는 영상을 보니 이해에 훨씬 도움이 되었다. 앞으로 남은 강의들도 이런식으로 공부해 나가면 될 것 같다!

   자료구조와 알고리즘 공부가 어렵긴 하나, 뭔가 배워가는게 많아서 그런지 하나씩 알아갈 수록 성취감이 큰 것 같다! 그런데 하루만 지나도 머릿속에서 기억이 절반은 사라지는 것 같다...ㅋㅋㅋ 복습을 얼마나 해야 완전히 자리잡을 지 모르겠지만 꾸준하게 헤쳐 나가야 겠다 ㅠㅡㅠ 꾸준함이 답이다! 오늘하루도 수고 많았고 내일 더 더 열심히 해보자! 화이팅!!