DataStructure - 스택(Stack)이란?

본 글은 『얄코의 가장 쉬운 자료구조와 알고리즘』을 참고하여 개인 학습 목적으로 이해한 내용을 정리한 것입니다.

스택은 LIFO(Last In, First Out) 구조를 가지고 있어, 마지막에 들어간 요소가 먼저 나오게됨.

• push: 요소 추가 O(1)
• pop: 요소를 하나 꺼내는 것 O(1)
• peek: 맨 위 요소를 확인 O(1)

스택은 배열, 연결 리스트를 통해 구현 가능함.

배열을 통한 구현

class ArrayStack{
    private var stack: [Int]
    private var top: Int
    
    var size: Int {
        return top + 1
    }
    
    init() {
        stack = []
        top = -1
    }
    
    public func push(item: Int){
        top += 1
        stack.append(item)
    }
    
    public func pop() -> Int{
        let item = stack[top]
        stack.remove(at: top)
        top -= 1
        
        return item
    }
    
    public func peek() -> Int{
        let item = stack[top]
        
        return item
    }
}

var stack: ArrayStack = ArrayStack()

stack.push(item: 1)
stack.push(item: 2)
stack.push(item: 3)
stack.push(item: 4)

print("size : \(stack.size)")
print("pop : \(stack.pop())")
print("peek: \(stack.peek())")

결과

size : 4
pop : 4
peek: 3

연결 리스트를 통한 구현

class Node{
    var data: Int
    var next: Node?
    
    init(data: Int) {
        self.data = data
    }
}

class LinkedStack{
    private var head: Node?
    var size: Int = 0
    
    var isEmpty: Bool{
        guard let head = head  else { return true }
        return false
    }
    
    func push(data: Int){
        let newNode = Node(data: data)
        newNode.next = head
        head = newNode
        size += 1
    }
    
    func pop() -> Int{
        guard let data = head?.data else { return 0 }
        
        head = head?.next
        size -= 1
        return data
    }
    
    func peek() -> Int{
        guard let data = head?.data else { return 0 }
        return data
    }
}

var stack = LinkedStack()

print("isEmpty : \(stack.isEmpty)")

stack.push(data: 1)
stack.push(data: 2)
stack.push(data: 3)

print("size : \(stack.size)")
print("pop : \(stack.pop())")
print("peek : \(stack.peek())")

print("isEmpty : \(stack.isEmpty)")

결과

isEmpty : true
size : 3
pop : 3
peek : 2
isEmpty : false