3. 스택 (Stack)

dyeoma.tistory.com/4

자료구조 개념, 종류

 

Stack class 선언

Private:
   T *stack;		// stack 원소 저장 배열
   int top;		// top 원소 위치
   int capacity;	// stack 배열 크기
Template <class T>
Stack<T>::Stack (int stackCapacity): capacity(stackCapacity){	// 생성자
   if(capacity < 1) throw "Stack Capacity must be > 0";
   stack = newe T[capacity];
   top = -1;
}

초기 top = -1

empty 상태 top = -1

full 상태 top = capacity-1

 

 

Stack 삽입 - O(1) 소요

template <class T>
void Stack<T>::Push(const T& x){
   if(top == capacity-1){		// 배열 크기 2배 확장
      ChangeSizeID(stack, capacity, 2*capacity);
      capacity *=2;
   }
   stack[++top]=x;
}

 

 

Stack 삭제 - O(1) 소요

template <class T>
T* Stack<T>::Pop(T& x){
   if(top==-1)		// empty stack
      return 0;		// null 반환
   x = stack[top--];	// x = 삭제되는 값
   return &x;		// x 주소 반환
}