여행을 사랑하는 직장인의 개발이야기

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

IT/DataStructure 자료구조

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

CTHY 2020. 4. 30. 15:45

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의 활용 예시

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

'IT > DataStructure 자료구조' 카테고리의 다른 글

[자료구조 #1] Software Engineering Principles  (1) 2020.03.29
Comments