필수 알고리즘 1 '스택'

스택의 어원은 '쌓는다'이다.
어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료 구조이다.

LIFO(Last In First Out): 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO라고 한다.
이때 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

ADT(abstract data type): 추상자료형

• 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다.
• 일종의 자료형의 설계도라고 생각하면 된다.

그렇다면 스택은 어떤 정의가 필요한 자료구조 일까?

스택의 ADT

우선 다음을 정의해야 된다.

• push
• pop
• isFull (가득 찼는지 확인)
• isEmpty (비었는지 확인)
• top
  • 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top도 있어야 된다.