스택 (Stack)
데이터의 삽입, 삭제가 한 쪽 끝에서 일어난다.
- 재귀호출, 후위표현의 연산, 깊이우선탐색
- 후입선출 구조, LIFO (Last-In-First-Out) 이다.
- top 으로 정한 곳을 통해서만 접근할 수 있다. 따라서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
- push : top 을 통해 삽입하는 연산
- pop : top 을 통해 삭제하는 연산
Stack 활용 예시
- 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여주기
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
- 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행 취소
- 후위 표기법 계산
- 수식의 괄호 검사 : 연산자 우선 순위 표현을 위한 괄호 검사
자료 삭제 알고리즘
- 오버플로우 : 스택 공간이 가득 찼을 때, 하나의 데이터를 더 넣으려는 경우 발생
- 언더플로우 : 스택 공간에 데이터가 없을 때, 데이터를 꺼내려고 하는 경우 발생
큐 (Queue)
데이터의 삽입, 삭제가 양방향에서 일어남
- 선택정렬 : 가장 작은 값을 위치가 정렬되어있지 않은 최초의 값과 바꿈
- 선입선출, FIFO (First-In-First-Out) 방식의 자료 구조이다.
- 한 쪽 끝에서 삽입, 다른 쪽 끝에서 삭제 작업이 양 쪽으로 이루어진다. 따라서 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제된다.
- 리어(rear) : 삽입 연산(인큐, enQueue)만 수행되는 곳
- 프론트(front) : 삭제 연산(디큐, dnQueue)만 수행되는 곳
Queue 활용 예시
주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있을 때 이용
- 우선 순위가 같은 작업 예약 : 프린터의 인쇄 대기열
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 캐시(Cache) 구현
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
📍 Stack, Queue 의 java 코드와 실행 결과
실행 결과
슬기로운 개발 생활