[자료구조] 간단한 Stack 구현

 

 

 

 

자료구조

Stack은 제한적으로 접근할 수 있는 선형 자료구조(LIFO-Last in First Out)이며 Stack은 한쪽에서만 입출력이 발생하는 자료구조이다.

Stack 자료구조

 

 

 

소스코드

#pragma once
/*--

Stack method
	pop,top,push,empty,size

Custom method
	safety_pop

--*/
typedef bool BOOL;
template<class T>
class Pstack;

template<class T>
class Node {
private:
	Node<T>* next_;
	T value_;
public:
	Node(const T& value) :value_(value), next_(nullptr) {}
	friend Pstack<T>;
};

template<class T>
class Pstack {
private:
	Node<T>* top_;
	size_t size_;
public:
	Pstack() :size_(0) {
		top_ = new Node<T>(0);
		top_->next_ = nullptr;
	}

	void Push(const T& value) {
		Node<T>* newNode = new Node<T>(value);
		newNode->next_ = top_;
		top_ = newNode;
		++size_;
	}

	T Pop() {
		T value = top_->value_;
		Node<T>* deleteNode = top_;
		top_ = top_->next_;
		delete deleteNode;
		--size_;
		return value;
	}

	T Top()const {
		return top_->value_;
	}

	BOOL Empty()const {
		return (0xFFFFFFFF & size_) == 0 ? true : false;
	}

	size_t Size()const {
		return size_;
	}

	T Safety_Pop()const {
		return (0xFFFFFFFF & size_) == 0 ? -1 : top_->value_;
	}

};

 

 

후기

자료구조를 다시 공부한다는 마음으로 시작한 첫 번째 자료구조 Stack이다. Stack은 자료구조 중에서 난이도가 낮은 편이기 때문에 구현할 Method도 적었고 기본적인 거만 구현했다..

POP은 비트 연산을 이용해서 구현해보았으며

Template을 사용해서 어떤 자료 형태에서도 돌아갈 수 있게 만들었다.  반복자도 추가해서 해보고 싶었지만 너무 욕심내는 거 같아서 나중에 추가해봐야겠다.

 

추가적으로 Safety 한 Pop을 만들어서 Pop에서 프로그램이 죽지 않고 -1을 반환할 수 있는 Method를 간단하게 구현하였다.

Queue, Priority_Queue, List, graph,Tree, Binary_Tree, Redblack_Tree까지 구현해보는 것이 목표이다.

 

 

 

출처 및 레퍼런스

 

Wiki: https://ko.wikipedia.org/wiki/스택