ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [자료구조] Stack (스택)
      Mhwan's Study/Data Structure 2021. 1. 5. 22:46

      평소 블로그를 포트폴리오용으로 사용했으나, 오늘부터 개인적인 공부할 내용을 정리해두는 용도로 사용합니다.

      일단 알고리즘 문제보단 CS관련으로 올리려 합니다. 알고리즘도 이와 연관된 것들만..

      첫번째는 스택으로 시작하려합니다.

       

      # Stack

      스택은 Last In First Out (LIFO) 방식의 자료구조로, 주로 함수의 호출 콜스택 등에 사용됩니다.

      1. 배열을 통한 구현

      top이라는 변수를 통해 push할 곳과, pop할 곳을 가르켜야한다. (top의 초기 위치는 -1)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      public Stack {
          int MAX_SIZE;
          int[] stack;
      int top = -1;
          public Stack(){
              MAX_SIZE = 50;
              stack = new int[MAX_SIZE];
          }
          public void push(int v) {
              if(isFull())
                      return;
              stack[++top] = v;
          }
       
          public int pop() {
              if(isEmpty())
                      return null;
              int v = stack[top--];
              return v;
          }
       
          public boolean isFull(){
                  return top+1 == MAX_SIZE ? true : false;
          }
          public boolean isEmpty(){
              return top == -1 ? true : false;
          }
      }
      		 cs

      -> 하지만 이 방법은 MAX_SIZE가 정해져있다, 어떻게 하면 크기 제한이 없는 스택을 만들것인가?

      2. 스택이 가득 찼을때, 스택 배열의 크기를 2배씩 키워주면 된다. (Java의 경우 ArrayCopy를 이용하면 된다.)

      3. 연결리스트를 이용한 구현

      코틀린 연습을 위해 코틀린으로 구현한 코드입니다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      class Node(val value: Int, var next: Node? = null) {
      }
      class Stack(val MAX_SIZE:Int = 10, var head: Node? = null) {
          private var size :Int = 0
       
          fun isEmpty() = size === 0
          fun isFull() = size === MAX_SIZE
          fun getSize() = size
       
          fun push(v:Int){
              if (!isFull()) {
                  var newNode: Node = Node(v)
                  newNode.next = head
                  head = newNode
                  size++
              }
          }
       
          fun pop():Int? {
              if (isEmpty() || head == null) {
                  return null
              } else {
                  var remove:Node? = head
                  head = remove?.next
                  size--
                  return remove?.value
              }
          }
       
          fun printStack(){
              print("Stack : [ ")
              var node:Node? = head;
              while (node != null) {
                  print("${node.value} ")
                  node = node.next
              }
              println("]")
          }
      }
      		 cs

       

      # 스택을 이용한 알고리즘

      1. 중위 표기법을 후위 표기법 변환, 후위 표기법 계산

      https://mhwan.tistory.com/54

      2. 괄호 유효성 체크

      https://mhwan.tistory.com/55

      3. DFS

      4. 스택을 이용해 큐 구현, 큐를 이용해 스택 구현

      https://mhwan.tistory.com/56

       

       

       

       

      참고 : gyoogle.dev/blog/computer-science/data-structure/Stack%20&%20Queue.html

      'Mhwan's Study > Data Structure' 카테고리의 다른 글

      [자료구조] Queue(큐)  (0) 2021.01.06

      관련글 관련글 더보기

      댓글

    Designed by Mhwan.

    티스토리툴바