Today I learned : 바킹독 스택, 큐
바킹독의 실전 알고리즘 : 스택
스택은 LIFO.
정의와 성질
스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다.
스택의 성질
- 원소의 추가 O(1)
- 원소의 제거 O(1)
- 제일 상단의 원소 확인 O(1)
- 나머지 원소들의 확인/변경 원칙적으로 불가능
기능과 구현
const int MX=1000005;
int dat[MX];
int pos=0;
일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다.
#include <bits/stdc++.h>
using namespace std;
const int MX=1000005;
int dat[MX];
int pos=0;
void push(int x){
dat[pos]=x;
pos++; //dat[pos++]=x;로 한 줄로 표현도 가능, 전치 후치 차이에 대해 알고 있기
}
void pop(){
pos--; //여기까지만 써도 됨
/* 어차피 아래 코드들은 나중에 push할 때 덮어쓸 공간
cout<<dat[pos];
dat[pos]=0; */
}
void top(){
return dat[pos-1];
}
void test(){
}
int main(void){
test();
}
음 연결 리스트 하다가 얘 하니까 구현은 쉽다. 그래도 바킹독 강의에서는 STL을 권장한다. STL stack을 썼으면 최소 스택 쪽에는 문제 없다는 걸 알 수 있으니 로직 개선에 신경 쓸 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
stack<int> s;
s.push(10);
s.push(20);
cout<<s.size()<<'\n'; // 2
s.empty(); // bool
s.pop(); //10만 남을 것
}
바킹독의 실전 알고리즘 : 큐
큐는 FIFO.
정의와 성질
큐는 FIFO 바로 나와주면 된다.
큐의 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞/뒤 원소 확인이 O(1)
- 앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능
추가 -rear 제거 -front 로 보통 나타낸다.
기능과 구현
스택 어렵지 않았으니까 걍 내가 구현해보자.
const int MX = 100005;
int dat[MX];
int tail=0; // 추가
int head=0; // 제거
void push(int x){
dat[tail++]=x;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
제미나이한테 던졌더니 길이 제한 생각 안 하냐고 혼났다. 그치 대기큐 같은 병목 현상도 있지. 바킹독에서는 이를 다루고 있진 않다. 혹시 필요하다면 % 연산 기호로 원형 큐를 만들 수 있을 거 같다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
queue<int> q;
q.push(10);
q.push(20);
cout<<q.size()<<'\n';
q.empty();
q.pop();
q.front();
q.back();
}
나왔던 오류
연산자 관련
풀다가 연산자 우선순위 관련한 오류가 하나 나왔다.
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(void){
int n;
cin>>n;
while(n--){
string inst;
cin>>inst;
if(inst=="push"){
int nor;
cin>>nor;
q.push(nor);
}
else if(inst=="front") cout<< (q.size()==0) ? -1 : q.front()<<'\n';
else if(inst=="back") cout<< (q.size()==0) ? -1 : q.back() << '\n';
else if(inst=="size") cout<<q.size()<<'\n';
else if(inst=="empty") cout<<q.empty()<<'\n';
else if(inst=="pop") {
cout<< (q.size()==0) ? -1 : q.front()<<'\n';
if(q.size()!=0) q.pop();
}
}
}
/*
❌ Test Case #1: Failed
--------------- Expected ---------------
1
2
2
0
1
2
-1
0
1
-1
0
3
---------------- Actual ----------------
002
0
0010
1
10
0
--------------- 채점 종료 ----------------
*/
자꾸 이런 오류가 뜨길래 제미나이한테 넘겼더니 연산 우선순위 때문이라고 한다.
// 작성하신 코드
cout << (q.size()==0) ? -1 : q.front() << '\n';
// 컴퓨터의 해석 (괄호 위치 주목!)
( cout << (q.size()==0) ) ? -1 : ( q.front() << '\n' );
위와 같이 삼항 연산자보다 출력 연산자가 우선순위가 높다고 한다.
2^31-1
위 키워드 보면 int 최댓값임을 바로 파악해야 한다.