Stack

• LIFO (Last In First Out)
• 삽입과 삭제가 모두 top에서 이루어진다.
  

※linked list를 사용하여 stack 구현

Stack Class

template <class Item>
class stack {
public:
	stack(node<Item>* init_ptr = NULL) {
		top_ptr = init_ptr;
	}
	void push(const Item& data);
	void pop();
	bool empty() const;
	Item top() const;

private:
	node<Item>* top_ptr;
};

push

template <class Item>
// 데이터를 top_ptr 위치에 삽입
void stack<Item>::push(const Item& data) {
	//Linked list의 가장 앞에 데이터 삽입
	head_insert(top_ptr, data);
}

Linked list를 사용하여 구현한 Stack은 stack overflow를 고려하지 않아도 된다.

empty

template <class Item>
bool stack<Item>::empty() const {
	return top_ptr == NULL;
}

Stack이 비어으면, true 반환.

pop

template <class Item>
void stack<Item>::pop() {
	//stack underflow
	assert(!empty());
	head_remove(top_ptr);
}

Stack이 비어있는 경우 stack underflow를 고려해야 한다.

top

template <class Item>
Item stack<Item>::top() const {
	// Stack 비어있으면 error
	assert(!empty());
	return top_ptr->data();
}