[자료구조] Stack

자료구조 02 / Stack

---

정의 

"쌓다" 개념을 가진 자료구조

후입선출 LIFO (Last-In First-Out) 의 원리를 가짐

예를들어 책을 쌓고 다른 곳으로 옮길때 맨위에 책부터 다시 하나씩 빼는 모습으로 볼 수 있다.

 

장점 : 구조 단순해서 구현이 쉽다.

단점 : 저장 공간 낭비가 발생 할 수 도 있다.

 

주요기능

push() : 스택에 데이터 쌓기

pop() : 스택의 가장 마지막 데이터 빼기

top() : 스택의 가장 마지막 데이터

empty() : 스택이 비어있는 지 확인하는  

 

활용

컴퓨터 내부의 프로세스 구조의 함수 동작 방식 (return)

- 함수 동작을 시작할때 돌아갈 시점(반환주소)을 스택에 쌓고 함수동작이 끝나는 데로 가장 마지막으로 쌓인 시점부터 돌아간다

 

예상하지 못한 Stack 범위를 넘게 되면 "Stack Overflow" 오류가 발생한다.

 

구현

 

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

연결리스트를 통한 구현

 - 노드의 할당 및 삭제, 포인터를 타고 들어가는 시간 낭비가 생긴다

 

동적 배열을 이용한 구현

 - HEAD와 TAIL의 사용을 신경쓰지 않으면 공간의 낭비가 발생할 수 있다.

// Swift 5
// raywenderlich.com

public struct Stack<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

  // 원소가 맨 앞에 생성되면 index이동으로 O(n)의 시간복잡도 비용발생
  public mutating func push(_ element: T) {
    array.append(element)		
  }

  public mutating func pop() -> T? {
    return array.popLast()
  }

  // Stack 내부의 값이 없는 경우대비 옵셔널 처리 
  public var top: T? {		
    return array.last	
  }
}

추가적으로 생각해볼 내용

면접 예상질문

Q: 비어있는 스택 참조 하는 경우? 

A: 스택이 비어 데이터가 없는데 데이터를 참조하는 경우 Stack Underflow 발생할 수 있음,

    스택이 수용범위까지 가득찼는데 데이터 푸시하는 경우 Stack Overflow 발생

 

Q : 스택을 활용하는 경우?

A : 하나의 프로세스가 동작할때 할당되어 함수를 참조 할경우 함수 코드가 마칠때 돌아갈 코드의 위치를 스택에 쌓아둠

      가장 마지막으로 실행된 함수가 돌아갈 리턴될 위치 필요

 

Q : X 상황에서 스택과 큐중 무엇을 사용하는 게 이득?

- 1. 웹브라우저 방문기록 (뒤로가기) -> 스택구조

- 2. 역순 문자열 만들기 -> 스택구조

- 3. 괄호 검사 (수식) -> 스택구조

- 4. 메모리의 Stack영역 -> 지역변수, 매개변수 저장, 함수

- 5. 재귀함수 무한 호출 (하노이 탑) 및 지역변수 클 경우  ->  Stack영역 Stack Overflow 

 

Q : Array와 Linked List 형태로 스택 구현할 경우 차이점

A : Array는 top에 바로 접근 가능하지만 Linked List는 마지막 데이터에 접근하기 위해서 모든 데이터 거쳐야함

Reference : raywenderlich.com github explain