TIL(Today I Learn) - #2. Data Structure - Stack

chadonghwa·2019년 9월 18일
0

Stack에 대해 알아보도록 하겠습니다.

Stack이란 들어오고 나가는 방향이 하나인 Data Structure를 말합니다.

들어왔던 방향으로 나가야하기 때문에 가장 먼저 들어온 데이터가 마지막으로 나가게 됩니다.
이것을 LIFO(Last In First Out)라고 합니다.

쉽게 이해하기 위해 예를 들어보겠습니다.

  • 책이 쌓여있는 모습
  • 프링글스 감자칩

Stack의 실제 사용 예시

  • 재귀 알고리즘
    재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
    재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
    스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
    또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
  • 웹 브라우저 방문기록 (뒤로가기)
  • 실행 취소 (undo) (command+z)
  • javascript의 callStack

Stack Data structure의 methods

  • push(item)
    요소를 스택에 넣는다(삽입, 저장).
    위치는 포인터(Linked list)에 의해 / 인덱스(Array)에 의해 지정된다.
  • pop()
    요소를 스택에서 뽑아낸 후 제거한다.
    위치는 포인터(Linked list)에 의해 / 인덱스(Array)에 의해 지정된다.
  • peek()
    스택의 맨 위에 있는 항목을 제거하지 않고 반환한다.(pop은 제거하지만, peek은 제거하지 않는다.)
  • isEmpty()
    스택이 비어 있으면 true, 그렇지 않으면 false로 반환한다.

Stack Data structure의 property

  • Array를 사용한 Stack
    top(데이터 삽입/삭제하는 위치)-(index), maxSize(배열의 최대크기), stackArray(배열)
  • Linked list를 사용한 Stack
    top(데이터 삽입/삭제하는 위치)-(head node), Node(스택을 구성하는 요소)

Stack 이미지

aww-board (2).png

Array를 사용한 Stack 구현

pseudo code

Linked list를 사용한 Stack 구현

pseudo code

profile
command and obey

0개의 댓글