스택(Stack)

🥪

Stack

목표

• 스택(Stack)의 기본 연산을 이해한다.

• Kotlin과 Python으로 Stack을 구현할 수 있다.

📖개념

---

한쪽 끝에서만 자료를 넣고 뺼 수 있는 LIFO(Last In First Out) 형식의 자료구조

🧮연산

---

스택(Stack)은 LIFO를 따른다.

즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

• pop(): 스택에서 가장 위에 있는 항목을 제거한다.

• push(item): item 하나를 스택의 가장 윗 부분에 추가한다.

• peek(): 스택의 가장 위에 있는 항목을 반환한다.

• isEmpyty(): 스택이 비어있을 때 true를 반환한다.

⚒️구현

---

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

• 배열과 달리 스택은 상수시간(O(1)에 i번째 항목에 접근할 수 없다.
  • 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

• 하지만, 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.

스택은 연결리스트(Linked List)로 구현할 수 있다.

연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.

kotlin Code

package com.parade621.stack_kotlin

import java.util.NoSuchElementException

class MyStack(val num: Int){

    private var top: StackNode?

    init{
        val t: StackNode = StackNode(num)
        top = t
    }

    // linked list
    private class StackNode(val data: Int) {
        var next: StackNode? = null
    }

    fun pop(): Int {
        if (top == null) throw NoSuchElementException()
        val item: Int = top!!.data
        top = top!!.next
        return item
    }

    fun push(item: Int) {
        val t: StackNode = StackNode(item)
        t.next = top
        top = t
    }

    fun peek(): Int {
        if (top == null) throw NoSuchElementException()
        return top!!.data
    }

    val isEmpty: Boolean
        get() = top == null
}

fun main(){

    var stack = MyStack(0)
    stack?.push(1)
    stack?.push(5)
println(stack?.pop())
println(stack?.pop())
println(stack?.pop())
println(stack?.isEmpty)
}

타입을 제네릭을 사용해서 구현해 보고 싶었는데, 아직 제네릭을 원활하게 사용하지 못해서 그냥 Int 타입의 클래스를 만들었다.

• 위 코드를 제네릭으로 작성한 것

  package Basic
  
  import java.util.NoSuchElementException
  
  class MyStack<T>(val num: T){
  
      private var top: StackNode<T>?
  
      init{
          val t: StackNode<T> = StackNode(num)
          top = t
      }
  
      // 링크드 리스트
      private class StackNode<T>(val data: T) {
          var next: StackNode<T>? = null
      }
  
      fun pop(): T {
          if (top == null) throw NoSuchElementException()
          val item: T = top!!.data
          top = top!!.next
          return item
      }
  
      fun push(item: T) {
          val t: StackNode<T> = StackNode<T>(item)
          t.next = top
          top = t
      }
  
      fun peek(): T {
          if (top == null) throw NoSuchElementException()
          return top!!.data
      }
  
      val isEmpty: Boolean
          get() = top == null
  }
  
  fun main(){
  
      var stack = MyStack<Int>(0)
      stack?.push(1)
      stack?.push(5)
      println(stack?.pop())
      println(stack?.pop())
      println(stack?.pop())
      println(stack?.isEmpty)
  }

python Code

파이썬에서는 그냥 List를 스택처럼 사용하는 것이 가장 편한 듯 합니다.

s = []
s.append("Hello, World!")
s.append("안녕하세요!")
print(s[-1]) # 안녕하세요!
s.pop()
print(s[-1]) # Hello, World!
if s:
    print("Stack is not Empty") # Stack is not Empty

🔡사용 사례

---

후입선출이 필요한 경우에 스택 자료구조는 유용하게 사용된다.

• 재귀 알고리즘(Recursive Algorithm)
  • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
  • 재귀 함수를 빠져나와 퇴각 검색(Backtrack)을 할 때는 스택에 넣어 두었던 임시데이터를 빼줘야한다.
  • 스택은 이러한 일련의 과정을 직관적으로 가능하게 해준다.
  • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.

• 탐색 알고리즘에서 깊이 우선 탐색(DFS) 알고리즘 구현에 사용.

• 웹 브라우저의 방문기록(뒤로가기)

• 실행 취소(Undo)

• 역순 문자열 만들기

• 수식의 괄로 검사(연산자 우선순위 표현을 위한 괄호 검사)
  • ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
  • 괄호 짝 맞추기

• 후위 표기법 계산(Postfix)

Uploaded by N2T