스택(Stack)과 큐(Queue) 자료구조

스택(Stack) 자료구조

삽입과 삭제 연산이 후입선출(LIFO : Last-In First-Out)로 이뤄지는 자료구조

 

* 후입선출 : 가장 나중에 삽입된 데이터를 가장 먼저 삭제한다.

  ⇒ 삽입과 삭제가 한 쪽에서만 일어난다.

 

스택 push 연산 과정

 

- 새 값이 스택에 들어가면 top이 새 값을 가리킨다.

 

스택 pop 연산 과정

 

- 스택에서 값을 빼낼 때 pop는 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다.

 

 

스택 용어

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

 

---

 

큐(Queue) 자료구조

삽입과 삭제 연산이 선입선출(FIFO : First-In First-Out)로 이뤄지는 자료구조

 

* 선입선출 : 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다.

  ⇒ 삽입과 삭제가 양방향에서 이뤄진다.

 

큐 연산 과정

 

- 새 값이 추가는 큐의 back에서 이뤄진다.

- 삭제는 큐의 front에서 이뤄진다.

 

 

큐 용어

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

 

 

우선순위 큐(Priority Queue)

• 값이 들어간 순서와 상관없이 우선순위가 높은 데이터를 가장 먼저 삭제한다.
• 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
• 일반적으로 힙(heap)을 이용해 구현한다.
  
  • 최소 힙 : 값이 낮은 데이터 먼저 삭제
  • 최대 힙 : 값이 큰 데이터 먼저 삭제

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.