[면접대비] Stack, Queue와 Javascript 예제

선형 자료구조

적용 가능한 Method

• push: 리스트 제일 뒤에 추가
• pop: 리스트 제일 앞에 삭제
• shift: 리스트 제일 앞에 추가
• unshift: 리스트 제일 뒤에 삭제

Stack

바구니 안에 층층이 쌓이는 것과 같은 구조다.

가장 나중에 들어간 것이 먼저 나오고, 가장 먼저 들어간 것이 나중에 나온다.

Last In First Out(LIFO)

First In Last Out(FILO)

 

Javascript와 Stack의 구현 예제

 

Stack이 사용되는 예시

• 재귀 알고리즘
• 웹 브라우저의 뒤로가기 기능
• 실행 취소기능

Stack의 시간복잡도

• 삽입: 가장 최근에 들어온 데이터를 찾고 데이터를 추가한다. O(1)
• 삭제: 가장 최근에 들어온 데이터를 삭제한다. O(1)

Queue

줄을 서는 것과 같은 구조다.

가장 처음에 들어간 것이 가장 먼저 나온다.

First In First Out(FIFO)

Queue가 사용되는 예시

• 캐시 구현
• 프린터 출력처럼 우선순위가 같은 작업 예약
• 티켓처럼 선입선출이 필요한 대기열

Queue의 시간복잡도

• 리스트로 구현한 경우
  • 삽입: 가장 처음에 들어온 데이터를 찾고 데이터를 추가한다. 그 외의 데이터가 하나씩 뒤로 이동한다. O(n)
  • 삭제: 가장 처음에 들어온 데이터를 삭제한다. 그 외의 데이터가 하나씩 앞으로 이동한다. O(n)
• 링크드 리스트로 구현한 경우
  • 삽입: 가장 처음에 들어온 데이터를 찾고 데이터를 추가한다. 가장 앞에 있던 데이터의 노드만 새로 연결된다. O(1)
  • 삭제: 가장 처음에 들어온 데이터를 삭제한다. 앞에서 두번째에 해당하던 데이터의 연결된 노드만 삭제된다. O(1)

 

스택과 큐