[알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

Stack

• 후입 선출(LIFO)
• 선입 후출(FILO)
• push, pop, top, isEmpty
  * isEmpty가 True일 때 pop하면 Underflow

 

* 배열 vs 스택

• 배열: 임의의 위치에 random access O(1)
         동적배열이 아닌 이상 static한 환경에서 append 불가능
• 스택: top에만 접근 O(1)
         한쪽 끝에서만 추가/삭제 일어나는 구조가 필요한 케이스에 유용
         ex) infix -> postfix로 바꾸기, 최근 행위 undo하기

 

 

Queue

• 선입 선출(FIFO)
• Enqueue, Dequeue, Front, Rear, isEmpty
  * isEmpty가 True일 때 pop하면 Underflow

 

 

Deque (Double Ended Queue)

• 스택+큐
• 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
• push front/back, pop front/back, front, back, isEmpty
  * isEmpty가 True일 때 pop하면 Underflow

 

 

 

---

관련문제

• 스택
  9012. 괄호  (정답코드)
  2841. 외계인의 기타 연주 (정답코드) stack을 monotonic하게 관리
  2812. 크게 만들기 (정답코드)
  17298. 오큰수 (정답코드)
  1935. 후위 표기식2 (정답코드)
  2022.01.27 - [PS/Baekjoon] - [백준/C++] 6604번: Matrix Chain Multiplication(S4)
  2022.01.27 - [PS/Baekjoon] - [백준/C++] 1863번: 스카이라인 쉬운거(G5)
  
  
  
• 큐
  14713. 앵무새 (정답코드)
  1158. 요세푸스 문제 (정답코드) (시간복잡도 O(NK). N,K가 커지면 세그먼트트리 이용_1168번 참고)
  3078. 좋은 친구 (정답코드)
  
  
• 덱
  20301. 반전 요세푸스 (정답코드)
  19591. 독특한 계산기 (정답코드)
  2022.01.27 - [PS/Baekjoon] - [백준/C++] 18115번: 카드 놓기(S3)