[C++/코테] 스택(Stack) 기초

스택 Stack

• FILO 자료구조. 먼저 넣은 것이 가장 나중에 나온다. 프링글스 통처럼!
• 수식의 괄호 쌍, 전위/중위/후위 표기법(코테 X), DFS, Flood Fill 등에 활용된다.

스택의 성질

1. 원소의 추가와 제거는 O(1)
2. 제일 상단의 원소 확인이 O(1)
3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.
   STL에서도 기능이 없지만, 배열을 이용해서 구현하면 가능하도록 만들 수는 있다.

스택의 구현

배열 또는 연결 리스트를 사용하여 구현할 수 있다.

배열로 구현 시, 

• 원소를 담을 큰 배열 1개, 인덱스 저장 배열 1개 필요
• data[0]부터 저장
• pos: 다음 원소 삽입 위치. 즉 스택의 길이(원소의 수)

push함수

• pos가 가리키는 위치에 원소를 삽입한다.
• pos를 1 증가시킨다.

void push(int x){
   dat[pos++] = x;		// 연산을 하고 -> pos +1
}

pop 함수

• pos를 1 감소시킨다.
  굳이 값을 변경(삭제)하는 연산을 수행하지 않아도 된다.

void pop(){
    pos--;
}

top 함수

• pos 바로 밑(직전) 원소 출력

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

STL Stack

• 주로 push, pop, top, empty, size 멤버 함수를 쓴다.
• 스택이 비어있을 때 pop이나 top을 호출하면 런타임 에러가 발생한다.

연습문제: 백준 10828 스택

* python으로 풀었습니다.

2023.11.08 - [Algorithm] - [Python/코테] 백준 10828 스택

[Python/코테] 백준 10828 스택

---

출처:

https://www.youtube.com/watch?v=0DsyCXIN7Wg