[자료구조][C++] 스택(stack) 정리

---

1. 스택이란?

• stack은 쌓는다는 의미를 가지는 자료구조이다.
• LIFO(Last In First Out) 나중에 넣은 게 먼저 나오는 특성을 가진다.
• FILO(Fist in Last Out) 먼저 넣은 게 나중에 나오는 특성을 가진다. (결국엔 LIFO와 FILO는 같은 말이다.)
• 쉽게 프링글스통이라고 생각하거나 바닥이 막힌 상자라고 생각하면 된다.

               -> 나중에 들어간 원소가 나올 때는 먼저 나오는 특성을 보인다.

---

2. 스택의 성질

• 원소의 추가와 제거 O(1)
• 제일 상단 원소 확인 O(1)
• 특정 데이터를 찾기 O(n)

  ---

3. 스택의 기능

• push : 스택에 원소를 추가하는 기능 (밀어넣는다)
  

  

  push 기능

• pop : 스택 꼭대기에 위치한 원소를 제거하는 기능(맨 마지막에 넣은 원소 제거)
  

  

  pop 기능

• top : 스택 꼭대기에 위치한 원소의 값 확인 (맨 마지막에 넣은 원소)
  

  

  top 위치

• empty : 스택이 비어있으면 1 리턴, 아니면 0 리턴
• size : 스택에 들어있는 정수 개수 출력

  ---

 

4. 스택 구현 방법

 4-1) 직접 구현

• 전역함수 설정
  

  const int MAX = 100000;
  int stack[MAX];  # 사이즈 큰 배열 생성	
  index = 0;​  # 다음 원소가 추가 될 때 삽입해야 할 곳 가리킴

  

    stack[0] = 10, stack[1] = 20, stack[2] = 20 데이터가 저장돼있다.

• push 함수
  위 상태의 스택에 40이라는 원소를 넣으려고 할 때, 현재 index 위치에 40을 넣어주고 index는 하나 올려주면 된다. (index는 다음 원소가 들어갈 위치이므로)
  

  

  void push(int x){
  	stack[index++] = x;
  }​

  ++는 후위연산자이기 때문에 먼저 stack[index] = x의 값을 넣고나서 index++를 해준다.
  
  
• pop 함수
  위 상태에서 pop을 해주는 것은 맨 위에 있는 원소 40을 빼주는 것인데 이것은 index 위치만 하나 줄이면 된다. 
  그 이유는 나중에 push가 나오면 index 위치에 값이 덮어쓴다. 
  

  

  void pop(){
  	index--;
  }​

• top 함수
  index-1 위치에 있는 배열을 반환하면 된다.
  

  

  이 상태에서 top은 40이다. 따라서 40을 출력하려면 stack[index-1]
  

  int top(){
  	return stack[index-1];
  }​

• empty 함수
  
  index가 0자리에 있으면 스택에 원소는 없다. 그 이유는 index는 다음에 올 원소 위치를 알려주는데 그 자리가 0이라는 것은 스택에 아무 것도 없고 이제 원소가 들어오면 0번째 자리가 된다는 것이다.
  

  int empty(){
  	if (index == 0) return 1;
  	else return 0;
  }

•  size 함수
  사실 size 함수는 index랑 같다. index는 0부터 시작하고 size는 개수이기 때문에 1부터 시작한다.
  

  

  여기서 index 위치는 4이고 원소의 개수도 4개이기 때문에 index = size이다.
  따라서 만들 필요도 없지만 공부용으로 해보자면,
  

  int size(){
  	return index;
  }​

• Total
  

  #include <iostream>
  using namespace std;
  
  const int MAX = 100000;
  int stack[MAX];
  int index = 0; ​ 
  
  void push(int x) {
  	stack[index++] = x;
  }
  
  void pop() {
  	index--;
  }
  
  int top() {
  	return stack[index - 1];
  }
  
  int empty() {
  	if (index == 0) return 1;
  	else return 0;
  }
  
  int size() {
  	return index;
  }​

4-2) 스택 라이브러리 이용

이번에는 STL stack을 써보겠다.

헤더파일에 스택을 추가하고 스택을 정의를 해주면 된다.

#include <stack>
using namespace std;

int main(){
	stack<int> st;
}

예를 들어 이러한 코드가 있다고 하면 'st'이름을 가진 스택이 생성된 것이다.

이 STL stack의 방법은 예제를 이용해서 한 줄씩 이해해보는 게 나을 것 같다.

#include <stack>
#include <iostream>
using namespace std;

int main() {
	stack<int> st; //st 스택 생성
	st.push(10); //10
	st.push(20); //10 20
	st.pop(); //10
	cout << st.size(); //1
	st.push(30); //10 30
	st.push(40); //10 30 40
	st.push(50); //10 30 40 50
	cout << st.top(); // 50
	if (st.empty())
		cout << "st is empty.";
	else cout << "st is not empty.";
	st.pop(); // 10 30 40
}

스택에 데이터를 추가하려면 (스택이름).push(넣을 데이터)
스택에 데이터를 삭제하려면 (스택이름).pop()

스택의 마지막 원소 확인하려면 (스택이름).top()  => cout을 해야 출력된다

스택의 사이즈를 확인하려면 (스택이름).size()  => cout을 해야 출력된다.

스택이 비어있는지 확인하려면 (스택이름).empty() 

 

 

+)만약 스택에서 런타임에러가 발생했을 경우, 스택이 비어있을때 pop이나 top을 호출했는지 확인해보자!

 

 

 

정보가 틀릴 수도 있습니다. 틀린 부분은 알려주시면 정말 감사하겠습니다.