[CS] 자료구조 Stack(스택)과 Queue(큐)에 대해 알아보자

🍓 Stack(스택)과 Queue(큐)

: Stack과 Queue는 자료구조로서 사용되는 개념입니다.

 

Stack이란?

LIFO(Last In First Out)정책을 사용하는 자료구조로서 데이터를 차곡차곡 쌓아 올린 형태입니다.

가장 마지막에 삽인된 자료가 가장 먼저 삭제되는 구조를 가지고 있습니다.

 

• 데이터를 삽입할때의 연산을 push, 데이터를 뺄 때의 연산을 pop 이라 일컫습니다.
• 후입 선출의 구조라고도 말합니다.
• 스택의 삽입,삭제 시간 복잡도는 O(1)입니다.
• 장점으로는 top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠릅니다.
• 단점으로는 top 이외의 위치의 데이터에 접근하기 위해서는 그 중간의 데이터들을 거쳐가야 합니다.

Stack의 사용 사례

• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

Queue란?

FIFO(First In First Out)정책을 사용하는 자료구조로서 먼저 들어간 데이터가 먼저 나오는 형태를 가집니다.

선입 선출의 구조라고도 말합니다.

 

• 데이터를 삽입할 때에는 enqueue(인큐), 데이터를 뺄 때는 dequeue(디큐)라고 일컫습니다.
• 삭제 연산이 수행되는 곳을 front(프론트), 삽입 연산이 이루어지는 곳을 rear(리어)라고 합니다.
• 큐의 모형에는 위의 이미지처럼 선형큐와 원형큐 모형이 있습니다.
• 스택과 마찬가지로 시간 복잡도는 O(1)입니다.
• 장점과 단점 역시 스택과 동일합니다.

Queue의 사용 사례

• 은행 업무
• 대기열 순서와 같은 우선순위의 작업 예약
• 프로세스 관리
• 서비스 센터의 대기시간

 

 

references

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

[자료구조] 스택 Stack, 큐 Queue, 덱 Deque

https://chifuyu.tistory.com/8

JavaScript - 자료구조 (큐, 스택)