02) 스택(Stack)의 개념 및 구현

들어가며

---

과외를 시작했다.

편입을 준비하는 학생인데 내가 사실 컴퓨터 분야 과외는 처음이고 

편입 과외는 더더욱 처음이라, 뭐부터 시작해야할지 잘 모르겠다.
과외를 빌미삼아 자료구조랑 알고리즘을 더 열심히 정리하는 기회로 삼아야겠다.

 

오늘은 자료구조 중에 가장 기초라할 수 있는 스택(stack)에 대해 포스팅 해보고자 한다.
스택을 공부하면서 나에게 가장 어려웠던 점은, 이 스택이라는 용어를 너무 여기저기 쓴다는 점이었다.
자료구조에도 나오고 프로세스 구조에도 나오고 심지어는 C++ STL에서도 등장한다.

여기서 주목할 점은 스택은 LIFO의 방식으로 데이터를 처리하는 자료구조인데
이러한 자료구조를 따르는 모든 아키텍처에 스택이라는 이름을 붙여놨다는 점이다. 
이 점만 기억하면 스택은 정말 쉬운 개념이다.

 

개념 및 특징

---

• LIFO(Last In First Out)으로 데이터를 저장/처리한다.
• stack pointer 또는 top은 스택의 마지막 데이터가 저장된 위치를 가리킨다.

소스코드(C++)

---

#include <iostream>

using namespace std;

#define MAX 100

template <typename T>
class Stack {
	T s[MAX];
	T ptr;
public:
	Stack(void)
		:ptr(-1) {}
	T top(void) const {
		return s[ptr];
	}	
	bool empty(void) const {
		return ptr==-1;
	}
	size_t size(void) const {
		return ptr+1;
	}
	void push(T v) {
		if(ptr==MAX) {
			cerr << "ERROR: stack is full" << endl;
			return ;
		}
		s[++ptr] = v;
	}
	T pop(void) {
		if(ptr==-1) {
			cerr << "ERROR: stack is empty" << endl;
			return -1;
		}
		return s[ptr--];	
	}
	const T operator[] (size_t i) const {
		return s[i];
	}
	T operator[] (size_t i) {
		return s[i];
	}
	friend ostream& operator << (ostream& os, const Stack& st) {
		for(int i=0;i<st.size();++i)
			os << st[i] << ' ';
		return os;	
	}
};

int main(void)
{
	Stack<int> st;
	st.push(1);
	st.push(2);
	cout << st << endl;
	st.pop();
	cout << st << endl;
	st.pop();
	cout << st << endl;
	st.pop();
	cout << st << endl;
	st.push(3);
	cout << st << endl;
	cout << st.top() << endl;
	st.push(5);
	cout << st.top() << endl;
	cout << st.size() << endl;
	return 0;
}