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

스택

• 한쪽 끝에만 원소를 넣거나 뺄 수 있는 자료구조
  • Restricted Structure: 스택, 큐, 덱
• ex. 프링글스 통, 엘리베이터
• FILO(First In Last Out) 자료구조
  • 먼저 들어간 원소가 나중에 나오는 구조

성질

1. 원소의 추가 / 제거 O(1)
2. 제일 상단의 원소 확인 O(1)
3. 제일 상단이 아닌 나머지 원소들의 확인 / 변경이 원칙적으로 불가능
   • 구현 시 배열 기반으로 구현

구현

• 배열(더 쉬움)
• 연결리스트

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

원소를 담은 큰 배열 1 개, 인덱스 저장할 변수 1개
{13, 21, 30}이 담겨있는 스택 나타내기
-> dat[0], dat[1], dat[2]에 각각 13, 21, 30, pos = 3
=> 스택의 값들은 dat의 0번지부터 저장,
pos는 다음에 원소가 추가될 때 삽입해야 하는 곳 가리킴 -> pos의 값 = 스택의 길이(스택 내의 원소의 수)

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

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

void push(int x) {
	// pos가 가리키는 자리에 12 추가, pos 1증가
	dat[pos++] = x;
}

void pop() {
	// pos 1 줄이기
	pos--;
}

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

void test() {

}

int main(void) {
	test();
}

---

STL stack

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

 

---