✅ 스택(Stack)이란?
데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 조금 더 설명하자면, 위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있습니다.
ex) 책상에 책을 쌓아두는 것 포개둔 종이 컵을 꺼내서 사용하는 것
top : 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있습니다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능합니다.
push : 스택에서의 삽입 연산
pop : 스택에서의 삭제 연산
이러한 스택의 구조를 ”후입 선출” 의 구조라고 하며, 줄여서 LIFO(Last In First Out)라고 부릅니다.
스택(Stack)의 사용 사례
- 웹 브라우저 방문기록 (뒤로 가기)
- 실행 취소(undo)
- 역순 문자열 만들기
- 후위 표기법 계산 (11+,22+,33+)
스택(Stack)의 기본 동작
“Push”작업
1단계 - 스택이 가득찼는지 확인
2단계 - 스택이 가득차면 오류가 발생하고 종료
3단계 - 스택이 가득차지 않으면 Top를 증가시킴
4단계 -Top이 가리키는 스택위치에 데이터를 추가
“Pop”작업
1단계 - 스택이 비어있는 지 확인
2단계 - 스택이 빙있으면 오류가 발생하고 종료
3단계 - 스택이 비어있지 않으면 Top가 가리키는 데이터 제거
4단계 - Top 값을 감소시킴
5단계 - 성공을 반환
스택(Stack)의 구현 방법
- 배열사용
장점: 구현이 쉬움
단점: 크기가 동적이 아님. 런타임시 필요에 따라 늘어나거나 줄어들지 않음 - 연결리스트 사용
장점: 크기가 동적이 아님. 런타임시 필요에 따라 크기가 확장 및 축소 될 수 있음
단점: 포인터를 위한 메모리 공간이 필요함
✅ 큐(Queue)의 개념은?
큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로, FIFO(First In First Out)의 구조를 가지고 있습니다.
프론트(front) : 삭제 연산이 수행되는 곳
리어(rear) : 삽입 연산이 이루어지는 곳
FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있습니다.
인큐(Enqueue) : 리어(rear)에서 이루어지는 삽입 연산
디큐(Dequeue) : 프론트(Front)에서 이루어지는 삭제 연산
큐(Queue)의 사용 사례
- 은행 업무
- 대기열 순서와 같은 우선순위의 작업 예약 등
- 서비스 센터의 대기시간
- 프로세스 관리
