225 큐를 이용한 스택, 232 스택을 이용한 큐

IKNOW·2023년 12월 10일

Leet Code algorithm coding test queue stack

coding test

목록 보기

4/6

225 큐를 이용한 스택 구현
https://leetcode.com/problems/implement-stack-using-queues/description/

class MyStack() {
    var queue = MyQueue()

    fun push(x: Int) {
        this.queue.enqueue(x)
    }

    fun pop(): Int? {
        val returnItem = this.queue.rear?.item
        var current = this.queue.head
        val newQueue = MyQueue()
        while(current != this.queue.rear) {
            this.queue.dequeue()?.let { newQueue.enqueue(it) }
            current = current?.next
        }
        this.queue = newQueue
        return returnItem
    }

    fun top(): Int? {
        return this.queue.rear!!.item
    }

    fun empty(): Boolean {
        if (this.queue.head == null) {
            return true
        }
        return false
    }
}

class Node(val item: Int, var next: Node? = null)

class MyQueue {
    var head: Node? = null
    var rear: Node? = null

    fun enqueue(item: Int) {
        val node = Node(item, null)
        if(head == null) {
            this.head = node
            this.rear = node
        } else {
            this.rear?.next = node
            this.rear = node
        }
    }

    fun dequeue(): Int? {
        val item = this.head?.item
        this.head = this.head?.next
        return item
    }
}

232 스택을 이용한 큐
https://leetcode.com/problems/implement-queue-using-stacks/description/

class MyQueue() {

    val stack:MyStack = MyStack()

    fun push(x: Int) {
        this.stack.push(x)    
    }

    fun pop(): Int? {
        val tempStack = MyStack()
        var bottomItem:Int? = null

        while(!this.stack.empty()) {
            if(this.stack.top!!.prev==null) {
                bottomItem = this.stack.pop()
                break
            }
            tempStack.push(this.stack.pop()!!)
        }
        while(!tempStack.empty()) {
            this.stack.push(tempStack.pop()!!)
        }
        return bottomItem

    }

    fun peek(): Int? {
        var current:MyNode? = this.stack.top
        while(current?.prev!=null) {
            current = current.prev
        }
        return current?.item
    }

    fun empty(): Boolean {
        return stack.empty()
    }

}

class MyNode(val item:Int, var prev: MyNode?)
class MyStack() {
    var top: MyNode? = null

    fun push(item: Int) {
        val newNode = MyNode(item, this.top)
        this.top = newNode    
    }
    fun peek():Int? {
        return this.top?.item
    }
    fun pop():Int? {
        val oldTop = this.top
        this.top = oldTop?.prev
        return oldTop?.item
    }
    fun empty():Boolean {
        if(this.top==null) {
            return true
        }
        return false
    }
 }

각각 pop()을 할때 싱글 링크드 리스트를 따라 끝까지 한번 순회 해야하기 때문에 O(n)의 시간복잡도가 예상된다.

기본적으로 스택과 큐를 싱글 링크드 리스트로 구현한 이후 각각 큐와 스택을 구현하였다.
두 문제 모두 원소가 1개 있을 경우 pop을 했을 때, empty가 변하지 않는 문제가 발생 하였었다.
처음부터 바운더리 컨디션을 생각하면서 풀어야 할지, 기본적으로 풀고나서 바운더리 관련 에러가 발생하는 걸 확인하고, 수정해야 하는지 고민이다.

또 직접 스택과 큐를 구현하여 풀었는데, 다른 사람들 풀이를 보니, java.util에 있는 Stack과 Queue를 사용하는 것을 확인했는데
내가 생각한 각 방법에서의 장단점은 다음과 같다.

직접 구현:

장점