공hannah부
선형 자료 구조 (배열, 연결 리스트, 스택, 큐, 덱) 본문
선형 자료 구조
- 선형 자료구조: 하나의 데이터 뒤에 하나의 데이터만 올 수 있는 데이터 구조 ex) 배열 등
- 비선형 자료구조: 하나의 데이터 뒤에 여러 데이터가 올 수 있는 데이터 구조 ex) 트리, 그래프 등
배열
- 자료가 물리적으로 연속되어 저장되는 자료구조
- 시간복잡도
- 임의 위치 접근: O(1)
- 원소 삽입/삭제: O(N)
- std::vector, std::array
연결 리스트
- 자료가 논리적으로 연속되어 저장되는 자료구조 (메모리상에서 연속하지 않는다)
- 시간 복잡도
- 임의 위치 접근: O(N)
- 원소 삽입/삭제: O(1)
- std::list
- 각 자료를 노드라고 한다. 노드는 데이터와 자신과 인접한 노드의 주소를 저장한다.
- Singly Linked List: 다음 노드의 주소 또는 이전 노드의 주소만을 저장
- Doubly Linked List: 다음 노드와 이전 노드의 주소를 모두 저장
- 연결 리스트는 가장 처음 또는 끝 노드를 저장
스택
- Last In First Out (LIFO) 자료구조
- 나중에 들어온 자료가 먼저 나간다
- 할 수 있는 연산
- push(x): x를 스택에 넣는다
- pop(): 스택에서 가장 마지막에 추가된 원소를 뺀다
- std::stack
- STL
- #include<stack>
- std::stack<T>
- void push(T a);
- T pop();
- void pop();
- bool empty();
- unsigned int size();
#include<bits/stdc++.h>
using namespace std;
int main() {
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty()) {
cout << st.top() << " "; //4 3 2 1
st.pop();
}
}
큐
- First In First Out (FIFO) 자료구조
- 먼저 들어온 자료가 먼저 나간다
- 할 수 있는 연산
- push(x): x를 큐에 넣는다
- pop(): 큐에서 가장 먼저 들어온 원소를 뺀다
- std::queue
- STL
- #include<queue>
- std::queue<T>
- void push<T a>
- T front();
- void pop();
- bool empty();
- unsigned int size();
#include<bits/stdc++.h>
using namespace std;
int main() {
queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(3);
Q.push(4);
while (!Q.empty()) {
cout << Q.front() << " "; //1 2 3 4
Q.pop();
}
}
덱
- FIFO, LIFO 모두 지원하는 자료구조 (스텍+큐)
- 할 수 있는 연산
- push_back(x): 덱의 가장 뒤에 x를 넣는다
- push_front(x): 덱의 가장 앞에 x를 넣는다
- pop_back(): 덱의 가장 뒤 원소를 제거한다
- pop_front(): 덱의 가장 앞 원소를 제거한다
- std::deque
- STL
- #include<deque>
- std::deque<T>
- void push_front(T a);
- void push_back(T a);
- T front();
- T back();
- void pop_front();
- void pop_back();
- bool empty();
- unsigned int size();
- T at(unsigned int pos);
#include<bits/stdc++.h>
using namespace std;
int main() {
deque<int> deq;
deq.push_back(1); //1
deq.push_front(2); //21
deq.push_front(3); //321
deq.push_back(4); //3214
deque<int> deq2 = deq; //복제
while (!deq.empty()) {
cout << deq.front() << " "; //3 2 1 4
deq.pop_front();
}
while (!deq2.empty()) {
cout << deq2.back() << " "; //4 1 2 3
deq2.pop_back();
}
}
'공부 > 알고리즘' 카테고리의 다른 글
거듭제곱 (0) | 2023.08.03 |
---|---|
최대공약수(gcd)와 최소공배수(lcm) / 유클리드 호제법 (0) | 2023.08.03 |
비교 함수 / STL sort (0) | 2023.07.31 |
정렬 (버블정렬, 삽입정렬, 퀵정렬, 병합정렬) (0) | 2023.07.31 |
C++기초, C++ STL (0) | 2023.07.25 |