[자료구조] 스택(Stack)

스택(Stack)

https://luv-n-interest.tistory.com/161

스택(Stack : 쌓다)은 사진에서 사과를 쌓을 때 위로 쌓는 것만 가능하듯이 한 방향으로만 입력할 수 있으며, 구조 중간에 값을 끼워 넣어 저장할 수 없다. 즉, 같은 크기의 자료를 정해진 한 방향으로만 입력, 저장, 삭제가 가능하다.

 

맨 아래 있는 사과를 꺼내기 위해서 가장 위에 있는 사과부터 꺼내야 하는 것처럼 후입선출(Last-In First-Out, LIFO) 구조로 가장 마지막에 들어온 데이터(사과)가 가장 먼저 리턴, 삭제된다는 뜻이다.

 

스택의 연산

📌 push(item)

item 하나를 스택의 가장 윗부분에 추가한다.

 

📌 pop()

스택에서 가장 위에 있는 항목을 제거한다.

 

📌 peek()

스택의 가장 위에 있는 항목을 반환한다. (이번에 꺼낼 값이 뭔지 확인한다)

 

📌 isEmpty()

스택이 비어 있을 때 true를 반환한다. (스택의 값을 전부 꺼냈는지 확인한다)

 

스택의 장단점

📌장점

• 구조가 단순해서 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

 

📌단점(배열 기반)

• 데이터 최대 개수를 미리 정해야 한다.
• 저장 공간 낭비 발생할 수 있다. (미리 최대 개수만큼 저장 공간 확보해야 함)

 

스택은 언제 사용될까?

🔙 브라우저의 뒤로가기

웹 브라우저의 뒤로 가기를 누르면 '스택' 자료구조를 사용하는 것이다.

웹 브라우저에 들어가면 스택에 해당 주소들을 저장해두었다가 뒤로가기를 누를 때 스택의 맨 위에 있는 한 페이지를 가져가는 것이다.

 

⏰ 실행 취소(Ctrl + Z)

내 앱에서 되돌리기를 실행하려면 유저가 하고 있는 행동들을 스택에 차곡차곡 쌓다가 되돌리기를 누르는 순간 스택으로 가서 과거를 되돌릴 수 있는 것이다.

 

실습

스택은 배열 기반, 연결 리스트 기반으로 구현할 수 있어서 각각 따로 포스팅을 해두었다!

- 스택(Stack) 실습(feat. 배열)

- 스택(Stack) 실습(feat. 연결 리스트)

 

🤔 연결 리스트를 활용하는 스택???

연결 리스트도 하나의 자료구조인데 이것을 이용해 다른 자료구조를 구현하는 게 의아할 수가 있다. 하지만 배열도 자료구조이고 리스트의 구현 도구로도 사용된다. 마찬가지로 연결 리스트도 하나의 자료구조이지만 다른 자료구조의 구현에 사용되는 중요한 도구이기도 하다. 어찌 보면 연결 리스트는 다른 자료구조의 구현에 사용되는 도구로써 더 큰 의미를 지닌다고 볼 수 있다.

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

📺 https://www.youtube.com/watch?v=Nk_dGScimz8

📄 https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

📄 https://sycho-lego.tistory.com/23