스택과 큐

스택과 큐는 배열보다 발전한 형태로 서로 구조는 비슷하지만 처리 방식이 다릅니다.

 

• 스택(stack)
  • 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조이다.
  • 삽입과 삭제 연산이 한쪽에서만 일어나는 특징을 가지고 있다.
  • 깊이 우선 탐색(Depth First Search), 백 트래킹 종류에 효과적이다.
  • 후입선출은 재귀 함수 알고리즘 원리와 개념 자체가 비슷하다.

스택

• push : top위치에 새로운 데이터를 삽입하는 연산
• pop : top위치에 현재 있는 데이터를 지우는 연산이다.
• top : top 위치에 현재 있는 데이터를 확인하는 연산이다.

 

• 큐(queue)
  • 삽입과 삭제 연산이 선입 선출로 이루어지는 자료구조이다.
  • 삽입과 삭제가 양방향에서 이루어진다.
  • 새 데이터의 삽입은 back에서 이루어지고 기존 데이터의 삭제는 front에서 이루어진다.
  • 너비 우선 탐색(Breadth First Search) 에서 자주 사용한다.

큐

• back : 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front : 큐에서 가장 앞 데이터를 가리키는 영역이다.
• push : back 부분에 새로운 데이터를 삽입하는 연산이다.
• pop : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.

 

출처) Do it! 코딩테스트 c++편