[바킹독의 실전 알고리즘] 0x05강 - 스택

1. 정의와 성질

 

정의

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조. 구조적으로 먼저 들어간 원소가 제일 나중에 나오는 구조(FILO)

 

🎯 참고로 스택, 큐, 덱은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 있으며 이들은 묶어 Restricted Structure이라고 함!

 

성질 - 원소의 추가/제거/상단 원소 확인 및 변경

 

1) 원소의 추가 시간복잡도는 O(1)

2) 원소의 제거 시간복잡도는 O(1)

3) 제일 상단의 원소 확인 시간복잡도는 O(1)

4) 제일 상단이 아닌 나머지 원소들의 확인 및 변경은 원칙적으로 불가능함!

물론 스택을 구현할 때 가장 상단이 아닌 나머지 원소들을 확인하거나 변경할 수도 있겠지만, 애초에 스택은 그런 의미로 만들어진 것이 아님! 실제 스택의 용례를 보아도 1), 2), 3)을 위해 쓰인 경우만 존재함. STL stack에서도 제시된 기능 외에 다른 기능은 제공되지 않음!

 

2. 기능과 구현

 

직접 구현 - push(), pop(), top()

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

const int MX = 1000005;
int dat[MX];
int pos = 0; //음 원래 배웠던 거랑 다르게 위치가 -1이 아니고 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();
}

 

3. STL 속 stack

 

STL 속 stack에서는 보통 push(), pop(), empty(), top(), size() 멤버 함수를 사용하게 됨. 

 

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

int main(void) {
  stack<int> S; //stack 선언
  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'; // 스택이 비어있는데 top을 호출하면 런타임 에러가 발생함
}

 

 📌stack 개념 참고

https://coding-factory.tistory.com/597

https://cplusplus.com/reference/stack/stack/