[알고리즘] 자료구조 (스택, 큐, 덱, 문자열)

[알고리즘] 자료구조 (스택, 큐, 덱, 문자열)

스택 (Stack)

---

• 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

• 마지막에 넣은 것이 가장 먼저 나오는 LIFO 구조

• push : 스택에 자료 넣음

• pop : 스택에서 자료 뺌

• top : 스택의 가장 위에 있는 자료

• empty : 스택이 비어있는지 아닌지 확인

• size : 스택에 저장된 자료의 개수 확인

사용방법

• C++

  STL의 stack 이용

• Java

  java.util.Stack

- push
stack[size] = v;
size += 1;
​
- pop
stack[size-1] = 0;
size -= 1;

스택 활용 문제

괄호 : https://www.acmicpc.net/problem/9012

쇠막대기 : https://www.acmicpc.net/problem/10799

에디터 : https://www.acmicpc.net/problem/1406

큐(Queue)

---

• 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조

• 먼저 넣은 것이 가장 먼저 나오기 때문에 FIFO 구조

• push : 큐에 자료 넣음

• pop : 큐에서 자료 뺌

• front : 큐의 가장 앞에 있는 자료

• back : 큐의 가장 뒤에 있는 자료

• empty : 큐가 비어있는지 아닌지 확인

• size : 큐에 저장되어있는 자료 개수 확인

사용방법

• C++

  STL의 queue 이용

• Java

  java.util.Queue

- push
queue[end] = val;
end += 1;
​
- pop
queue[begin] = 0;
begin += 1;

큐 활용 문제

조세퍼스 문제 : https://www.acmicpc.net/problem/1158

덱(Deque)

---

• 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조

• push_front : 큐에 자료를 넣음

• pop : 큐에서 자료를 뺌

• front : 큐의 가장 앞에 있는 자료

• back : 큐의 가장 뒤에 있는 자료

• empty : 큐가 비어있는지 아닌지 확인

• size : 큐에 저장되어있는 자료 개수 확인

덱 구현 문제

https://www.acmicpc.net/problem/10866

문자열

---

아스키 코드

• 문자 인코딩 방법

• 대표적 아스키 코드

  '0' = 48

  'A' = 65

  'a' = 97

• 0은 아스키 코드로 NULL을 나타냄

• 숫자가 저장되어 있는데, 출력만 글자로 해주는 것

printf("%c", 65);
printf("%c", 48);
​
>>출력결과
A0

※ strlen 사용 시 시간 복잡도 줄이는 방법

• strlen 함수의 시간 복잡도는 O(N)

for (int i=0; i<strlen(s); i++) {
}
​
>> for문 안에서 strlen 함수를 계속 돌리기 때문에 시간 복잡도 O^2
​
​
int len = strlen(s);
for (int i=0; i<len; i++){
}
​
>> 밖에서 strlen을 len에 저장하면 
   strlen 함수가 한번만 실행되므로 시간 복잡도 O(N)

문자열 활용 문제

단어 길이 재기 : https://www.acmicpc.net/problem/2743

ROT13 : https://www.acmicpc.net/problem/11655

네 수 : https://www.acmicpc.net/problem/10824