[3주차]6장 스택

6장 스택

스택의 개념 

• 먼저 입력한 데이터를 제일 나중에 꺼낼수 있는 자료구조
• 맨 나중에 입력한 데이터를 제일 먼저 꺼낼 수 있는 자료구조
• 스택에 삽입하는 연산을 Push이라고 함
• 스택에서 꺼내는 연산을 Pop이라고 함

스택의 정의

ADT(Abstract data type) 추상 자료형이다. 

이때, 추상 자료형은 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다. 

즉, 구현되지 않은 설계만 된 자료형이라고 생각하면 된다. 

 

스택을 ADT형태로 정의해보면 다음과 같다. 

스택의 요소는 다음과 같다. 

• 푸시 Push(반환타입 - 없음)
• 팝 Pop (반환타입 - 아이템의 반환타입)
• 가득 찼는지 확인 isFull (반환타입 - boolean 타입)
• 비었는지 확인 isEmpty (반환타입 - boolean 타입)
• 최근에 삽입한 데이터의 위치를 저장할 변수인 탑 Top (반환타입 - int 타입)
  • 통상적으로 Top은 -1로 초기화 한다
  • Top이 0이 되면 값이 하나 있다는 의미이다. 
• 스택의 자료를 관리하는 배열 (아이템 타입 data[maxsize])

스택의 세부 동작

이번 포스팅에서 이 부분이 제일 중요하다. 

파이썬과 같은 언어로 스택을 구현하면 위에있는 모든 추상자료형의 요소들을 구현하지 않아도 스택을 쉽게 구현할 수 있다. 

그러나 뭐든지간에 본질이 기본이되어야 하는법이다. 

본질적인 것만 알면 스택에 관한건 통!! 한다. ㅎㅎ 

 

스택의 세부 동작은 다음과 같은 두 경우를 통해 설명하겠다. 

[스택에 3을 push 하는 경우]

1. isFull을 통해 push하고자 하는 스택에 공간이 있는지 확인한다. 
2. 공간이 있다면, top의 값을 +1한다.
3. 해당 인덱스의 칸에 데이터를 삽입한다. 

[스택에 3을 pop 하는 경우]

1. isEmpty를 통해 pop하고자 하는 스택이 혹시 빈공간은 아닌지, 꺼낼 값이 없는건 아닌지 확인한다. 
2. 값이 있다면, top의 값을 -1 한다.
3. top의 값을 -1하기 전의 값을 반환한다.

이때 반환한 값, 배열의 데이터를 지우거나 하지 않는다. 

top의 값만 -1을 해준다. 

향후 이것은 아무 문제가 되지 않는다. 왜냐하면 top은 -1이 된 위치를 가리키기는데, isEmpty라던지 isFull을 통해 스택의 내부 사정을 물어볼 때 top을 통해 상태를 확인하기 때문이다. 

 

파이썬에서는 list자료 구조(그 외의 다른 자료구조 또한 사용가능), append()나 pop(), len()을 통해 스택을 쉽게 구현할 수 있다.