[ 알고리즘 ] 스택 , STL stack

스택이란 선입후출의 자료구조이다.

 

원소의 추가,제거,제일상단의 원소확인이 O(1)에 가능하지만

다른 위치의 원소확인과 변경이 원칙적으로 불가능하다. 

하지만 배열과 연결리스트로 스택을 구현한다면 가능하다.

 

1. 배열로 스택 구현하기

cosnt in MX=1000005;
int dat[MX];
int pos=0  //위치

void push(int x){
	dat[pos++]=x;
}
void pop(){
	pos--;
}
void top(){
	dat[pos-1];
}

 

 

2. STL

 

#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 발생
}