[자료구조 씨자마 #2] FILO Stack 스택

C++로 자료구조 마스터하기 #씨자마2

 

---

 

Stack: value가 하나씩 쌓이고, 쌓이는 위치가 TOP이 된다. stack에서 삭제될 때는 가장 나중에 들어간 것이 먼저 나오는 Last in First out, LIFO 구조

 stack구조인 박스, 가장 위의 박스를 먼저 꺼내야 함

 

 

Stack ADT operations

• void MakeEmpty
  -stack의 비어있는 상태로 세팅
• bool IsEmpty
  -stack이 비어있으면 true, 비어있지 않으면 false를 반환
  -stack에서 pop연산 시 비어있는지를 확인
• bool IsFull
  -stack이 꽉 차 있으면 true, 꽉 차 있지 않으면 false를 반환
  -stack의 push연산 시 꽉 차 있는지를 확인
• void push
  -stack에서는 insert가 아닌 push를 주로 사용
  -stack의 top에 value를 넣음
  -IsFull이 true인 경우, exception을 throw
• void Pop
  -stack에서는 delete가 아닌 pop을 주로 사용
  -stack의 top에 있는 value를 삭제
  -IsEmpty가 true인 경우, exception을 throw
• Top
  -stack의 top에 있는 value를 리턴
  -IsEmpty가 true인 경우 exception을 throw

 

---

 

#Stack.cpp

StackType::StackType() {
	top=-1; //생성자를 통해 top 초기화
}

bool StackType::IsEmpty(){
	return (top==-1); //top이 -1이면, 즉 비어있으면 true return
}

bool StackType::IsFull(){
	return (top==MAXITEM-1); //maxitem보다 top이 1 작을 경우 꽉 찬 것이기 때문에 true return
}

void StackType::Push(int item){
	if (IsFull())
    	throw FullStack();
    top++;
    items[top]=item; //stack의 top에 item 넣어 줌
}

void StackType::POP(){
	if (IsEmpty())
    	throw EmptyStack();
    top--; //top을 줄임
}

int StackType::Top(){
	if (IsEmpty())
    	thorw EmptyStack();
    return items[top]; //stack의 top에 있는 value return
}
	

 

---

 

Stack의 활용 예시

• 역순 문자열 만들기
• 웹 브라우저 뒤로 가기 - 가장 나중에 닫힌 웹 브라우저부터 띄움