[자료구조] 스택 - Stack

728x90

 

 

 

 

🙆‍♂️Stack

---

First in Last out인 자료구조 입니다.

데이터가 쌓여져 가는 구조인데

PUSH라는 명령어로 데이터를 Stack의 가장 위에 올리고 

POP이라는 명령어로 Stack의 가장 위의 명령어를 뺍니다.

TOP이라는 명령어는 가장 위의 명령어에 접근합니다.

 

코딩테스트에서는 배열을 사용하여 스택이라고 가정하여 접근합니다.

 

🙋‍♂️문제

---

🚀 valid parentheses

---

 

괄호 열리고 닫힌 것을 구분하는 문제들은 stack 문제로 보고 풀 수 있습니다.

PUSH를 해서 괄호를 열어주고 POP을 해서 매칭이되면 괄호를 닫아줍니다.

매칭이 안되면 invalid하다는 것을 출력하는 것입니다.

>관련 문제<

 

🚀 min/max stack

---

스택 안에 최솟값과 최대값을 출력하는 명령어를 제공해야하는 문제입니다.

이런 경우는 2개의 스택을 만들어서 한 쪽은 그냥 스택 다른 쪽은 max나 min값을 구하는 스택을 만듭니다.

max값보다 작은 값이 들어오려고 하면 max값을 스택에 올리거나 안올리고

min값보다 큰 값이 들어오려고 하면 min값을 스택에 올리거나 안올립니다.

명령어가 실행되면 top명령어를 통해 제일 위의 데이터에 접근하면 됩니다.

 

더 정확하게 하려면

max/min 스택에 숫자와 갯수까지 같이 넣어주는 것입니다. 그러면 POP할 때 꼬이지 않을 수 있습니다.