[Kotlin] 자료구조 : Stack, Queue, Deque, Array, ArrayList, LinkedList

---

import java.util.*

fun main() {
    println("Hello kotlin.....")

    // playStack()
    // playQueue()
    // playDeque()
    // playArray()
    // playArrayList()
    // playLinkedList()
}

private fun playStack() {
    /**
     * 스택 : Stack
     * LIFO(Last In First Out) : 목록의 끝에서만 접근, 접근이 제한적임.
     * 
     * [시간복잡도]
     * - 접근, 검색 O(n)    처음 index 부터 접근
     * - 추가, 삭제 O(1)    마지막 index에 추가, 삭제
     * 
     * [메소드]
     * - push()     [.]         stack의 최상단에 item을 올림.
     * - pop()      [.]         stack의 최상단에 있는 item 제거, 노출
     * - peek()     [.]         stack의 최상단에 있는 item 제거X, 노출
     * - empty()    [Boolean]   stack이 비었을 때, true 반환
     * - search()   [int]       object를 stack의 어느 위치에 있는지 찾고 위치 반환 
     *                          (최상단 : 1, 최하단 : n, object가 없으면 : -1 반환)
     * 
     * import java.util.* [추가]
     */

    val stack = Stack<Int>()
    stack.push(1)
    stack.push(2)

    println("stack.pop() (1) : ${stack.pop()}")
    println("stack.pop() (2) : ${stack.pop()}")
    /*
        stack.pop() (1) : 2
        stack.pop() (2) : 1
    */
}

private fun playQueue() {
    /**
     * 큐 : Queue
     * FIFO(Last In First Out) : 한쪽에서는 삽입, 반대쪽에서는 추출
     * [stack - LIFO] 와 반대되는 개념 [Queue - FIFO]
     * 
     * [시간복잡도]
     * - 접근, 검색 O(n)    처음 index 부터 접근
     * - 추가, 삭제 O(1)    마지막 index 추가, 처음 index 삭제
     * 
     * [메소드]
     * - add()      [Boolean]   객체 추가
     * - offer()    [Boolean]   객체 추가, 성공여부 판단
     * - remove()   [.]         객체 삭제 (가장 처음에 들어간 객체)
     *                              - 제거된 객체를 반환
     *                              - Queue가 빈 경우 Exception Throw
     * - element()  [.]         객체 반환 (가장 처음에 들어간 객체)
     *                              - Queue가 빈 경우 Exception Throw
     * - poll()     [.]         객체 제거 (가장 처음에 들어간 객체)
     *                              - 제거된 객체를 반환
     *                              - Queue가 빈 경우 Exception Throw
     * - peek()     [.]         객체 반환 (가장 처음에 들어간 객체)
     *                              - Queue가 빈 경우 Exception Throw
     */

    val queue: Queue<Int> = LinkedList()
    queue.add(1)
    queue.add(2)
    queue.add(3)
    queue.add(4)

    for (item in queue) {
        println("queue1 : $item")
        /*
            queue1 : 1
            queue1 : 2
            queue1 : 3
            queue1 : 4
        */
    }
    println("queue.offer(4) : ${queue.offer(4)}")
    println("queue.offer(9) : ${queue.offer(9)}")
    println("queue.remove() : ${queue.remove()}")
    println("queue.poll() : ${queue.poll()}")
    /*
        queue.offer(4) : true
        queue.offer(9) : true
        queue.remove() : 1
        queue.poll() : 2
    */
}

private fun playDeque() {
    /**
     * 덱 : Deque (Double Ended Queue)
     * 
     * [메소드]
     * - addFirst()     [Boolean]   Queue의 앞쪽에 객체 추가
     * - addLast()      [Boolean]   Queue의 뒤쪽에 객체 추가
     * - offerFirst()   [Boolean]   Queue의 앞쪽에 객체 추가
     *                                  - 성공 true, 실패 false
     * - offerLast()    [Boolean]   Queue의 뒤쪽에 객체 추가
     *                                  - 성공 true, 실패 false
     * - removeFirst()  [.]         객체 제거 (가장 처음에 들어간 객체)
     *                                  - 제거된 객체 반환
     *                                  - Queue가 빈 경우 Exception Throw
     * - removeLast()   [.]         객체 제거 (가장 마지막에 들어간 객체)
     *                                  - 제거된 객체 반환
     *                                  - Queue가 빈 경우 Exception Throw
     * - pollFirst()    [.]         객체 제거 (가장 처음에 들어간 객체)
     *                                  - 제거된 객체 반환
     *                                  - Queue가 빈 경우 NULL 반환
     * - pollLast()     [.]         객체 제거 (가장 마지막에 들어간 객체)
     *                                  - 제거된 객체 반환
     *                                  - Queue가 빈 경우 NULL 반환
     * - peekFirst()    [.]         객체 반환 (가장 처음에 들어간 객체)
     *                                  - Queue가 빈 경우 NULL 반환
     * - peekLast()     [.]         객체 반환 (가장 마지막에 들어간 객체)
     *                                  - Queue가 빈 경우 NULL 반환
     * - getFirst()     [.]         객체 반환 (가장 처음에 들어간 객체)
     *                                  - Queue가 빈 경우 Exception Throw
     * - getLast()      [.]         객체 반환 (가장 마지막에 들어간 객체)
     *                                  - Queue가 빈 경우 Exception Throw
     */
}

private fun playArray() {
    /**
     * 배열 : Array
     * 같은 type의 연관된 데이터를 효율적으로 관리하기 위한 자료구조
     * 
     * [시간복잡도]
     * - 접근 O(1)
     * - 검색 O(n)          index를 통해 바로 접근이 가능
     * - 추가 및 삭제 O(n)    크기가 fix되기 때문에 데이터 추가, 삭제가 어렵. -> ArrayList
     */

    var array1 : Array<Int> = arrayOf(1, 2, 3) 
    var array2 : Array<Int> = Array(3) { 0 }
    var newArray = array1.plus(6)

    for (item in array1) {
        println("array1 : $item")
        /*
            array1 : 1
            array1 : 2
            array1 : 3
         */
    }
    for (item in array2) {
        println("array2 : $item")
        /*
            array2 : 0
            array2 : 0
            array2 : 0
        */
    }
    for (item in newArray) {
        println("newArray : $item")
        /*
            newArray : 1
            newArray : 2
            newArray : 3
            newArray : 6
        */
    }
}

private fun playArrayList() {
    /**
     * ArrayList : 배열리스트
     * 
     * 크기가 자유롭다.
     * 추가, 수정, 삭제가 용이하다.
     */

    val arrayList: ArrayList<Int> = arrayListOf(1, 2, 3)

    arrayList.add(4)
    for (item in arrayList) {
        println("arrayList1 : $item")
        /*
            arrayList1 : 1
            arrayList1 : 2
            arrayList1 : 3
            arrayList1 : 4
        */
    }
    arrayList.removeAt(0)
    for (item in arrayList) {
        println("arrayList2 : $item")
        /*
            arrayList2 : 2
            arrayList2 : 3
            arrayList2 : 4
        */
    }
    arrayList.remove(2)
    for (item in arrayList) {
        println("arrayList3 : $item")
        /*
            arrayList3 : 3
            arrayList3 : 4
        */
    }
}

private fun playLinkedList() {
    /**
     * 링크드리스트 : LinkedList
     * 
     * 각 Node들이 연결되어있는 형태
     * 각 Node에는 데이터와 다음 Node의 주소(pointer)가 들어있는 형태.
     * 
     * [시간복잡도]
     * - 접근, 검색 O(m)
     * - 추가, 삭제 O(1) [처음, 마지막] , O(n) [중간]
     * 
     * 단일 링크드리스트 : Single LinkedList
     *  - 하나의 Pointer를 가짐. 다음(next) 노드랑만 연결
     * 이중 링크드리스트 : Double LinkedList
     *  - 두개의 Pointer를 가짐. 이전(prev), 다음(next) 노드와 연결
     * 원형 링크드리스트 : Circular LinkedList
     *  - 단일 링크드 리스트에서 마지막 Node가 첫번째 Node의 Pointer를 가짐.
     */

    val linkedList = LinkedList<Int>()

    linkedList.addFirst(1)
    linkedList.add(1, 4)
    linkedList.addLast(10)

    for (item in linkedList) {
        println("linkedList1 : $item")
        /*
            linkedList1 : 1
            linkedList1 : 4
            linkedList1 : 10
        */
    }

    println("linkedList.removeAt(0) : ${linkedList.removeAt(0)}")
    println("linkedList.remove() : ${linkedList.remove()}")
    println("linkedList.removeLast() : ${linkedList.removeLast()}")
    /*
        linkedList.removeAt(0) : 1
        linkedList.remove() : 4
        linkedList.removeLast() : 10
    */
}