스택(stack) 과 큐(queue)

• 스택(Stack)의 개념
  • 한 쪽으로만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
  • 메모리의 스택영역은 함수의 호출과 관계되는 지역변수외 매개변수가 저장되는 영역
  • 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸.
  • 컴퓨터의 시간지역성(최근에 참조된 자료가 다시 참조될 확률이 높다는 원리)을 활용할 수 있는 추상적 자료구조
• 스택(Stack)의 연산
  
  • pop: 스택에서 가장 마지막에 입력된 항목을 활용하고 제거한다.
  • push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
  • peek(top): 스택의 가장 위에 있는 항목을 활용한다(삭제 ㄴㄴ).
  • empty(): 스택이 비어 있을 때에 true를 반환한다.
  • full :  스택이 다 차있으면 true반환
  • size : 스택의 크기를 리턴 (O(n)시간복잡도)
• 스택(Stack)의 사용 사례
  
  • 재귀 알고리즘
    • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
    • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
    • 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
    • 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
  • 웹 브라우저 방문기록 (뒤로가기)
  • 실행 취소 (undo)
  • 역순 문자열 만들기
  • 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
    • Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
  • 후위 표기법 계산

 

 

• 큐(Queue)의 개념
  • 데이터의 입력과 출력이 다른 자료구조.
  • 먼저 집어 넣은 데이터가 먼저 나오는 선입선출, FIFO(First In First Out)구조로 저장하는 형식
• 큐(Queue)의 연산
  
  • add(item): item을 리스트의 끝부분에 추가한다.
  • delete: 리스트의 첫 번째 항목을 제거한다.
  • front : queue의 맨 앞을 가리킴 데이터를 꺼낼 수 있는 위치.
  • rear : queue의 맨 뒤를 가리킴, 데이터를 넣을 수 있는 위치.
• 큐(Queue)의 사용 사례
  
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현
    • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
    • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
    • 노드를 접근한 순서대로 처리할 수 있다.
  • 캐시(Cache) 구현
  • 우선순위가 같은 작업 예약 (인쇄 대기열)
  • 선입선출이 필요한 대기열 (티켓 카운터)
  • 콜센터 고객 대기시간
  • 프린터의 출력 처리
  • 윈도우 시스템의 메시지 처리기
  • 프로세스 관리