[바킹독: 알고리즘] 스택 (Stack)

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

[목차] 정의와 성질, 기능과 구현, STL Stack, 연습문제

[실전 알고리즘] 0x05강 - 스택

출처: blog.encrypted.gg/933?category=773649

---

정의와 성질

스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 것을 이야기합니다. 과자 중 프링글스 통을 생각하면 쉽습니다. 구조적으로 먼저 들어간 원소가 제일 나오는 FILO (First In Last Out) 자료구조 입니다.

 

큐나 덱도 스택처럼 특정 위치에서 원소를 넣거나 빼는 제한이 있습니다. 그래서 스택, 큐, 덱을 묶어 Restricted Structure이라고 합니다. 

스택은 특정 위치에서 넣거나 뺄 수 있기에 시간복잡도는 아래와 같습니다.

 

1. 원소의 추가, O(1)
   
   
2. 원소의 제거, O(1)
   
   
3. 제일 상단의 원소 확인, O(1)
   
   
4. 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능

원칙적으로 불가능하다는 것은 원래 스택이라는 자료구조는 추가/제거/제일 상단의 원소 확인 기능만 제공하는 자료구조입니다. 그래서 제일 상단이 아닌 나머지 원소들의 확인 및 변경은 스택에서 제공하는 기능이 아닙니다. 구현을 할 때 배열을 기반으로 구현해 해당 기능이 가능하도록 만들 수 있지만, 추후 스택의 응용 사례들을 보면 모두 원소의 추가/제거/제일 상단의 원소 확인 기능만 제공합니다.

 

정리하자면, 스택에서 제일 상단이 아닌 나머지 원소들의 확인 및 변경 기능이 제공되지 않습니다. 

---

구현

스택은 배열 혹은 연결 리스트를 이용해 구현할 수 있습니다. 배열을 활용해 구현하는 것이 가장 효율적입니다.배열로 구현할 때, 원소를 담을 큰 배열 하나와 인덱스를 저장할 변수가 필요합니다. index는 원소를 저장할 위치를 가르키고 있습니다. 역으로 생각하면, 이 변수의 값이 스택의 길이를 뜻합니다.

 

 

---

STL Stack

Stack을 직접 구현하는게 어렵지 않지만, 그래도 Human error라는 것이 존재하기에 제공되는 Stack을 사용하는게 좋습니다. STL Stack 사용 예제를 살펴보는 것을 권장드립니다.

 

---

연습문제

(1) BOJ 10828번: 스택

 

 

github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

encrypted-def/basic-algo-lecture

www.acmicpc.net/workbook/view/7309

문제집: 0x05강 - 스택 (BaaaaaaaaaaarkingDog)

 

다시 풀어봐야하는 문제

 

(1) BOJ 6198번 : 시간초과

(2) BOJ 2493번 : 시간초과