[자료구조] [c++/STL] 스택, 큐, 덱

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를 반환