[자료구조] 스택

바로 이전에 공부한  Queue가 FIFO(First In First Out)의 선입선출 방식이라면, 

 

스택은 LIFO(Last In First Out)의 후입선출 방식이다.

 

스택을 떠올리면 무언가를 쌓는 이미지를 보통 연상하게 되는데 , 요소를 순서대로 밀어넣고(Push) 빼는(Pop) 동작을 수행할 수 있다.

 

 

Push

Push는 아래 그림과 같이 하나 하나 요소를 밀어넣는다. 

1 뒤에 2를 push한 후 다음 push연산이 발생하는 위치는 2의 뒤가 되겠다. 

이렇게 항상 마지막 요소에서 연산이 일어나는것이 Stack의 특징이다.

 

 

그림1 push

 

 

Pop

그림으로 본다면 간단하지 그지없다.

위에서 Push가 하나하나 요소를 밀어넣었다면 이번에는 반대로 하나씩 끄집어 내는 연산을 하는것이다.

push와 같이 요소를 꺼내는것 역시 마지막 요소의 위치에서 수행하게되는데, 4->3->2 순서로 요소를 꺼내게 된다.

그림 2 pop

 

 

 

구현

방법은 보통의 배열을 사용하는것과 연결리스트를 사용 방법이 있다.

두 방법의 차이점은 배열/연결리스트의 장단점과 같다.

 

양방향 연결리스트로 구현을 해봤다.

class Node {
    var nextAddress: Node?
    var prevAddress: Node?
    var data: Int?
    
    init(_ data: Int) {
        self.data = data
    }
}

struct Stack {
    
    private var top: Node?
    
    mutating func push(_ data: Int) {
        let newNode = Node(data)
        if let top = top {
            top.nextAddress = newNode
            newNode.prevAddress = top
        }
        top = newNode
    }
    
    mutating func pop() -> Node? {
        guard isEmpty() == false else {
            print("Stack is Empty")
            return nil
        }
        let item = top
        top!.prevAddress?.nextAddress = nil
        top = top!.prevAddress
        return item
    }
    
    func isEmpty() -> Bool {
        return top == nil ? true : false
    }
    
    func printDatas() {
        guard isEmpty() == false else {
            print("Stack is Empty")
            return
        }
        print("\n\n")
        var item: Node? = top
        while item != nil {
            print(item?.data)
            item = item?.prevAddress
        }
    }
}

top은 항상 마지막 요소를 가리킨다.  가장 처음에는 nil상태이지만, 첫 요소가 들어 오면서 값이 할당 된다.

 

1을 넣는다면 top은 1을 Data로 가진 Node가 된다. 다음에 2를 push하면 역시나 top은 2를 Data로 가진 Node가 된다.

항상 top(Node)에 newNode가 할당 되는 모습은 앞서 말한 것처럼 마지막 노드와의 연산만 하면 되는 Stack의 특징을 보여준다.

 

pop메서드는 맨뒤의 요소에서 바로 앞 요소에게 너의 뒤는 이제 없어 라고 말한다.

top.prevAddress.nextAddress = nil 이 바로 그것이다. 이것으로 스택의 마지막 요소였던 Node가 사라지게 된다.

 

물론 nextAddress를 nil로 변경해주기 전에 임시변수로 미리 값을 빼놔야 return으로 값을 돌려줄 수 있다.