Linked Stack

Linked 리스트를 구현할 때 중요한 점은 Item을 추가,삭제할 때 포인터들을 잘 연결해주는 것이다.

garbage를 만들지 않기 위해 Push,Pop할 때 tempPtr을 이용하자.

Add newItem to stack

NodeType* location을 선언하자.

location은 데이터(info)와 다음 노드를 가리키는 포인터(next)를 갖는다.

 

class LinkedstType

LinkedstStack() 

스택의 맨 위를 가리키는 노드 하나를 만들자. 초기 설정 NULL

LinkedstType::LinkedstType(){
	topPtr = NULL;
    }

~LinkedstStack()

스택이 scope 밖으로 벗어나면 스택의 로컬변수인 topPtr은 자동으로 할당 해제된다.

그러나 topPtr이 가리키는 노드는 남아있기 때문에 이 메모리를 해제해줘야함!!

LinkedstType::~LinkedstType(){
NodeType* tempPtr;

while(topPtr != NULL){
	tempPtr = topPtr;
	topPtr = topPtr -> next;
	delete tempPtr;
	}
}

 

bool IsEmpty()

bool LinkedstType::IsEmpty(){
	return topPtr == NULL
    }

bool IsFull()

새 노드 만들고 지우는거 성공하면 노드 만들 메모리 아직 존재 -> return false

실패하면 IsFull 

bool LinkedstType::IsFull(){
	NodeType* location;
    try{
    	location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc exception){
    	return true;
    	}
    }

 

void Push(ItemType newItem)

일단 스택 꽉 차있는지 확인하고 아닐때만.

새로운 아이템 넣으려면 새 location을 생성해야한다. location의 info에 값 넣고 next가 topPtr 가리키도록, topPtr이 location을 가리키도록 한다.

=> 스택 맨 위에 location이 올라가고 location의 next가 원래 스택 가리킴.

void LinkedstType::Push(ItemType newItem){
if(IsFull()){
	throw FullStack();
	}
else{
	NodeType* location;
    location = new NodeType;
    location -> info = newItem;
    location -> next = topPtr;
    topPtr = location;
}

 

void Pop()

일단 스택 비어있는지 확인해보고 아닐때만.

tempPtr 만들어서 스택의 현재 맨 위 노드를 가리키게 한다. 

현재 노드는 다음 노드를 가리키게 하고 tempPtr 삭제.

void LinkedstType::Pop(){
if(isEmpty()){
	throw EmptyStack();
    }
else{
	NodeType* tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr -> next;
    delete tempPtr;
}

 

ItemType Top()

맨 위 가리키고 있는 topPtr 있으니까 간단하다.

ItemType LinkedstType::Top(){
if(isEmpty()){
    throw EmptyStack();
}
else{
	return topPtr->info;
}