Stacks and Queues

스택

• LIFO(Last-In-First-Out) 구조의 삽입과 삭제 기능으로 이루어진 연속 배열
• E.g.) 프로그램 런타임 실행 중 프로세스 함수 호출 - 스택(함수 호출 시 스택 형식으로 쌓이는 호출된 함수들)
  

import Foundation

struct FixedStack<T> {
    let size: Int
    var nodes = [T]()
    
    init(size: Int) {
        self.size = size
        // 스택 사이즈 고정
    }
    
    var isEmpty: Bool {
        return nodes.isEmpty
    }
    
    var count: Int {
        return nodes.count
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        return nodes.removeLast()
    }
    
    mutating func push(_ element: T) {
        if count < size {
            nodes.append(element)
        }
    }
    
    func peek() -> T? {
        guard !isEmpty else { return nil }
        return nodes[nodes.count-1]
    }
    
    func printStack() {
        print(nodes)
    }
}

var fixedStack = FixedStack<Int>(size: 5)
fixedStack.push(1)
fixedStack.push(2)
fixedStack.push(3)
fixedStack.push(4)
fixedStack.push(5)
fixedStack.printStack()
// [1, 2, 3, 4, 5]
fixedStack.push(5)
fixedStack.push(4)
fixedStack.push(3)
fixedStack.push(2)
fixedStack.push(1)
fixedStack.printStack()
// [1, 2, 3, 4, 5] (full size -> push not work)
fixedStack.pop()
fixedStack.push(10)
fixedStack.printStack()
// [1, 2, 3, 4, 10]

동적 할당 스택

import Foundation

struct DynamicStack<T> {
    var size: Int
    var nodes = [T]()
    
    init(size: Int) {
        self.size = size
        // 스택 사이즈 고정
    }
    
    var isEmpty: Bool {
        return nodes.isEmpty
    }
    
    var count: Int {
        return nodes.count
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        return nodes.removeLast()
    }
    
    mutating func push(_ element: T) {
        if count < size {
            size *= 2
        }
        nodes.append(element)
    }
    
    func peek() -> T? {
        guard !isEmpty else { return nil }
        return nodes[nodes.count-1]
    }
    
    func printStack() {
        print(nodes)
    }
}

var dynamicStack = DynamicStack<Int>(size: 5)
dynamicStack.push(1)
dynamicStack.push(2)
dynamicStack.push(3)
dynamicStack.push(4)
dynamicStack.push(5)
dynamicStack.printStack()
// [1, 2, 3, 4, 5]

dynamicStack.push(1)
dynamicStack.push(2)
dynamicStack.push(3)
dynamicStack.push(4)
dynamicStack.push(5)
dynamicStack.printStack()
// [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

• 스위프트는 C 언어의 배열과 달리 별도의 동적 메모리 할당이 아니더라도 append 메소드를 통해 자동으로 추가가 되기 때문에 C에서와 같이 사이즈 및 현재 배열의 원소 개수를 비교, 체크하는 것으로 만들었다.

큐

• FIFO(First-In-First-Out) 구조의 삽입과 삭제로 이루어진 연속 배열
• OS의 Job Scheduling 기법에 FIFO가 응용된다.
  

import Foundation

struct FixedQueue<T> {
    private var nodes = [T]()
    let size: Int
    
    init(size: Int) {
        self.size = size
    }
    
    var isEmpty: Bool {
        return nodes.isEmpty
    }
    
    var count: Int {
        return nodes.count
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        return nodes.removeFirst()
    }
    
    mutating func push(_ element: T) {
        guard count < size else { return }
        nodes.append(element)
    }
    
    mutating func peek() -> T? {
        guard !isEmpty else { return nil }
        return nodes[0]
    }
    
    func printQueue() {
        print(nodes)
    }
}

var fixedQueue = FixedQueue<Int>(size: 5)
fixedQueue.push(1)
fixedQueue.push(2)
fixedQueue.push(3)
fixedQueue.push(4)
fixedQueue.push(5)
fixedQueue.printQueue()
// [1, 2, 3, 4, 5]
fixedQueue.push(6)
fixedQueue.printQueue()
// [1, 2, 3, 4, 5] - 현재 큐 Full 상태
fixedQueue.pop()
fixedQueue.printQueue()
// [2, 3, 4, 5]

원형 큐

• front, rear 두 변수를 활용, 원형 큐의 앞과 끝을 감지할 수 있다.
• FixedQueue와 마찬가지로 고정된 크기 size를 설정했다.
• CircularQueue 구조체는 가득 찬 경우 곧바로 사이즈를 두 배로 늘려주는 동적 할당 원형 큐로 구현했다. 정적 크기의 원형 큐라면 정해진 사이즈 이상의 push가 들어올 경우 front 단의 원소를 덮어씌우거나 더 이상 push를 받아들이지 않는 방법으로 구현할 수 있다.

import Foundation

struct CircularQueue<T> {
    private var nodes = [T]()
    var size: Int
    var front = -1
    var rear = -1
    
    init(size: Int, defaultValue: T) {
        self.size = size
        nodes = Array(repeating: defaultValue, count: size)
    }
    
    var isEmpty: Bool {
        return front == rear
        // (1). empty case (2). full case -> full 되는 순간 곧바로 큐 사이즈 * 2배
    }
    
    var count: Int {
        return abs(front - rear)
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        front = (front + 1) % size
        return nodes[front]
    }
    
    mutating func push(_ element: T) {
        if count + 1 == size {
            let defaultValue = element
            let newNodes = Array(repeating: defaultValue, count: size)
            nodes += newNodes
            size *= 2
        }
        rear = (rear + 1) % size
        nodes[rear] = element
    }
    
    func printQueue() {
        guard !isEmpty else { return }
        var tmp = front
        while tmp != rear {
            tmp = (tmp + 1) % size
            print(nodes[tmp])
        }
    }
}

var circularQueue = CircularQueue<Int>(size: 5, defaultValue: 0)
circularQueue.push(1)
circularQueue.push(2)
circularQueue.push(3)
circularQueue.push(4)
circularQueue.push(5)
circularQueue.printQueue()
// 1, 2, 3, 4, 5
circularQueue.pop()
circularQueue.pop()
circularQueue.pop()
circularQueue.printQueue()
// 4, 5
circularQueue.push(1)
circularQueue.push(2)
circularQueue.push(3)
circularQueue.push(4)
circularQueue.push(5)
circularQueue.push(6)
circularQueue.printQueue()
// 4, 5, 1, 2, 3, 4, 5, 6