04-(1) ADTs Stack

스택 (Stack)

• 논리적인 (ADT) 수준에서의 스택
  • 동일한(homogeneous) 요소들로 구성된 순서가 있는 그룹으로, 요소의 삽입 및 제거는 스택의 ‘top'에서만 수행될 수 있다.

    따라서 반복자(iterator)가 필요하지 않는다.

  • LIFO (Last In, First Out) 구조
    
    

---

스택의 연산

✏️ StackType.h 의 예외 처리 (exception handling)

// exception class thrown by pushing when stack is full
class FullStack {};

// exception class thrown by popping or topping when stack is empty
class EmptyStack {};

✏️ 오버플로우와 언더플로우

• overflow 에러
  : 지정된 메모리 크기보다 더 많은 메모리를 사용하게 되어 발생하는 문제
• underflow 에러
  : 해당 메모리에 데이터가 존재하지 않는데 데이터에 접근하려고 하는 경우 발생하는 문제

  둘 모두 런타임 오류이다

• 생성자 (Constructor)
  : 스택 초기화

  StackType::StackType() {
  	top = -1;
  }

• 변환자 (Transformer)
  • MakeEmpty
    : 스택을 비어 있는 상태(empty state)로 설정
    
    
  • Push

    void StackType::Push(ItemType newItem) {
    // post: if stack is full, FullStack exception is thrown. 
    //       otherwise, newItem is at the top of the stack. 
    	if(IsFull())
    		thorw FullStack(); //check the overflow
    	top++;
    	items[top] = newItem;
    }

  • Pop

    void StackType::Pop(ItemType newItem) {
    // post: if stack is empty, EmptyStack exception is thrown. 
    //       otherwise, top elemnet has been removedfrom stack.
    	if(IsEmpty())
    		thorw EmptyStack(); //check the overflow
    	top--;
    }

    메모리에 저장되어 있는 데이터를 제거하는 것이 아닌, top 인덱스를 조정함으로써 마치 삭제된 것처럼 나타내고, push 시 덮어씌우는 원리

• 관찰자 (Observer)
  • IsFull

    bool StackType::IsFull() const {
    	return (top == MAX_ITEMS - 1);
    }
    // top은 index니까 -1

  • IsEmpty

    bool StackType::IsEmpty() const {
    	return (top == -1);
    }

  • Top

    ItemType StackType::Top() {
    // function: returns a copy of top item on the stack.
    	if (IsEmpty())
    		throw EmptyStack();
    	return items[top];
    }