CS 비전공자의 IT 기업 면접 뽀개기 - (1) Data Structure - Stack

자료구조(Data structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 즉, 처리하고자 하는 데이터들이 모여 있는 형태, 혹은, 처리하고자 하는 데이터들 사이의 관계 (수직, 상하, 일방적, 상호 등)를 정의한 것, 혹은, 데이터들을 사용하기 용이하게 저장해 놓은 형태라고 볼 수 있다.

자료구조를 잘 선택하면 사용하는 메모리와 시간, 공간적 효율성을 확보할 수 있다.

Stack

위 그림과 같이 LIFO, 즉, 선입후출 구조를 갖는다. 먼저 들어온 것은 Stack의 맨 마지막에 있기 때문에, 먼저 나갈 수가 없다. 따라서 가장 마지막에 들어온 데이터가 가장 먼저 나갈 수 있게된다. 앞서 살펴보았던 array나 linkedlist를 사용하여 구현할 수 있다.

Stack의 특징으로는,

• 참조 지역성(locality)을 활용할 수 있다.
• 데이터를 탐색하기 어렵다.

언제쓰는가?

큐와 스택의 사용 예

스택/큐 홀로 사용되기보단, 다양한 알고리즘과 결합되어 사용된다. 예를 들어 DFS에서는 stack을, BFS에서는 queue가 사용된다.

현실적인 문제에서 맞닥들인다면, 큐와 스택을 사용해서 문제를 풀어야지 가 아닌, 순서를 고려하거나 우선적으로 무엇인가를 선택할 때, 즉, 어느 것을 먼저 선택할 것 인가의 경우는 대게 스택/큐를 쓴다고 보면 된다.

일반적으로,

• 재귀 알고리즘
  • 재귀적으로 함수를 호출하는 경우, 임시 데이터를 stack에 넣어줌
  • 재귀함수를 빠져나와 backtrack할 경우, stack에 넣어놨던 임시 데이터를 빼줘야 함.
• 웹 브라우저 방문기록
• 실행 취소
• 역순 문자열 만들기
• VPS
• 후위 표기법 계산

ADT

• push (-> None): 맨 위에 값 추가
• pop (-> data): 가장 최근에 넣은 맨 위의 값을 제거
• peak (-> data or 1): stack의 변형 없이 맨 위의 값을 출력
• is_empty (-> boolean): 스택이 비어있는지 확인

Python 구현

list를 상속하여 만들면 된다.

class Stack(list):
    def empty(self):
        if len(self) == 0:
            return True
        else:
            return False

    def top(self):
        if len(self) != 0:
            return self[-1]
        else:
            return -1

또한 다음과 같이 노드를 통해 singly linked list로 구현할 수 있다.

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None

class Stack:
    def __init__(self) -> None:
        self.head = None  # top node

    def is_empty(self) -> bool:
        if not self.head:
            return True
        else:
            return False

    def push(self, data) -> None:
        # 새로운 data를 push하면 이 data가 새로운 head가 되고
        # 기존에 있던 data는 stack 아래층에 쌓이게 된다.
        # 이 때, 새로운 data의 next는 stack 아래층의 data를 가르키게 된다.
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self) -> Node:
        if self.is_empty():
            return None

        ret_data = self.head.data
        self.head = self.head.next

        return ret_data

    def peek(self):
        if self.is_empty():
            return None

        return self.head.data

파이썬에서는 collections.deque로 구현되어 있다.

Reference

https://wayhome25.github.io/cs/2017/04/18/cs-20/

https://daimhada.tistory.com/105?category=820522