스택이란
스택은 동질적인 요소들의 집합으로 구성된 자료구조이다.
LIFO(last in first out)의 원칙에 기초한다.
일반적으로 사용되는 추상 데이터 유형으로 push 와 pop이라는 두 가지 주요 연산이 있다.
해당 연산은 스택에 가장 최근에 추가된 항목인 맨 위 요소에 대해 수행된다.
push는 스택에 요소를 추가하고 pop은 상단에서 요소를 제거한다.
스택 개념은 컴퓨터의 프로그래밍과 메모리 구성에 사용된다.
스택의 모든 연산은 상단에서 수행된다. push에 의해 요소가 스택에 추가될 때마다 상위 값이 1씩 증가하고, pop에 의해 스택에서 요소가 튀어나오면 상위 값이 1씩 감소된다. 스택의 상단 위치에 대한 포인터는 stack pointer (스택 포인터)라고도 한다.
스택의 동작과정
스택은 제한된 수의 작업만 허용되므로 제한된 데이터 구조다. push와 pop외에도 특정 구현은 다음과 같은 고급 작업을 허용할 수 있다.
Peek - 스택에서 맨 위 항목을 본다.
Duplicate - 상위 항목의 값을 변수로 복사한 후 다시 스택으로 밀어넣는다.
Swap — 스택의 맨 위 항목 두 개를 교환한다.
Rotate — 숫자로 지정된 대로 스택의 맨 위 요소를 이동하거나 회전하는 방식으로 이동한다.
스택에 관련된 문제는 다음과 같다.
백준 - 9012번
입력된 괄호문자열이 올바른 괄호 문자열인지 아닌지 확인여부를 출력하여야 한다.
해당 문제는 스택의 성질을 활용하여 해결할 수 있다.
- 스택은 데이터가 후입선출한다.
- 괄호는 이미 완성된 것이 아니라 순서대로 스택에 들어온다.
위 관점으로 문제를 접근하였다.
- 입력값을 받아주고 스택과 문자열 여부를 초기화 시켜준다.
- 열린 괄호가 들어오면 일단 스택에 넣어둔다. 열린괄호든 닫힌 괄호는 일단 들어와도 문자열이 성립될 수 있기 때문.
- 스택이 비어있는 상태에서 닫힌 괄호가 들어오면 일단 글러먹은 것이다.
)로 시작한 이상 이미 문자열이 성립 될 수 없음.- 이미 완성된 괄호는 신경쓸 필요가 없다.
(), (())가 있으면 뒤에 뭘오든 의미가 없다 이미 완성되어 있으니까
그래서 열린괄호 뒤에 닫힌 괄호가 들어오면 pop을 시켜서 스택 자체를 비워버렸다.- ()) 나 (()의 경우는 어떻게 되냐면 성립된 괄호들은 pop되어서 없어졌기 때문에 짝이 없는 괄호들만 남게 된다. 따라서 stack에 남아있는 괄호가 남아있으면 해당 문자열은 성립되지 않는다.
daelkdev@gmail.com