[자료구조] #스택(Stack)

오늘은 매우 오랜만에 자료구조다. 이게 공부할건 엄청 많은데 하루에 공부량이 정해져 있어서 어쩔수 없이 알고리즘과 자료구조가 자꾸 우선순위에 밀려버린다.. 그래도 잊지말기 상기할겸 오늘 포스팅을 하기로 했다..!

 

스택(Stack)이란?

 

출처 : https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

원리는 간단하다. 우리가 젠가를 상자에 차곡차곡 쌓는다고 가정하자. 그러면 가장 첫번쨰로 쌓은 블록은 가장 아래에 향할 것이고 가장 마지막으로 쌓은 블록은 가장 위에 있을 것이며 꺼낼때도 가장 위에 있는 블록 부터 꺼내야할것이다. 그냥 상자를 뒤집어서 다 꺼내버리면..

 

그 개념이 바로 스택이다. 이것을 프로그램에 대입하면 저 블록은 특정 '데이터', 쌓는것(Push)과 꺼내는 것(Pop)은 프로그램을 '추가 또는 삭제하는 때' 라고 할수 있다. 그래서 정의를 하자면 이렇다

 

푸쉬(Push)와 팝(Pop)으로 이루어져 있는 후입선출(LIFO) 자료구조

 

컴퓨터는 호출스택이라는 것을 사용하는데 우리가 작은 예제 프로그램을 작성했다고 가정을 해보자. 그 프로그램안에는 무수한 함수와 메서드들이 존재할 텐데, 그것들이 마구잡이로 본인들이 원할 때 실행되는게 아닐 것이다. 그것에도 순서가 있는데 간단한 과정은 이렇다.

1. 함수를 싱행
2. 함수안의 속성들을 실행
3. 함수안의 속성 종료
4. 함수 종료

 

프로그램은 코드 위에서 아래방향으로 실행된다. 간단한 코드와 그림을 살펴보자

class Greeting{
	sayHi()	//1. 실행		//4. 종료
	func sayHi(){	//2. 함수호출
    	print("안녕하세요!")
    }	//3. 함수호출 종료
}

개똥퀄리티 죄송..

대강 느낌이 왔을 것이다...(?) 스택은 초반에 다루는 주제만큼 쉬운 구조이다. 다른 자료구조중엔 덱과 큐등이 있는데 그것은 다음에 포스팅을 할 예정이다.

 

 

스택이라는 존재를 가장 어필해주는 알고리즘이 아닌가 싶다. 모두 자바를 배운 사람들이라면 재귀함수가 무엇인지는 알것이다. 재귀를 쓸줄 아냐 모르냐에 따라 아마 프로그래머의 개발실력을 좌지우지 할것이다. 재귀에 모르는 사람을 위해서는 나중에 포스팅을 하겠다. 

 

위의 코드는 아주아주 간단한 예시를 든것 뿐이고 제대로 함 가보자 스택에 대해서..

struct Stack<T> {
    var stack:[T] = []

    var length:Int{
        return stack.count
    }
    var isEmpty: Bool {
        return stack.isEmpty
    }
    var bottom:T?{
        return isEmpty ? nil :  stack.first
    }
    var top:T? {
        return isEmpty ? nil :  stack.last
    }
    
    mutating func push(_ item: T) {
        stack.append(item)
    }
    
    mutating func pop() -> T? {
        return isEmpty ? nil : stack.popLast()
    }
    
    private var list = [T]()
}

var stackTable = Stack<Int>()
stackTable.push(10)     //후입
stackTable.push(30)     //선입                   //출력
print(stackTable.stack)                         //[10,30]
print(stackTable.isEmpty)                       //false
print(stackTable.top!)          //가장 위         //30
print(stackTable.bottom!)       //가장 아래        //10
print(stackTable.length)        //스택 길이        //2
stackTable.pop()        //30이 가장 후입이므로 선출
print(stackTable.stack)                         //[10]

일단 어떤 값이 들어올지 몰라 구조체는 제네릭으로 선언하였다. 10과 30 두 값이 들어왔을 때 길이와 스택 요소전체,요소 유무,가장 위의 값, 가장 아래값을 알려주는 내용이다. 이 정도는 모두 해석할 수 있으리라 믿는다..