[자료구조] 스택(Stack)

스택(Stack)

스택은 선형 자료구조에서 대표적인 것 중에 하나다. 

스택을 떠올리면 가장 먼저 생각하는 것은 이러한 구조의 그림이다. 바구니에 책을 차례대로 쌓고, 이 것을 꺼내려면 가장 나중에 쌓은 책을 꺼내야 한다. 

많은 책에서 이 것을 LIFO(Last In First Out)라고 한다. 가장 나중에 들어 간 것이 가장 먼저 나온다는 의미다. 스택은 재귀 함수를 할 때도 많이 언급되는 자료구조이기도 하다.

스택을 구현할 때 배열을 이용해 하는 법과 리스트를 이용하는 방법이 있다. 나는 리스트로 구현을 했다. STL을 사용하지 못할 때는 이렇게 구현해서 써야하고, 개념을 이해하기 위해서는 직접 구현해보는 것이 좋은 것 같다. 나도 복습할 겸 다시 구현을 해봤다.

<소스코드>

	#include <cstdio>
	#include <iostream>
	using namespace std;
	template <typename T>
	class _stack {
	public:
	class Node {
	public:
	T data;
	Node *next;
	Node() {}
	Node(T data) : data(data),next(NULL){}
	};
	Node* Top = NULL;
	int _size = 0;
	void push(T data) {
	Node *newNode = new Node(data);
	_size++;
	if (Top == 0) {
	Top = newNode;
	}
	else {
	newNode->next = Top;
	Top = newNode;
	}
	}
	void pop() {
	if (_size == 0)return; //오류
	_size--;
	Node *temp = Top;
	Top = temp->next;
	delete temp;
	}
	T top() { return Top->data; }
	int size() { return _size; }
	bool empty() { return _size == 0; }
	};

view rawStack_STL.cpp hosted with ❤ by GitHub

[push()]

push(T data)는 데이터를 넣는 것이다. 리스트의 가장 마지막에 넣어주면 된다. 가장 마지막 데이터는 Top포인터가 가리키는 노드다. 새로운 노드가 생성되면, Top포인터는 새로운 노드를 가리키게 된다. 그리고 새로운 노드는 next포인터를 이용해 이전의 Top노드와 연결해준다.

[pop()]

노드를 지울 때는 Top 포인터가 가리키는 노드를 지워줘야한다. temp라는 임시 변수에 노드를 담아두고, Top을 밑에 있는 노드로 설정해준 뒤에 temp를 지워준다. 

[top()]

top()은 가장 위에 있는 데이터를 반환하는 함수이다. 스택은 가장 나중에 들어온 데이터만 확인할 수 있다.

[size()]

stack의 사이즈를 반환하는 함수이다. 이를 이용해 현재 stack에 쌓은 데이터의 갯수를 알 수 있다.

[empty()]

empty()는 stack이 비었는 지 알려주는 bool 반환형 함수이다. _size변수가 0이라면 true를 반환해주면 된다. 조건문에 자주 쓰이는 함수이기도 하다.

<소스코드>

	template <typename T>
	class _stack {
	public:
	int capacity, Top;
	T *arr;
	_stack() {
	capacity = 4;
	Top = 0;
	arr = new T[capacity];
	}
	~_stack() {
	delete[] arr;
	}
	void resize(int n) {
	T *temp = new T[n * 2];
	int idx = 0;
	for (int i = 0; i < Top; i++)temp[idx++] = arr[i];
	delete[] arr;
	arr = temp;
	Top = idx; capacity *= 2;
	}
	int size() { return Top; }
	void push(T data) {
	if (Top == capacity - 1)resize(capacity);
	arr[Top++] = data;
	}
	void pop() { Top--; }
	T top() { return arr[Top - 1]; }
	bool empty() { return Top == 0; }
	void clear() { return Top = 0; }
	};

view rawStack_STL.cpp hosted with ❤ by GitHub

다음은 배열을 통해 구현한 스택STL이다. 가변배열을 이용해서 구현을 했다. 리스트와 다른 점은 구성하는 내용은 같지만, 담는 데이터에 용량에 따라서 속도에서 차이가 날 수 있다는 점이다.

그리고 단순한 스택을 쓴다는 것에서 크게 차이가 없다고 생각하지만, 배열로 스택을 쓰게 되면 중간의 데이터에 접근해야할 경우에 용이하다. 

다음에 스택을 이용해서 풀었던 백준문제도 리뷰를 올릴 예정이다. 부지런하게...

출처: http://meylady.tistory.com/