[ 자료구조 ] 스택 Stack 정리 및 STL 사용법

 

 

# 만약 스택을 이용한 알고리즘 문제를 풀고 싶다면, 블로그에 스택을 검색하면 스택을 이용하여 풀이한 문제들이 나와있습니다. 

스택이란?

스택이란, LIFO의 구조를 가진 자료구조를 의미한다. 여기서 LIFO는 Last In Fisrt Out으로 마지막에 입력된 요소가 가장 먼저 출력된다는 구조이다. 

 stack 

위의 그림을 참고하면 이해하기 쉬울 것이다.

1. 먼저 3이 입력이 되면, stack 맨 아랫단에 위치하게 됩니다.
2. 두번째, 4가 입력 되면, 3의 바로 위에 위치하게 됩니다.
3. 이를 반복합니다. 
4. pop[출력]이 되면, 쌓아 놓은 탑 중에 가장 위에 값을 없애고 출력합니다. 

이러한 형식을 가진 자료구조를 스택이라고 하며, LIFO(Last In Front Out)라고 합니다. 이러한 자료구조는 가장 최근에 입력한 값의 접근이 필요할 때, 유용합니다. 

스택 활용

1. 재귀함수 : 재귀함수를 호출할 때마다 시스템 스택에 이전 함수의 데이터를 저장한다. 이후 함수가 완성되면 시스템 스택에 저장한 내용을 호출하여 다시 함수를 진행한다.
2. 웹 브라우저 뒤로가기 : 웹 브라우저의 뒤로가기에도 스택이 사용된다. 방문기록을 스택에 쌓아서 관리하기에 뒤로가기가 가능하다. 
3. 실행 취소 
4. 역순 문자열 만들기 
5. 수식의 괄호 검사 
6. 후위 표기법 계산  

 

스택 구현 _ 배열

#include <iostream>
using namespace std;
int main() {
	int stack[1000] = { 0 }; 
	//배열을 선언할 때는 초기화를 필수적으로 해야 오류를 피할 수 있다. 

	int top_point = -1;
	//stack의 꼭대기(top)을 가리키는 인테스용 변수이다. 

	for (int i = 0;i < 10;i++) {
		stack[++top_point] = i;
	}
	//인덱스 0부터 9까지 0~9의 값을 입력하였다.

	cout << stack[top_point--] << endl;
	//9가 출력된다. - pop의 기능

	cout << stack[top_point--] << endl;
	//8가 출력된다.

	stack[++top_point] = 10;
	//현재 stack의 상태 : 0 1 2 3 4 5 6 7 10

	return 0;
}

 이렇게 배열과  인데스용 변수를 하나 선언하여 직접 스택처럼 이용할 수 있다. 이는 스택 말고도 다양한 자료구조로 접근이 가능하다. 또한, STL를 이용하지 않고 사용가능하다. 단점으로는 선언하고 관리하기가 귀찮다. 

스택을 더 편하게 이용하기 위해서는 STL를 이용하면 된다.  

 

스택 구현 _ STL

#include <iostream>
#include <stack>
using namespace std;
int main() {
	stack<int> s;
	for (int i = 0;i < 10;i++) {
		s.push(i);
	}
	cout << s.top();
	s.pop();
	//s의 상황 : 0 1 2 3 4 5 6 7 8

	cout << s.top();
	s.pop();
	//s의 상황 : 0 1 2 3 4 5 6 7
	
	s.push(2);
	//s의 상황 : 0 1 2 3 4 5 6 7 2

	return 0;
}

스택 STL을 사용하기 위해서는 #include<stack>을 필수적으로 해줘야된다. 

stack<int> s; int형 변수인 스택을 s를 선언한다.                             

s.push(1); 스택 s에  1의 값을 추가한다.                                        

s.top(); 스택 s의 가장 위에 값을 의미한다.                                     

s.pop(); 스택 s의 가장 위에 값을 삭제한다.                                     

s.empty(); 스택 s가 비어있는지 확인한다. 비어있으면 true를 의미하고 안에 값이 있다면 false를 의미하다. 이는 if문에 유용하게 사용된다. ex) if(s.empty()) { (1) } 라고 코딩하면 s 안에 값이 없을 때, (1)의 코드가 실행된다. 

s.size(); 스택 s의 크기를 리턴한다. 만약 s에 값이 4개가 들어가 있다면, s.size()는 4를 의미한다. 이는 for문에서 유용하게 사용된다. ex) for(int i=0;i<s.size();i++){ s.pop(); } 처럼 사용하면 for이 s사이즈만큼 돌면서 모든값을 pop할 수 있다.