![#3 코테준비 - 스택(Stack)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJcx1u%2FbtrMPVEcHR3%2FphzBvsFVuUdeRFxmIjKOUK%2Fimg.png)
스택(Stack)
- 끝에서만 원소를 넣거나 빼는 자료구조
- 먼저들어간 원소가 나중에 나옴
(FILO : First In Last Out / 프링글스 통을 생각하면 편함)
- 최상단(top) 원소의 추가/제거/확인의 시간복잡도는 O(1)
- 다른 원소의 확인/변경은 불가능함.
STL - Stack
#include <iostream>
#include<stack>
using namespace std;
int main(void) {
stack<int> myStack;
//스택에 원소 1을 삽입
myStack.push(1);
//스택에 원소가 있다면 최상단의 원소를 출력
if (!myStack.empty()) cout << "최상단 원소: " << myStack.top() << endl;
else cout << "원소 없음!"<<endl;
//스택의 사이즈 출력
cout << "스택의 사이즈 : " << myStack.size() << endl;
//최상단 원소 삭제
myStack.pop();
//스택에 원소가 있다면 최상단의 원소를 출력
if (!myStack.empty()) cout << "최상단 원소: " << myStack.top() << endl;
else cout << "원소 없음!" << endl;
//스택의 사이즈 출력
cout << "스택의 사이즈 : " << myStack.size() << endl;
}
리스트,벡터와 다르게 쓰이는 함수가 몇개 없어서 정리 해봤다.
더 자세한 부분은 아래의 사이트에서 참고하시면 좋다.
https://cplusplus.com/reference/stack/stack/?kw=stack
https://cplusplus.com/reference/stack/stack/?kw=stack
container_typeThe second template parameter (Container)Type of the underlying container
cplusplus.com
문제 풀어보기
백준 10828번 - 10828번: 스택 (acmicpc.net)
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
그냥 직접 명령어를 입력해서 stack의 기능을 구현하는 간단한 문제다.
#include <iostream>
#include<stack>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n = 0;
cin >> n;
stack<int> myStack;
while (n--)
{
string s;
cin >> s;
if (s == "push")
{
int m;
cin >> m;
myStack.push(m);
}
else if (s == "pop")
{
if (myStack.empty()) cout << -1 << '\n';
else {
cout << myStack.top() << '\n';
myStack.pop();
}
}
else if (s == "size")
{
cout << myStack.size() << '\n';
}
else if (s == "empty")
{
if (myStack.empty()) cout << 1 << '\n';
else cout << 0 << '\n';
}
else
{
if (myStack.empty()) cout << -1 << '\n';
else cout << myStack.top() << '\n';
}
}
}
직접 스택을 구현해서 하셔도 되고 STL의 스택을 이용해서 풀어도 된다.
STL의 스택은 원소가 하나도 없을때 pop,top 함수를 사용하면 런타임 에러를 내니 조건에 맞게 함수들을 써서 구현하면 된다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#5 코테준비 - 덱(Deque) (0) | 2022.09.23 |
---|---|
#4 코테준비 - 큐(Queue) (0) | 2022.09.23 |
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
#1 코테 준비 - 배열 (0) | 2022.09.21 |
코테 준비하기 - 기본 사항들 (2) | 2022.09.21 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!