[Data Structure] Stack and Queue

스택(Stack)

특징

• 입력과 출력이 한 곳(방향)으로 제한적임
• LIFO(Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴
• 예시 : 함수의 콜스택, 연산자 후위표기, 문자열 역순, DFS

장점 및 활용

• 재귀함수를 필요로하는 소스코드에 재귀함수를 사용하지 않고 구현 가능
• 웹 브라우저의 방문기록에서 스택의 트깅을 활용해 '뒤로가기'를 구현할 수 있음
• 프로그램의 실행취소(Undo)에 활용됨

큐(Queue)

• 입력과 출력을 한 쪽 끝(front,rear)로 제한
• 큐의 가장 첫 원소를 front , 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
• FIFO(First In First Out, 선입선출) : 가장 먼저 들어온 것이 가장 먼저 나옴
• 예시 : 버퍼, 막 입력된 것을 처리하지 못하고 있을 때, BFS

장점 및 활용

• 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에서 사용
• 은행 업무
• 콜센터 고객 대기시간
• 우선순위가 같은 작업 예약(ex. 프린터의 인쇄 대기열)
• 콜센터 고객 대기시간
• 프로세스 관리
• 캐시 구현