[Swift:자료구조] Stack 와 struct

Newon·2022년 7월 5일

스위프트 자료구조

목록 보기

1/3

들어가기 전에 !!
나는 stack 이 어떤 것인지 알고, Swift 로 어떻게 쓰는지만 알고 싶다.

: 그냥 배열 쓰세용 :)

var stack = [T]() // T 에는 원하는 자료형 - Int, String ...
stack.append()  // push
stack.popLast   // pop
stack.isEmpty   // isEmpty
stack.last      // peek

Stack 정의

Stack 자료구조는 자료를 쌓듯이 저장하고, 사용할때도 가장 뒤에 있는 자료 먼저 꺼내서 사용하는 형태를 지칭합니다.

좀 더 편하게 말하자면, 프링글스 같은 자료구조 입니다.
넣을 때는 아래에서부터 차곡차곡 과자를 쌓았겠지만,
먹을 때는 위에서부터 차근차근 먹게 되는 구조.

Stack 입니다. ~~쏟아서 먹지만 않는다면~~

이때 과자(자료)를 넣는 행위를 push, 과자를 꺼내는 행위를 pop 이라고 합니다.

이러한 자료구조의 장점은 사용하고자 하는 용도가 명백할 때,
즉 자료를 차곡차곡 쌓아서 위에서 부터 쓰겠다. 를 지킨다면 언제나 시간복잡도를 O(1) 을 지킬 수 있기 때문에 굉장히 빠른 자료구조가 됩니다.

왜냐구요? 항상 맨 뒤에다가 넣으면 되고, 맨 뒤에 있는 것만 빼서 쓰면 되거든요 !!

단, 이때 이미 쌓여있는 자료 중 어떤 것이 몇번째에 있지 라든가,
"뒤에 있는 것만 활용하겠다" 라는 취지를 어기게 되면 시간복잡도는 단숨에 확 늘어나게 됩니다.

왜냐구요? 프링글스를 뒤적뒤적 하면서 정확히 밑에서부터 42번째 있는 프링글스를 찾아가며 먹고 싶진 않잖아요 !!

Stack 의 메소드들

push : 자료를 넣는 메소드에요.
pop : 자료를 꺼내는 메소드에요.
peek : 가장 뒷단, 혹은 상단에 있는 자료를 확인하는 메소드에요.
isEmpty: 스택이 비어있는지 확인할 메소드에요.

Stack - Swift

struct Stack<T> {
	var storage = [T]()
    init(_ elements: [T]) {
    	storage = elements
    }
    
    mutating func push(_ element: T) {
    	storage.append(element)
    }
    mutating func pop() -> T? {
    	storage.popLast()
    }
    
    func peek() -> T? {
    	storage.last
    }
    var isEmpty : Bool {
    	storage.isEmpty
    }
}

var stack = Stack<Int>([1,2,3,4,5])

앞으로 자료구조는 모두 struct 를 활용하여 구조체 형태로 만들게 될 것 입니다. 사실 Stack 은 가장 상단에서 언급하였듯, 배열을 활용해서 사용해도 되긴 하지만 struct 활용이 처음인만큼 어떤 내용들이 있는지 살펴보겠습니다.

struct : 구조체를 정의하는 문법입니다. 해당 문법을 통해 사용자는 복잡한 형태를 하나의 자료형처럼 사용할 수 있게 됩니다. 이때 struct 는 값 타입 으로, 새로 생성될 때 마다 새로운 객체가 인스턴스 됩니다.

struct Coordinate<Int> {
   var y: Int
   var x: Int
}

var a = A<Coordinate>(y: 0, x: 0)
var b = a
b.y = 1; b.x = 1
print(a)
print(b)

// 출력 :
// Coordinate(y: 0, x : 0)
// Coordinate(y: 1, x : 1)
// 즉, 값 타입은 생성될 때 마다 새롭게 메모리에 적재되기에 (인스턴스 되기에)
// 새롭게 생성된 두 값 타입은 서로에게 영향을 미치지 않으며
// 구조체 struct 는 언제나 값 타입이다.

Stack<T>: 이름인 Stack 과 자료형을 지칭하는 T 입니다. 이때 T 는 제네릭 타입이라고 지칭되며, 어떠한 자료형이든 입력을 받아주겠다 라는 의미로 사용됩니다. 한번 입력되고 나면 해당 함수 내에서는 처음에 입력된 자료형으로만 통일되어 사용할 수 있습니다. 제네릭 타입에 대해서 더 궁금하면 여기를 참고해보세요.

var storage = [T](), init(...) { ... } : struct 를 통해 호출할 변수, 프로퍼티와 struct 를 처음 생성할 때 지시할 내용을 init 함수를 통해 지정할 수 있습니다.
여기서는 제네릭 타입 T 를 통해 프로퍼티인 배열 storage 를 생성하고, init 함수에서는 T 타입의 배열을 storage 에 넣는 것을 확인할 수 있습니다.

mutating func ... () :
struct 는 -좀 더 정확히는 값 타입의 프로퍼티들은-
기본적으로 내부의 값을 임의로 바꿀 수 없게 되어있습니다. 따라서 일반적인 func 함수를 호출해서 내부의 프로퍼티를 변경하려고 하면 "할 수 없어 !" 라고 컴파일러가 호되게 야단칩니다. 그래서 mutating 키워드를 활용하여 아니? 나 이거 바꿀건데 라고 컴파일러에게 요청할 수 있게됩니다.
여기서는 mutating func pop, mutating func push 를 통해 내부의 프로퍼티인 var storage 의 값을 원하는대로 바꾸고 있네요.

func peek() ... : 상단의 mutating func 와 달리 mutating 이 없는 peek 는 이름 그대로, 가장 상단의 값을 확인만 할 뿐이니 mutating 이 필요가 없는 모습을 확인할 수 있습니다.

var isEmpty : Bool { } : 연산 프로퍼티라고 불리는 변수입니다. 특징은 특정 값을 저장하지 않고, 다른 값을 읽어들여서 확인하거나, 수정하는 형태로 사용되는 프로퍼티입니다. 읽어들이는 행위를 GET, 특정 데이터를 수정하는 행위를 SET 이라고 합니다.
여기서는 GET 의 형태로만 사용되어, storage 가 비어있는지만 확인하고 있네요.

그래서 Stack 은 어떻게 쓰면 되는건데

정말 복잡했던 struct 설명이 애석하게도, 자세히 살펴보면 결국 Swift 의 기본 제공 Collection 인 배열의 메소드만 활용하고 있는 것을 확인할 수 있어요. 따라서 각각의 내용들은 이렇게 바꿔서 사용하는게 ~~정신건강~~ 편리할 것 같습니다.

var stack = [T]() 
: 원하는 자료형으로 stack 을 선언, 
struct Stack<T>{
	var storage = [T]()
    init (_elements: [T]) {
    	storage = elements
    }
    
    ...
}
를 stack = [T]() 로 한번에 정리


stack.append()
: mutating func push(_ element: T) { 
	storage.append(element)
} 를 push 를 통해 정리


stack.popLast
: mutating func pop() -> T? {
	storage.popLast
} 를 통해 pop 을 정리


stack.last
:func peek() -> T? {
    storage.last
} 를 통해 last 를 정리


stack.isEmpty
: var isEmpty : Bool {
    storage.isEmpty
  } 를 통해 isEmpty 를 정리

요약은 상단처럼 볼 수 있습니다.

var stack = [T]() // T 에는 원하는 자료형 - Int, String ...
stack.append()  // push
stack.popLast   // pop
stack.isEmpty   // isEmpty
stack.last      // peek

그래서 Stack 이 알고리즘 푸는데 어디에 쓰여요

데이터가 언제나 순서대로 온다는 점을 착안해서 이런 문제들이 출제되고 있어요.
백준 - 좋은 단어
백준 - 문자열 폭발
프로그래머스 - 크레인 인형뽑기 게임

관통하는 주제로는 "순서대로 오는 무언가를, 특정 조건에 따라 구분할 수 있는가?" 가 될 것 같네요 !!

한편 Stack 은 Stack 그 자체로 쓰이기 보다는 CS 관점에서 볼 때 재귀함수와 DFS 의 기본 구조라서, 이를 활용한 문제들이 더 많이 나오게 됩니다.

~~ㅎㅎ.. 코틀린버전으로 쓴 게 있는데 확인해주면 ㅈ..ㅈ..좋아합니다! 언어 상관없이 이해되게 썻다고 하네요!~~ 문과생이 적어보는 백트래킹 재귀와 DFS 를 곁들인

그럼 빠이네라네 ~

참고

Data Structures & Algorithms in Swift - fourth Edition
Swift Language Guide 5.7
부스트코스 - iOS 프로그래밍을 위한 스위프트 기초

Newon

나만 고양이 없어

다음 포스트