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

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 이미지

Array를 사용한 Stack 구현

pseudo code

push(item)
- index를 1 증가시킨다.
- array[index]에 값을 할당한다.

pop()
- 만약 비어있으면(index가 -1(초깃값)이라면), 아무것도 하지 않는다.
- index 위치에 있는 값을 반환한다.
- index 위치에 있는 값을 삭제한다. 
- index를 1 감소시킨다.

peek()
- 만약 비어있으면(index가 -1(초깃값)이라면), 찾지 못했다는 메세지를 반환한다.
- index 위치에 있는 값을 반환한다.

isEmpty()
- index가 -1이면 true, 아니면 false

Linked list를 사용한 Stack 구현

pseudo code

push(item)
- node객체를 하나 만든다.(생성자 함수를 이용)
- 새로 만든 node객체의 포인터가 가장 위(head) node를 가르킨다.
- 새로 만든 node객체가 head node가 된다.

pop()
- 만약 비어있으면, 아무것도 하지 않는다.
- head를 임시 변수에 저장한다.
- head에 head 포인터가 가리키고 있던 것을 저장한다.
- 임시 변수를 삭제한다.

peek()
- 만약 비어있으면, 찾지 못했다는 메세지를 반환한다.
- head node의 data를 반환한다.

isEmpty()
- top이 null이면 true, 아니면 false