스택

  • 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 (LIFO)
  • push, pop, empty, top

  • 일차원 배열 하나로 구현 가능

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int stack[10000];
    int size = 0;

    void push(int data){
        stack[size] = data;
        size += 1;
    }

    void pop(){
        stack[size - 1] = 0;
        size -= 1;
    }

  • 구현된 라이브러리 사용

    • C++: std::stack
    • Java: Stack

응용문제

  • 단어 뒤집기 (9093)
  • 괄호 (9012)
  • 스택 수열 (1874)
  • 에디터 (1406) (링크드 리스트로 풀이 가능)
  • 단어 뒤집기2 (17413)
  • 쇠막대기 (10799)

** c++ 입력 관련 정리

  • getline() : 띄어쓰기/공백을 포함한 문자열을 입력 받을 수 있음

    1
    2
    string str;
    getline(cin, str);

  • cin.ignore() : cin >> n으로 정수를 입력받고 바로 getline(cin, str)로 문자열을 입력받고자 할 경우 정수값을 입력한 뒤 누른 엔터가 버퍼에 남아있다가 str에 저장된다. 이럴 때 cin.ignore()로 입력 버퍼의 내용을 제거시켜주면 된다.

    1
    2
    3
    4
    5
    6
    int n;
    string str;
    cin >> n;
    //cin은 띄어쓰기, 엔터, 탭을 기준으로 입력값을 나누고, 이런 문자들이 나오면 무시하기 때문에 버퍼에 그대로 남아있다. 하지만 getline()의 경우 delim을 지정해주지 않으면 엔터('\n')를 기준으로 입력을 받아들인다.
    cin.ignore();
    getline(cin, str);

  • cin.get() : char 하나 입력 받을 수 있음

    1
    2
    char str[256];
    cin.get(str, 256);

  • cin >> str : cin으로 string도 입력받을 수 있음 (띄어쓰기 전까지 입력받음)

    1
    2
    string str;
    cin >> str;

    (cout << str 처럼 cout으로 string을 출력할 수는 없음)

    1
    2
    3
    for(char c : str){
      cout << c;
    }

  • 문자열은 크게 2가지 형태로 입력가능. C에서와 같이 char str[] 형태로 받는 방법과 헤더파일의 string 클래스를 이용하는 방법. 주의, strlen 함수는 O(n), size 함수는 O(1)이다.