[Algorithm] 스택(Stack), 큐(Queue)

 

안녕하세요! 공대남입니다.

오늘은 stack에 대해 알아볼게요.

 

스택(Stack)이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하고
반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 됩니다.

• 웹 브라우저 뒤로가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행합니다.
• 문서작업에서 Ctrl+Z : 가장 나중에 수정한 내역부터 되돌립니다.
• 역순 문자열 만들기 : 맨 끝의 문자열부터 차례대로 만들어집니다.
• 후위 표기법 계산
• 재귀적 알고리즘

 

큐(Queue) 란?

선입선출(FIFO, First In First Out) 형식의 자료구조

정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 다르게 큐는 Rear부분에서 자료의 삽입이, Front부분에서 자료의 삭제가 이루어집니다. 

• 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봅니다.
• 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됩니다.
• 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책
• 너비 우선 탐색(BFS) 알고리즘

 

덱(Deque) 란?

Deque 는 Double - Ended Queue 의 줄임말이다!
한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던 큐와 달리 양쪽 front, rear 에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조이다.

삽입 삭제 연산은 마찬가지로 O(1) 의 시간 복잡도를 가지고, 스택/큐와 달리 index 를 통해 요소들에 탐색이 가능하므로 이 역시 O(1) 의 시간 복잡도를 가진다.

 

• 데이터의 삽입 삭제가 빠르고 앞, 뒤에서 삽입 삭제가 모두 가능하다
• 가변적 크기
• index 를 통해 임의의 원소에 바로 접근이 가능하고
• 새로운 원소 삽입 시, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
• 중간에서의 삽입 삭제가 어렵고
• 스택, 큐에 비해 비교적 구현이 어렵다.