Stack

특징

• 책을 쌓듯이 데이터를 차곡차곡 쌓아 올린 형태의 자료구조
• 선형 구조
• 같은 구조의 데이터를 정해진 방향으로만 쌓을 수 있다.
• 후입선출(LIFO) 구조: 마지막에 삽입된 데이터를 가장 먼저 꺼낸다.
• 데이터가 없을 때 pop하는 오류를 stack-underflow, 스택의 크기 이상의 데이터를 push하려는 오류를 stack-overflow라고 한다. (!)
  
  

주요 연산

• push: top을 위로 한 칸 올리고, top이 가리키는 위치에 데이터 저장(삽입)한다.
• pop: top이 가리키는 데이터를 반환하고, top을 아래로 한 칸 내린다(삭제).
• peek: 스택의 top에 있는 item을 반환한다. pop과 달리 stack에서 객체를 꺼내지 않는다.
  
  

활용

• 브라우저의 방문 기록(뒤로 가기): 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소(undo): 가장 나중에 실행된 것부터 취소한다.
• 수식의 괄호 검사(연산자 우선순위를 위한 괄호 검사)
• 함수의 콜스택: 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 LIFO 구조다. 함수 호출이 발생하면 함수 수행에 필요한 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.
• 깊이 우선 탐색(DFS)
  
  

Stack과 Queue

• 공통점: Stack과 Queue 모두 Peek을 사용할 수 있다.
  • Peek 연산은 자료구조의 변화를 주지 않고, pop이나 dequeue를 할 때 리턴되는 item을 리턴할 수 있다.
• 차이점: 아이템을 삭제할 때 가장 큰 차이점이 있다.
  • Stack은 가장 마지막에 추가된 item을 삭제하고, Queue는 가장 처음 들어와 있던 item을 삭제한다.
    
    

참고

• https://devuna.tistory.com/22