Skip to content

Latest commit

 

History

History
122 lines (88 loc) · 3.71 KB

200806.md

File metadata and controls

122 lines (88 loc) · 3.71 KB
Raw

2020/08/06 2개의 Stack으로 Quene의 구현 - Kotlin

예전에 손코딩 관련해서 줏어들은적이 있었는데 까먹고 있다가 요즘 급 생각나서 코틀린으로 구현해 보았음.

기초

Stack은 LIFO 후입선출의 자료구조로서 마지막으로 삽입한 요소를 제일 먼저 꺼내는 구조이다. 가장 최근에 삽입된 데이터를 top이라고 하며 top에서만 삽입, 삭제, 읽기 등 을 할 수 있다. 일반적인 undo/redo또는 웹 브라우저의 뒤로/앞으로 기능을 생각하면 편하다. Stack 에서 만약 1, 2, 3이 차례로 push()되었다면 pop()했을 때, 3을 꺼낸다.

Queue는 FIFO 선입선출 자료구조로서 가장 먼저 삽입된 요소를 먼저 꺼내는 구조이다. 프린터의 인쇄 대기 목록, 혹은 버퍼등을 생각 하면 편하다. Quene에 1, 2, 3이 차레로 enQuene되었다면 deQuene하였을 때 1을 꺼낸다.

1. Stack의 구현

Stack인터페이스를 만들고 구현 클래스를 심플하게 만듬

interface Stack<T> {
    fun isEmpty(): Boolean
    fun push(t: T)
    fun pop():T?
    fun peek():T?
}

class MutableStack<T>: Stack<T> {
    private val list = mutableListOf<T>()

    override fun isEmpty(): Boolean = list.isEmpty()

    override fun push(t: T) {
        list.add(t)
    }

    override fun pop(): T? {
        if (isEmpty()) return null
        return list.removeAt(list.size-1)
    }

    override fun peek(): T? {
        return list.lastOrNull()
    }

    override fun toString(): String {
        return list.toString()
    }
}

2. Stack 2개의 인스턴스를 갖는 Quene의 구현

위 (1)번에서 만든 Stack 2개를 갖는 Quene를 인터페이스로 만들고 구현한다.

interface StackedQueue<T> {
    fun isEmpty(): Boolean
    fun enQuene(t: T)
    fun deQueue(): T?
}

class MutableStackQueue<T>: StackedQueue<T> {
    val head: Stack<T> = MutableStack()
    val tail: Stack<T> = MutableStack()
    
    override fun isEmpty(): Boolean = head.isEmpty() && tail.isEmpty()
    
    override fun enQuene(t: T) {
        head.push(t)
    }
    
    override fun deQueue(): T? {
        if (tail.isEmpty()) {
            while (!head.isEmpty()) {
                tail.push(head.pop()!!)
            }
        }
        return tail.pop()
    }
    
    override fun toString(): String {
        return "${head} , ${tail}"
    }
}

일단 2개의 Stack의 목적을 나눈다. 첫번째 스택은 삽입되는 요소들을 저장 한다. 두번째 스택은 삽입되었던 요소들이 deQueue()되었을 때 첫번째 스택에 남아있는 요소를 그대로 모두 가져온다. 만약 이 Quene가 처음만들어져서 두번째 스택에 아무런 요소가 존재 하지 않는다면 위 작업을 두번째 스택이 완전히 빌 때까지 수행하게 될 것 이다.

만약 두번째스택에 요소가 존재 한다면 그대로 두번째 스택에서 요소를 pop()한다. 첫번째 스택에 입력한 순서 그대로 두번째 스택에 저장되기 때문에 순서가 보장되므로 Queue처럼 먼저들어간 요소가 다음에 deQueue()된다.

3. 테스트 및 결과

정상적으로 동작 하는지 테스트를 해 본다.

val sq: StackedQueue<Int> = MutableStackQueue()
    
sq.enQuene(1)
sq.enQuene(2)
sq.enQuene(3)
    
println(sq)
println("deQuene : ${sq.deQueue()}")
println(sq)
    
sq.enQuene(4)
sq.enQuene(5)
    
println(sq)
println("deQuene : ${sq.deQueue()}")
println(sq)

결과는 아래와 같다.

[1, 2, 3] , []
deQuene : 1
[] , [3, 2]
[4, 5] , [3, 2]
deQuene : 2
[4, 5] , [3]

deQuene()할 때 마다 이전에 입력했던 순서대로 요소를 꺼내고 있음을 확인 할 수 있다.