스택

스택이란 한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. 

LIFO(Last in First out) 자료구조라고 부른다. 참고로 큐나 덱도 스택처럼 특정 워치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려 있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 

 

스택의 성질

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 - 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다.

스택 구현

스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있다. 둘 중에서 배열을 이용하는게 구현이 더 쉽다.

원소를 담은 큰 배열 한 개와 인덱스를 저장할 변수 한 개만 필요하다. 

스택의 값들은 dat의 0번지부터 저장되고 pos는 다음에 원소가 추가될 때 삽입해야하는 곳을 가리키고 있다. pos의 값이 곧 스택의 길이, 즉 스택 내의 원소의 수를 의미한다는 것을 알 수 있다. push 함수는 스택에 x를 추가하는 함수이고, pop함수는 스택의 꼭대기에 위치한 원소를 제거하는 함수이고, pop함수는 스택의 꼭대기에 위치한 원소의 값을 확인하는 함수이다.

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x){
  dat[pos++] = x;
}

void pop(){
  pos--;
}

int top(){
  return dat[pos-1];
}

void test(){
  push(5); push(4); push(3);
  cout << top() << '\n'; // 3
  pop(); pop();
  cout << top() << '\n'; // 5
  push(10); push(12);
  cout << top() << '\n'; // 12
  pop();
  cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

---

STL stack

STL stack에서는 주로 push, pop, top, empty, size 함수를 쓰게 될 것이다. empty는 스택이 비어있으면 true, 아니면 false를 반환한다. size는 스택 사이즈를 반환. 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  stack<int> S;
  S.push(10); // 10
  S.push(20); // 10 20
  S.push(30); // 10 20 30
  cout << S.size() << '\n'; // 3
  if(S.empty()) cout << "S is empty\n";
  else cout << "S is not empty\n"; // S is not empty
  S.pop(); // 10 20
  cout << S.top() << '\n'; // 20
  S.pop(); // 10
  cout << S.top() << '\n'; // 10
  S.pop(); // empty
  if(S.empty()) cout << "S is empty\n"; // S is empty
  cout << S.top() << '\n'; // runtime error 발생
}

스택이 비어있는데 top을 호출하면 런타임 에러가 발생한다. 스택이 비어있는데 pop을 호출해도 마찬가지이다. 그렇기 때문에 스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 해야한다. 만약 런타임 에러를 받았다면 스택이 비어있을 때 top이나 pop을 하지 않았을지 의심해보자. 

 

출처 : https://blog.encrypted.gg/933