1. 스택
스택의 개념
후입 선출(LIFO,Last In First Out)방식으로 가장 최근에 들어온 데이터가 가장 먼저 나간다.
스택의 연산
- push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.
- pop() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.
- isEmpty()
- peek() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.
- isFull()
- size()
스택의 사용 사례
함수호출, Undo기능, 괄호검사, 계산기, 미로탐색
c++ STL stack 기본 사용법
헤더 : <stack>
선언 : stack <데이터 타입> 변수명 ex) stack <int> st;
추가 및 삭제
-st.push(element) :top에 원소를 추가
-st.pop():top에 있는 원소를 삭제
조회
-st.top() : top에 있는 원소를 반환
기타
-st.empty():스택이 비어있으면 true 아니면 false를 반환
-st.size():스택 사이즈를 반환
-st.swap(st): stack st와 요소 바꾸기
2. 큐
큐의 개념
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(Fist InFirst Out)방식이다.
큐의 연산
- enqueue(e) : e를 큐의 맨 뒤에 추가한다.
- dequeue() : 맨 앞 요소를 삭제하고 반환한다.
- isEmpty()
- peek() : 맨 앞 요소를 삭제하지 않고 반환한다.
- isFull()
- size()
- front : 큐의 맨 앞의 위치(인덱스)
- rear : 큐의 맨 뒤의 위치(인덱스)
큐의 사용 사례
BFS(너비 우선 탐색), 캐시구현, 우선순위가 같은 작업 예약(인쇄 대기열), 선입선출이 필요한 대기열, 프로세스 관리, 프린터의 출력 처리
c++ STL queue 기본 사용법
헤더 : <queue>
선언 : queue <데이터 타입> 변수명 : ex) queue<int> q;
추가 및 삭제
-q.push(element) :top에 원소를 추가
-q.pop():top에 있는 원소를 삭제
반환
-q.front() : 최상위 원소를 반환
-q.back() : 마지막 원소를 반환
기타
-q.empty():스택이 비어있으면 true 아니면 false를 반환
-q.size():스택 사이즈를 반환
3. 덱
덱의 개념
Deque(Double Ended Queue)의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.
덱의 연산
- addFront(e)
- deleteFront()
- addRear()
- deleteRear()
- isEmpty()
- getFront()
- getRear()
- isFull()
덱의 사용사례
앞과 뒤에서 삽입,삭제가 자주 일어나는 경우
데이터의 개수가 가변적일 경우
데이터 검색을 거의 하지 않을 경우(랜덤 요소에 접근해야할 때)
deque vs vector
deque | vector | |
크기 변경 가능 | 0 | 0 |
앞에 삽입, 삭제 용이 | 0 | x |
뒤에 삽입, 삭제 용이 | 0 | 0 |
순차 접근 가능 | 0 | 0 |
랜덤 접근 가능 | 0 | x |
deque는 앞과 뒤에서 삽입 삭제 성능이 vector보다 좋지만 그 외 기능은 vector보다 성능이 좋지 못하다.
또한 vector와 다른 점은 원소가 메모리 블록에 연속하게 저장되지만 하나의 메모리 블록이 아닌 여러 메모리 블록에 나뉘어 저장된다는 것이다.
c++ STL deque 기본 사용법
헤더 : <deque>
선언 : deque <데이터 타입> 변수명 : ex) deque<int> dq;
deque dq(10) : default 값으로 초기화된 10개의 원소를 가진 dq를 생성
deque dq(10,4) : 4의 값으로 초기화 된 10개의 원소를 가진 dq를 생성
-dq.assign(element)
-dq.at(idx)
-dq[idx]
-dq.front()
-dq.back()
-dq.clear()
-dq.push_front(x)
-dq.pop_front()
-dq.push_back(x)
-dq.pop_back()
-dq.begin()
-dq.end()
-dq.swap(dq1)
-dq.insert(1,2,3) : 1번째 위치에 2개의 3값을 삽입
-dq.insert(3,4) : 3번째 위치에 4의 값을 삽입, iterator 반환
-dq.erase(iter) : iter가 가리키는 원소를 제거,iterator를 반환
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] DFS와 BFS (0) | 2021.02.24 |
---|---|
[자료구조] 그래프 (0) | 2021.02.24 |
[자료구조] 동적 계획 (DP : Dynamic Programming) (0) | 2021.02.12 |
[c++ / STL] sort, priority queue (0) | 2021.01.30 |
[자료구조] 정렬 , 우선순위 큐(힙정렬) (0) | 2021.01.30 |