[자료구조] 스택 (Stack)

스택 (Stack) 이란?

• 순서가 보존되는 선형 데이터 구조
• 스택은 LIFO(Last In, First Out) 구조로, 마지막에 들어간 데이터가 가장 먼저 나오는 자료구조를 이야기한다.
• 쌓인 접시나 하노이 탑을 예시로 생각하면 된다.

장단점

장점

• 데이터의 삽입과 삭제가 O(1) 시간으로 이루어져 빠르게 처리가 된다.

단점

• 중간과 마지막에 있는 데이터의 접근하려고하면 비효율적이다.

구현

#include <stack> 사용

#include <iostream>
#include <stack>

using namespace std;

int main(void) {

	stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	cout << s.top() << "\n"; // output : 3
	s.pop();
	cout << s.top() << "\n"; // output : 2

	if (!s.empty()) {
		cout << "not empty" << "\n"; // output : not empty
	}
	if (s.size()) {
		cout << "size : " << s.size() << "\n"; // output : size : 2
	}

	return (0);
}

 

정적할당 방식으로 구현

#ifndef CUSTOMSTACK_HPP
#define CUSTOMSTACK_HPP

#define MAX_SIZE 10000 // 실제로는 동적

#include <iostream>

template <typename T>
class CustomStack 
{
	private:
		T c[MAX_SIZE];
		int _top;
	public:
		CustomStack() : _top(-1) {};
		~CustomStack() {};

		void push(T data) {
			c[_top + 1] = data;
			_top++;
		}
		T pop() {
			T temp = c[_top];
			_top--;
			return temp;
		}
		size_t size() const {
			return _top + 1;
		}
		bool empty() const {
			if (size() == 0) return true;
			else return false;
		}
		T top() const {
			T temp = c[_top];
			return temp;
		}
};

#endif

• 실제 stack에 경우에는 동적으로 크기범위가 커도 동작을 하겠지만 간단하게 정적할당 방식으로 사용한 구현은 위와 같다.
• 스택(Stack)에 경우 메서드로 LIFO(Last In, First Out) 에 해당되는 선입후출에 해당되는 메서드만 존재한다.
• stack과 queue의 실제 구현에서도 deque방식이 사용되어 인터페이스 제한을 사용하여 구현되어있다.