[자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘

스택이란

스택은 우물과도 같습니다.  가장 마지막에 들어간 데이터가 맨위에 쌓이게 되고, 데이터를 가져올 때 맨 위에 쌓인 (즉, 가장 마지막에 들어간) 데이터를 먼저 빼내야 합니다.

-메- 우물?

---

스택 기능

스택에는 자주 사용되는 5가지 메소드 (method)가 존재합니다.

push(data)

스택에 데이터를 넣습니다. 들어간 데이터는 스택의 맨 위 (top)에 위치합니다.

top()

스택의 맨 위에 위치한 데이터에 접근합니다. 만약 스택이 비어있는 경우 런타임 에러를 발생시킵니다.

pop()

스택의 맨 위에 위치한 데이터를 빼냅니다. top과 마찬가지로 스택이 빈 경우 런타임 에러를 발생시킵니다.

size()

스택에 현재 저장되어있는 데이터의 개수를 반환합니다. 

empty()

스택이 비어있는지 확인합니다. 비어있다면 true를 반환하고, 데이터가 있다면 false를 반환합니다.

---

스택 구현

www.acmicpc.net/problem/10828

10828번: 스택

위의 백준 10828번: 스택 문제에 맞춰서 약간 수정한 버전입니다.

런타임 에러가 발생할 수 있는 조건에서 -1을 대신 반환하도록 수정했습니다.

arr배열은 데이터가 저장될 공간이며 last는 스택의 top에 해당하는 위치를 가리킵니다. 

그러므로 스택이 비어있다면 last는 -1을 가리키며 0보다 작으므로 empty()를 호출할 시 true를 반환하게 됩니다.

나머지 부분은 위에 설명드린것과 같습니다.

struct stack {

	int arr[10000];
	int last;

	void init() {
		last = -1;
	}
	void push(int data) {
		arr[++last] = data;
	}
	bool empty() {
		return (last < 0);
	}
	int pop() {
		if (empty()) {
			return -1;
		}
		return arr[last--];
	}
	int size() {
		return last + 1;
	}
	int top() {
		if (empty()) {
			return -1;
		}
		return arr[last];
	}
};

 

사용법은 아래와 같습니다.

먼저 스택을 선언하고 초기화를 시켜줍니다.

stack s;
s.init();

이 후 모든 메서드는 아래와 같이 작성하면 됩니다.

s.push(num);
s.pop();
s.size();
s.empty();
s.top();

 

아래는 10828번: 스택 문제 풀이입니다.

#include <iostream>
#include <string>

using namespace std; 
struct stack {

	int arr[10000];
	int last;

	void init() {
		last = -1;
	}
	void push(int data) {
		arr[++last] = data;
	}
	bool empty() {
		return (last < 0);
	}
	int pop() {
		if (empty()) {
			return -1;
		}
		return arr[last--];
	}
	int size() {
		return last + 1;
	}
	int top() {
		if (empty()) {
			return -1;
		}
		return arr[last];
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	stack s;
	s.init();
	for (; n--;) {
		string str;
		int num;
		cin >> str;
		if (str == "push") {
			cin >> num;
			s.push(num);
		}
		if (str == "pop") {
			cout << s.pop() << "\n";
		}
		if (str == "size") {
			cout << s.size() << "\n";
		}
		if (str == "empty") {
			cout << s.empty() << "\n";
		}
		if (str == "top") {
			cout << s.top() << "\n";
		}
	}
}

 

템플릿을 사용한 스택

#include <iostream>
#include <string>

#define MAX_SIZE (10000)
using namespace std;

template <typename T>

class stack {
private:
	T data[MAX_SIZE];
	int _top;

public:
	stack() {
		_top = -1;
	}
	~stack() {

	}
	void push(T inputdata) {
		data[_top + 1] = inputdata;
		_top += 1;
	}
	T pop() {
		T res = data[_top];
		_top -= 1;
		return res;
	}
	int size() {
		return _top + 1;
	}
	bool empty() {
		return size() == 0 ? true : false;
	}
	T top() {
		T res = data[_top];
		return res;
	}
};

int main() {
	
	ios_base::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);

	stack<int> s;

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string com;
		cin >> com;
		if (com == "push") {
			int data;
			cin >> data;
			s.push(data);
		}
		else if (com == "pop") {
			if (s.empty()) {
				cout << "-1\n";
			}
			else{
				cout << s.pop() << "\n";
			}
		}
		else if (com == "size") {
			cout << s.size() << "\n";
		}
		else if (com == "empty") {
			cout << s.empty() << "\n";
		}
		else {
			if (s.empty()) {
				cout << "-1\n";
			}
			else {
				cout << s.top() << "\n";
			}
		}
	}

}