(알고리즘) 바킹독의 실전 알고리즘 0x05강 ( 스택 )

업데이트:
1 분 소요

바킹독의 실전 알고리즘 0x05강 ( 스택 )Permalink

목차Permalink

  • 0x00 정의와 성질
  • 0x01 기능과 구현
  • 0x02 STL list
  • 0x03 연습 문제

1. 정의와 성질Permalink

  • 한쪽 끝에서만 원소를 넣거나 뺄수 있는 자료구조
  • ex) 프링글스 통, 엘리베이터
  • FILO(Fisrt In Last Out) 자료 구조
  • 스택, 큐,덱은 특정위치에 원소만 삽입,삭제가 가능 (Restricted Structure)

alt

1) 스택의 성질Permalink

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

2. 기능과 구현Permalink

#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(){

}

int main(void){
  test();
}

1

1) push 함수Permalink

alt

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

2) pop 함수Permalink

alt

void pop(){
  pos--;
}

3) top 함수Permalink

alt

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

3. STL stackPermalink

#include <bits/stdc++.h>
using naemspace 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 발생
}

4. 연습 문제Permalink

1) BOJ 10828 : 스택Permalink

BackJoon Algorithm 10828 스택 (Java)

2) BOJ 10773 : 재로Permalink

BackJoon Algorithm 제로 10773 (Java)

출처Permalink

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

댓글남기기