Stack 구현하기

자료구조(Data Structure)를 공부하고, 복습하기 위해 앞으로 정리를 하겠습니다..!!

 

그 첫번째로는 Stack!!

FILO(First In Last Out) 혹은 LIFO(Last In First Out)을 만족하는 데이터 저장하는 방법이라고 생각하면 됩니다!

 

Stack의 구현 요소로는, 

1. 현재 stack안의 데이터 갯수

2. 현재 stack이 비었는지를 파악할 수 있게 해주는 Bool값

3. stack에 값을 추가 할 수 있는 push() 함수

4. stack에서 값을 꺼내는 pop() 함수

 

정도가 됩니다!

 

Stack 구현을 해볼까요?

struct Stack<T> {
    var stack: [T] = []
    
    var count: Int {
        return stack.count
    }
    
    var isEmpty: Bool {
        return stack.isEmpty
    }
    
    mutating func push(_ element: T) {
        stack.append(element)
    }
    
    mutating func pop() -> T? {
        return isEmpty ? nil : stack.popLast()
    }
}

 

위와 같이 Stack을 만들고, 실제 데이터를 push해보고, pop해봅시다!

var stack = Stack<Int>()
stack.push(1)
stack.push(2)

stack.pop()
stack.pop()
stack.pop()

 

첫번째 라인에서 Int 타입을 element들로 갖는 Stack을 생성해주고, 이 stack에 1을 push하게 되면,

 

stack.push(1) // stack = [1]

 

 

2를 push하면

stack.push(2) // stack = [1, 2]

 

 

stack은 FILO의 성격이 있기에, pop()을 해주게 되면, 1이 아닌 가장 마지막에 들어온 2부터 나가게 됩니다.!

 

첫번째 pop을 해주면

stack.pop() // stack = [1], 나온 값: 2

 

 

두번째 pop을 하면

stack.pop() // stack = [], 나온 값: 1

 

세번째 pop을 하게 되면

stack.pop() // stack = [], 나온 값: nil

위와 같이 우리가 만든 stack에는 데이터가 없게 되므로, nil값이 return 되고, stack은 그대로 비워져 있는 상태가 된다!

 

 

push(), pop()하는 경우 가장 마지막 element들을 대상으로 데이터의 변화가 진행되므로,

데이터 삽입과 삭제의 경우에 O(1)의 복잡도를 가지게 된다!

 

비교적 간단한 자료구조에 속하는 Stack! 앞으로 어려운 것들이 많으니 더욱 기대하시라!

 

끗!