[알고리즘 공부] 실전 알고리즘 5강-스택

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

정의

스택은 구조적으로 먼저 들어간 원소가 나중에 나오는 LIFO(Last In First Out) 자료구조이다.

성질

1) 원소의 추가는 O(1)
2) 운소의 제거는 O(1)
3) 제일 상단의 원소 확인이 O(1)
4) 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로는 불가능하다.

---

구현

스택은 배열 혹은 연결리스트로 구현을 할 수 있다.

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

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

void push(int x) // 스택에 x를 추가
{
	dat[pos++] = x;
}

void pop() // 꼭대기에 위치한 원소 제거
{
	// 굳이 pos에 있는 값을 없앨 필요가 없는게 어차피 
    	// 나중에 push를 하면 push 되는 값으로 덮여지게되기 때문이다.
	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으로 구현

push, pop, top, empty, 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 발생
}

1) stack이 empty상태 일때 top이나 pop을 호출하면 runtime error가 발생하게 된다.