[자료구조] 스택 (Stack)

이번에 알아 볼 자료구조는 스택(Stack)이다.

스택은 Stack Overflow나 Stack Memory때문에 한번씩 접했던 자료구조다.

문제 해결을 위해서 사용해본적 없기때문에 어떤식으로 사용되는지 공부해 보겠다.

 

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

※ 틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

스택은 데이터를 한 열로 저장하지만, 마지막에 추가한 데이터에만 접근할 수 있다.

티셔츠를 개서 쌓아 올리면 가장 위에 있는 티셔츠만 집을 수 있고 중간을 건들면 무너지는 것 처럼 스택도 가장 위에 있는 데이터에만 접근 가능하다.

스택의 개념도

스택에 데이터를 추가하면 맨 위에 추가된다.

 

데이터 추가

스택의 푸시(Push)

스택에 데이터를 넣는 작업을 푸시(Push)라고 한다.

Blue를 넣고 Yellow를 다음으로 넣었다.

 

데이터 제거

스택의 팝(Pop)

스택에서 데이터를 꺼내는 작업을 팝(Pop)이라고 한다.

스택에서 데이터를 꺼낼 때는 가장 직전에 추가된 데이터부터 꺼낸다. 따라서 나중에 추가된 Yellow를 꺼내고 다음으로 Blue를 꺼낼 수 있다.

 

데이터 접근

스택처럼 나중에 넣은 것 부터 꺼내는 후입선출 구조를 Last In First Out, 줄여서 LIFO라고 한다.

또한 맨 위에 놓인 데이터만 접근할 수 있기 때문에 중간에 있는 데이터에 접근하려면 해당 데이터가 스택의 맨 위에 놓일 때까지 데이터를 팝해야 한다.

---

📌 추가 내용

스택은 한쪽 끝에서만 조작할 수 있다는 제약 조건 때문에 불편해 보인다.

하지만 항상 최신 데이터에 접근해야 할 때 유용하게 사용할 수 있다.

 

예를 들어 (AB(C(DE)F)(G((H)IJ)K))라는 문자열에서 같은 괄호에 묶인 문자를 알고싶을때 왼쪽 괄호를 만나면 push하고 오른쪽 괄호를 만나면 pop하는 방식으로 알수있다.

 

왼쪽부터 차례대로 살펴보면 스택을 활용해서 같은 레벨의 문자를 확인할 수 있다.

 

또한 나중에 공부할 깊이 우선 탐색이라는 알고리즘에서도 항상 최신의 것을 선택해야 하기 때문에 스택을 사용한다.

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

 

 

---

📝 스택(Stack) 관련 문제

[C#][프로그래머스 > 코딩테스트 기초] 배열 만들기 6

 

[C#][프로그래머스] 햄버거 만들기