[2022 겨울학기] 8주차 - 자료구조(스택, 큐)

1. 자료구조란?

자료를 효율적으로 표현하고 저장, 처리할 수 있도록 정리하는 것

삽입, 삭제, 탐색 세 가지 연산을 빨리 하기 위해 각 상황에 맞는 다양하고 효율적인 자료구조들이 많이 개발되었다.

 

-스택

후입선출 구조로 마지막 삽입한 원소는 맨 위에 있고, 제일 먼저 삭제된다

웹 브라우저 방문기록(뒤로가기)

역순 문자열 만들기

실행 취소(undo)

후위 표기법 계산

수식의 괄호 검사(연산자 우선 순위 표현을 위한 괄호 검사)

 

-큐

선입선출 구조로 뒤에서만 원소를 삽입하고 앞에서만 원소를 삭제할 수 있다

우선순위가 같은 작업 예약(프린터의 인쇄 대기열)

프로세스 관리

너비우선탐색

캐시 구현

 

-덱

큐의 양쪽 끝에서 삽입과 삭제 연산을 둘 다 수행할 수 있는 자료 구조

 

 

2. 동작 원리

-스택

push(삽입할 값): 스택의 가장 위에 새로운 값을 삽입하는 연산

pop( ): 스택의 top값을 삭제하는 연산

top( ): 스택에서 top값을 반환해주는 연산, 빈 스택이라면 오류 발생한다

size( ): 스택에 들어있는 원소의 개수를 반환

empty( ): 스택이 비어있는지 확인하는 연산, 비어있으면 true 비어있지 않으면 false

 

-큐

push(삽입할 값): 큐의 rear에 값을 삽입하는 연산

pop( ): 큐의 front값을 삭제하는 연산

front( ): 큐의 front값을 반환하는 연산

back( ): 큐의 rear값을 반환하는 연산

size( ): 큐에 들어있는 원소의 개수를 반환

empty( ): 큐가 비어있는지 확인하는 연산, 비어있으면 true 비어있지 않으면 false

 

-덱

push_front(삽입할 값): 큐의 front에 값을 삽입하는 연산

push_back(삽입할 값): 큐의 rear에 값을 삽입하는 연산

pop_front( ): 큐의 front에 값을 삭제하는 연산

pop_back( ): 큐의 rear에 값을 삭제하는 연산

front( ): 큐의 front값을 반환하는 연산

back( ): 큐의 rear값을 반환하는 연산

size( ): 덱에 들어있는 원소의 개수를 반환

empty( ): 덱이 비어있는지 확인하는 연산, 비어있으면 true 비어있지 않으면 false

 

 

3. 코드

stack<int> s;
queue<int> q;
deque<int> dq;

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!