선형 자료 구조 (배열, 연결 리스트, 스택, 큐, 덱)

선형 자료 구조

• 선형 자료구조: 하나의 데이터 뒤에 하나의 데이터만 올 수 있는 데이터 구조 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();
	}
}