C/C++) 자료구조 - Stack, 스택
알고리즘 공부를 시작했다.
이를 위해서는 자료구조에 대한 지식이 바탕이 되어 있어야 하기에 여러가지 자료구조에 대해 정리하려 한다.
첫번째로 정리할 자료구조는 Stack, 스택이다.
목차
- 스택의 정의
- 스택의 구현
- STL스택
1. 스택의 정의
스택은 톱(top)이라고 하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)이 일어나는 순서리스트이다.
스택을 그림으로 표현하면 아래와 같다.
그림을 보면 원소들이 탑처럼 쌓여있는 것을 볼 수 있다.
앞서 말했듯 top에서 push와 pop이 이루어지기 때문에
후입선출, LIFO(Last-In-First-Out) 구조를 띈다.
2. 스택의 구현
이제 스택을 구현해보자. 스택에 자주 쓰이는 메소드는 크게 5가지가 있다.
push()
스택에 원소를 삽입한다. 원소는 스택의 top에 위치한다
pop()
스택의 맨 위에 있는 top 원소를 삭제한다. 스택이 빈 경우 런타임 에러를 발생시킨다.
top()
스택의 맨 위에 있는 top 원소의 값을 반환한다. pop과 마찬가지로 스택이 빈 경우 런타임 에러를 발생시킨다.
empty()
스택이 비었다면 1, 아니라면 0을 반환한다.
size()
스택의 크기, 스택 내의 원소의 수를 반환한다.
class Stack{
private:
int arr[100005]={}; //배열을 이용해 구현
int pos=0; //스택의 top을 따라간다
public:
void push(int a){arr[pos++]=a;}
void pop(){
if(pos==0) cout<<"-1\n";
else{ cout<<arr[--pos]<<"\n"; }
}
void top(){
if(pos==0) cout<<"-1\n";
else{ cout<<arr[pos-1]<<"\n"; }
}
void empty(){
if(pos==0) cout<<"1\n";
else cout<<"0\n";
}
void size(){cout<<pos<<"\n";}
};배열을 이용해 stack class를 구현했다.
pos는 스택의 top을 표시하는 역할을 한다.
pop과 top은 위에서 언급했듯 빈 스택에서 수행될 경우 런타임 에러가 발생할 수 있으므로 예외처리를 해주었다.
3. STL스택
STL스택도 앞서 구현한 스택과 사용법이 크게 다르지 않다.
먼저 STL스택을 사용하기 위해 헤더파일을 포함시켜주자
#include<stack>헤더를 불러왔으니 이제 스택을 사용할 수 있다.
스택의 선언은 아래와 같다.
stack<int> s;stack<자료형> 이름; 의 방식으로 선언하면 된다.
스택의 메소드들은 아래와 같은 방식으로 사용할 수 있다.
s.push(3); //3이 top
s.push(1); //1이 top
s.pop(); //1 pop
s.top(); //3
s.empty(); //비지 않았으므로 0
s.size(); //1