[자료구조] 스택과 큐

Stack

Stack(스택) 자료구조는 이름 그대로 쌓아올리다와 같은 의미이다. 예를 들어, 책상위에 쌓인 책과 비슷한 구조라고 할 수 있다. 밑에서 책을 차곡차곡 올리고 뺄때는 위에서부터 빼낸다. 이러한 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 부른다. 프로그래밍에서 함수호출, 수식계산에 대한 작업을 스택으로 처리한다.
스택은 배열과 연결리스트를 통해 구현해볼 수 있다.

Array로 Stack 구현하기

Array를 이용한 방법은 간단하게 구현할 수 있지만 크기가 고정되어 있다는 단점이 있다.

// 코틀린
class Stack<T>(private val size: Int) {
    private val arr = Array<Any?>(size) { null }
    private var top = -1

    fun push(item: T) {
        if (top == size - 1) throw StackOverflowError()
        arr[++top] = item
    }

    fun pop(): T? =
        if (isEmpty()) null
        else arr[top--] as T

    fun peek(): T? =
        if (isEmpty()) null
        else arr[top] as T

    fun isEmpty(): Boolean = top == -1
}

LinkedList로 Stack 구현하기

연결리스트로 스택을 구현하면 동적으로 크기 조절 가능하다는 장점이 있지만 연산과 구현이 복잡하다는 단점이 있다.

class Stack<T> {
    class Node<T>(val value: T) {
        var next: Node<T>? = null
    }
    private var head: Node<T>? = null

    var size = 0
    fun push(item: T) {
        val node = Node(item)
        node.next = head
        head = node
        size++
    }

    fun pop(): T? {
        val node = head?.value
        head = head?.next
        size--;
        return node
    }
    fun peek(): T? = head?.value
    fun isEmpty(): Boolean = head == null
}

Queue

Queue(큐)는 줄 서서 기다리다라는 뜻을 가진다. 놀이기구를 타기위해서 줄서서 기다리는 것, 롤을하기 위해 큐 잡히기를 기다린다고 할때의 큐도 같은 의미이다. 큐는 선입선출(FIFO, First-In-First-Out)의 구조를 가진다.

Array로 Queue 구현하기

Array로 구현한 스택과 마찬가지로 구현이 쉽지만 크기가 고정되어 있다는 단점이 있다 뿐만아니라 dequeue 이후 앞에 남는 공간이 낭비된다는 단점이 존재한다.

class Queue<T>(private val capacity: Int) {
    val arr = Array<Any?>(capacity) { null }
    var head = 0
    var rear = -1

    fun enqueue(item: T) {
        if (rear == capacity - 1) throw StackOverflowError()
        arr[++rear] = item
    }

    fun dequeue(): T? =
        if (isEmpty()) null
        else arr[head++] as T

    fun peek(): T? =
        if (isEmpty()) null
        else arr[head] as T

    fun isEmpty(): Boolean = rear < head

    fun size(): Int = (rear + 1) - head
}

LinkedList로 Queue 구현하기

연결리스트 기반 큐는 구현 및 연산은 배열기반 큐에 비해 복잡하지만 크기가 고정되어 있지 않다는 장점이 있다.

class Queue<T> {
    class Node<T>(val value: T) {
        var next: Node<T>? = null
    }
    var head: Node<T>? = null
    var rear: Node<T>? = null
    var size = 0

    fun enqueue(item: T) {
        val node = Node(item)
        if (isEmpty()) {
            head = node
            rear = node
        } else {
            rear?.next = node
            rear = node
        }
        size++
    }

    fun dequeue(): T? {
        if (isEmpty()) return null
        val node = head?.value
        head = head?.next
        if (head == null) rear = null
        size--
        return node
    }

    fun peek(): T? = head?.value

    fun isEmpty(): Boolean = size == 0
}

원형큐

원형큐는 배열기반 큐에서 dequeue 이후 낭비되는 공간을 재사용하여 효율성을 높였다. 그럼에도 초기설정한 capacity 만큼의 데이터만 가질 수 있다는 단점이 있다.

모듈려 연산을 통해 배열의 마지막에 다다르면 다시 배열의 첫번째로 돌아가 데이터를 삽입할 수 있도록 만들었다. 모든 요소를 원처럼 순회하며 사용한다고 하여 원형큐라고 부른다.

class Queue<T>(private val capacity: Int) {
    val arr = Array<Any?>(capacity) { null }
    var head = 0
    var rear = -1
    var size = 0

    // 들어갈 자리 -> (rear + 1) % capacity
    fun enqueue(item: T) {
        if (isFull()) throw StackOverflowError()
        rear = (rear + 1) % capacity
        arr[rear] = item
        size++
    }

    fun dequeue(): T? {
        if (isEmpty()) return null
        val node = arr[head] as T
        arr[head] = null
        head = (head + 1) % capacity
        size--
        return node
    }

    fun peek(): T? =
        if (isEmpty()) null
        else arr[head] as T

    fun isEmpty(): Boolean = size == 0
    fun isFull (): Boolean = size == capacity
}

Deque

Deque(Double ended queue)는 양 끝에서 삽입과 삭제가 가능한 자료구조이다. 큐와 스택의 특성을 모두 가지고 있다.

class Deque<T> {
    class Node<T>(val value: T) {
        var before: Node<T>? = null
        var next: Node<T>? = null
    }
    var head: Node<T>? = null
    var rear: Node<T>? = null
    var size = 0

    fun addFirst(item: T) {
        val node = Node(item)
        if (isEmpty()) {
            head = node
            rear = node
        } else {
            head?.before = node
            node.next = head
            head = node
        }
        size++
    }

    fun addLast(item: T) {
        val node = Node(item)
        if (isEmpty()) {
            head = node
            rear = node
        } else {
            rear?.next = node
            node.before = rear
            rear = node
        }
        size++
    }

    fun removeFirst(): T? {
        if (isEmpty()) return null
        val nowValue = head?.value
        if (head == rear) {
            head = null
            rear = null
        } else {
            head = head?.next
            head?.before = null
        }
        size--
        return nowValue
    }

    fun removeLast(): T? {
        if (isEmpty()) return null
        val nowValue = rear?.value
        if (head == rear) {
            head = null
            rear = null
        } else {
            rear = rear?.before
            rear?.next = null
        }
        size--
        return nowValue
    }

    fun peekFirst(): T? =
        if (isEmpty())  null
        else head?.value

    fun peekLast(): T? =
        if (isEmpty()) null
        else rear?.value

    fun isEmpty(): Boolean = size == 0
}