스택(Stack)과 큐(Queue)

스택(Stack)

---

스택은 삽입과 삭제 연산이 후입선출(LIFO : Last In First Out)로 이루어지는 자료구조입니다.

후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있습니다.

출처 : https://www.javatpoint.com/python-stack-and-queue

그림을 보듯 새 값이 스택에 들어가면 top이 새 값을 가리킵니다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으며 결과적으로 가장 마지막에 넣었던 값이 나오게 됩니다.

 

용어

• 위치
  • top : 삽입과 삭제가 일어나는 위치
• 연산
  • push : top 위치에 새로운 데이터를 삽입하는 연산
  • pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  • peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류의 알고리즘에 효과적입니다.

 

 

 

큐(Queue)

---

큐는 삽입과 삭제 연산이 선입선출(FIFO : First In First Out)로 이뤄지는 자료구조입니다. 스택과 다르게 먼저 들어온 데이터가 먼자 나가게 됩니다.

출처 : https://www.javatpoint.com/python-stack-and-queue

새 값의 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어집니다.

 

용어

• 위치
  • rear : 큐에서 가장 끝 데이터를 가리키는 영역
  • front : 큐에서 가장 앞의 데이터를 가리키는 영역
• 연산
  • add : rear 부분에 새로운 데이터를 삽입하는 연산
  • poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • peek : front 부분에 있는 데이터를 확인하는 연산

큐는 너비 우선 탐색(BFS : Breadth First Search)알고리즘에 사용됩니다.