[CS] Stack, Queue

Stack

데이터를 쌓아 올리는 형태의 자료구조

 

Stack 특징

• 후입선출 (LIFO, Last In First Out)
• 데이터의 삽입과 삭제가 Top에서만 가능
• 스택에 데이터 삽입 -> Push, 스택에서 데이터 꺼내기 -> Pop
• 시간 복잡도 -> O(n)
• 공간 복잡도 -> O(n)

 

Stack 활용

• 안드로이드의 액티비티 관리
• 함수의 콜 스택
• 연산자 후위 표기법
• 웹 브라우저 방문기록 (뒤로가기)
  사용자가 방문한 페이지를 스택에 저장하여 뒤로 가기 버튼을 누를 때 스택에서 이전 페이지를 꺼내 보여줌
• 역순 문자열 만들기
  문자열을 스택에 삽입한 뒤, 스택에서 원소를 꺼내면 역순으로 된 문자열을 얻을 수 있음
• 실행 취소 (Undo)
  사용자가 수행한 작업을 스택에 저장해 실행 취소를 수행할 때 스택에서 이전 상태를 꺼내어 복구
• 깊이 우선 탐색 (DFS, Deep-First Search) 

 

---

Queue

줄을 서서 기다리는, 데이터가 입력된 순서대로 처리하는 형태의 자료구조

 

Queue 특징

• 선입선출 (FIFO, First In First Out)
• 입구와 출구가 나뉘어 있음
• 데이터 삽입 장소 -> Rear, 데이터 삭제 장소 -> Front
• 데이터 삽입 -> Enqueue, 데이터 삭제 -> Dequeue
• 시간 복잡도 -> O(n)
• 공간 복잡도 -> O(n)

 

Queue 활용

• 안드로이드에서 루퍼의 메시지 큐
• 버퍼나 마구 입력된 내용을 처리하지 못하고 있는 상황
• 인쇄 대기열
• 은행 업무
• 프로세스 관리
• 너비 우선 탐색 (BFS, Breadth-First Search)

 

---

 

<< stack 2개로 queue 만들기 >>

1. 각각 in, out 이라는 스택 2개를 생성
2. 이때 in 스택에 각각 a, b의 데이터를 삽입(push) -> 순서 : a, b
3. in 스택에서 데이터를 추출(pop) -> 순서 : b, a
4. out 스택에 삽입 -> 순서 : b, a
5. out 스택에서 데이터 추출 -> 순서 : a, b
6. 결국 선입선출(FIFO) 형태로 데이터의 삽입과 추출이 가능해지며 queue처럼 이용할 수 있다.

 

---

* https://dev-records.tistory.com/entry/자료구조-스택Stack과-큐Queue

* https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data%20Structure/%5BData%20Structure%5D%20Stack과%20Queue.md