[알고리즘 스터디] 스택 (Stack) 큐 (Queue)

스택(Stack), LIFO(Last In First Out)

쌓아 올리다

 

Top을 통해 삽입하는 연산 'push'

Top을 통한 삭제하는 연산 'pop'

-> 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다. 

 

활용 예시

• 웹브라우저 방문기록 (뒤로가기): 가장 나중에 열린 페이지부터 다시 보여준다
• 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소(undo): 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

필요한 연산 

• S.push(e): Top 에 새로운 요소 추가 
• S.pop(): Top에 요소를 반환하면서 제거 
• S.top(): Top에 요소를 제거하지 않고 반환
• S.is_empty(): 스택이 비어있으면 True를 반환

 

큐(Queue), (FIFO, First In First Out)

줄 서서 기다리는 것

한쪽 끝에서 삽입 다른 쪽 끝에선 삭제 작업

삭제 연산 수행 되는 곳 : 프론트 (Front), 삭제 연산을 deQueue

삽입 연산 수행 되는 곳: 리어 (Rear), 삽입 연산을 enQueue

 

활용 예시

• 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황 
• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열) : 가장 먼저 대기열에 오른 프린터가 먼저 출력됨
• 은행 업무 : 빠른 번호표를 가진 사람이 먼저 업무를 봄
• 콜센터 고객 대기시간
• 프로세스 관리 
• 너비 우선 탐색 (BFS, Breadth-FIrst Search) 구현
• 캐시 (Cache) 구현

 

 

참조:

https://velog.io/@awesomeo184/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D