1. Stack
Stack은 Last In First Out. 맨 아래에 있는 데이터를 꺼내기 위해서는 제일 위의 데이터들을 꺼내야 한다는 것. 탑을 쌓는 듯한 구조로 되어있다. 삽입과 삭제 연산의 시간복잡도는 O(1).
연산은 push,pop,size,empty,top이 있다.
push = 원소 넣기
pop = 원소 빼기
size = 스택의 사이즈
empty = 스택이 비어있는가?
top = 가장 위에 위치하는 원소
어제 stack을 이용해서 푼 문제
3 9 6 5 1 <- 이런 배열이 있다고 생각해보자
배열을 2개로 나눈다. 서브 배열들은 연속되어 있어야한다. (3/9651 혹은 39/651 이렇게) 그리고 그 서브 배열들의 값을 각각 더했을 때 서로 같아야한다. 어떻게 나누면 될까?
위의 예시에서 정답이 되려면 39/651 로 나누어야 한다
3+9 = 12 / 6+5+1 =12 가 되니까
for(int i=0;i<5;i++){
int num=arr[i];
st.push(num);
sumA+=num;
for(int k=i+1;k<5;k++){
sumB+=arr[k];
}
if(sumA==sumB){
여기서 해야하는 일
}
}
이런식으로 했었다.
2.Queue
Queue는 FIFO 구조. 먼저 들어간 것이 먼저 나온다.
삽입과 연산의 시간복잡도는 O(1), 다른 값들의 이동이 필요하지 않기 때문이다.
Queue의 기능 push,size,empty,front,pop
push = 원소 넣기
size = Queue 크기
empty = Queue가 비었는가?
front = 제일 앞에 있는 값 리턴
pop = 제일 앞에 있는 원소 빼기
원형 순열으로 쓰는 법
queue<int> q;
while(돌리고 싶은 만큼){
// 앞의 원소를 뒤에다가 넣고
q.push(q.front());
// 앞의 원소를 제거해주기
q.pop();
}3. Deque
스택과 큐의 특성을 합친 자료구조. 앞/뒤에서 삽입 삭제가 모두 가능. 시간 복잡도 O(1)
Deque의 기능 push_front, push_back, pop_front,pop_back,size,empty,front,back,
push_front = 앞으로 넣기
push_back = 뒤로 넣기
pop_front = 앞의 원소 제거
pop_back = 뒤의 원소 제거
size = 사이즈 리턴
front = 맨 앞의 값
back = 맨 뒤의 값
