Session-자료구조 Stack & Queue

스택은 위에서부터 쌓인 것

1. Stack

---

• 마지막으로 저장한 데이터가 처음으로 읽힙니다.
• 영어로 하면 LIFO(Last In First Out)
• Stack에서 데이터 저장은 push 라고 합니다.
• 데이터를 읽어들이는 건 pop 이라고 합니다. 다만 pop은 읽어들임과 동시에 stack에서 삭제합니다.

 

스택활용 파이썬 예시

 

Stack의 활용

• 웹브라우저 방문기록(뒤로가기) 및 실행취소

• 미로찾기 알고리즘

  → 방문한 곳을 좌표로 표기하고, 다음 방문할 곳을 탐색한 후 Stack에 가능한 곳 전부를 push하고, 다시 pop 하면서 현재 경로로 변경하는 것을 반복

 

• 프로그램에서의 함수 호출 기록을 stack으로 저장. 

2. Queue

---

• 데이터가 들어온 순서대로 처리됩니다.(먼저 push된 게 먼저 pop 됩니다)
• 새치기는 안돼요! 새로운 데이터는 가장 마지막줄에 삽입됩니다.
• 영어로 하면 FIFO(First In First Out)

큐활용 파이썬 예시

Queue의 활용

• CPU의 프로세스 스케줄링
• 프린터의 인쇄 대기목록
• 맛집 예약, 티켓카운터 등의 예약 시스템

더 나아가서 원형큐, 우선순위 큐 같은 것들도 있는데 난이도 있는 알고리즘 문제로 출제 되기도 합니다.