Linked Stack

• topPtr

  • 필요 이유

    : 동적 할당 부분에 접근하려면 무조건 포인터가 있어야 한다.

    첫 노드를 제외한 다른 노드들은 다른 포인터들에 의해 가리켜진다.

    top node를 가리킬 포인터가 필요!

  • 처음에 nullptr

• push()

  • push(5)
  1. ‘NodeType’ 만들기
  2. NodeType 의 value를 5로 만들기
  3. NodeType 의 next 포인트를 old top으로 바꾸기
  4. topPtr 이 newNode 를 가리키게 만들기

  #include "StackType.h"
  
  void StackType::push(ItemType new_value){
  	//Exception Handling - isFull() -> return or throw;
  	NodeType* newNode;
  	newNode = new NodeType;
  	
  	newNode -> value = new_value;
  	newNode -> next = topPtr;
  	topPtr = newNode;
  }
  

• Edge cases

  • 소프트웨어 개발에서 일반적이지 않은 시나리오를 의미
  • 일반적이지 않은 input에서 예상치 못한 행동을 발생시킬 수 있음

• isFull()

  • Heap은 유한한 공간이기 때문에 계속 push 할 때마다 new를 만들 수 없다.

  #include "StackType.h"
  
  bool StackType::isFull(){
  
  	NodeType* newNode;
  	
  	try{
  		newNode = new NodeType;
  		delete newNode;
  		return false;
  		}
  		
  	catch (std::bad_aloc exception){ // full 일 경우
  		return true;
  		}
  }
  

• pop()

  • 동적 할당 부근에 접근하려면 무조건 포인터가 있어야 함.

  → tempPtr을 만들어 pop 되어야 할 노드를 가리키게 하여 지운다.

  #include "StackType.h"
  
  ItemType StackType::pop(){
  	// Exception Handling - isEmpty() -> return or throw
  	NodeType* tempPtr;
  	tempPtr = topPtr;
  	
  	topPtr = topPtr -> next;
  	Itemtype ret = tempPtr -> value;
  	
  	delete tempPtr;
  	tempPtr = nullptr
  	
  	return ret;
  	}
  

• isEmpty()

  • topPtr = nullptr

• Destructor

  • Node가 동적할당 된 애들이므로 delete(해제) 해주어야 함

  #include "StackType.h"
  
  StackType::~StackType(){
  	NodeType* tempPtr = topPtr;
  	
  	while (tempPtr != nullptr){
  		tempPtr = topPtr;
  		topPtr = topPtr -> next;
  		delete tempPtr;
  		tempPtr = nullptr; // tempPtr이 가리키는 공간만 사라진 것이므로 null로 바꿔주는 것이 좋다.
  		}
  }
  

• size()

  #include "StackType.h"
  
  int StackType::size(){
  	NodeType* tempPtr = topPtr;
  	int length = 0;
  	
  	while(tempPtr != nullptr){
  		length++;
  		tempPtr = tempPtr -> next;
  		}
  		
  	return length;
  	
  }
  

Linked Queue

• pFront, pRear 포인터 활용

• enqueue()

  #include "QueueType.h"
  
  void QueueType::enqueue(Itemtype new_value){
  	//Exception Handling - isFull() -> return or throw;
  	Nodetype* newNode;
  	newNode = new NodeType;
  	
  	newNode -> value = new_value;
  	
  	if(!isEmpty()){
  		pRear -> next = newNode; //(*pRear).next = newNode
  		//empty 일 경우 *pRear.next가 가리키고 있는 애가 없으므로 오류임
  		}
  		
  	else{
  		pFront = newNode;
  		}
  	pRear = newNode;
  }