스택(Stack)

스택이란?(What is Stack?)

---

 우리가 식당같은 곳에 가보면 다 먹은 음식의 접시나 그릇은 위로 차곡차곡 쌓아 올리는 모습을 볼 수 있다. 설거지를 할때는 위에서부터 하나씩 꺼내어 설거지를 하게 된다. 이것이 스택이다. 스택(Stack)이란 데이터 삽입, 삭제가 한 방향에서만 이루어지는 것을 말한다. 스택은 가장 먼저 들어온 데이터는 가장 나중에 나가고 가장 나중에 들어온 데이터는 가장 먼저 나가게 된는 성질을 가지고 있다. 이를 LIFO(Last-In-First-Out) 또는 FILO(First-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 LIFO를 더 많이 사용한다.

 

 스택은 top과 bottom이라는 2개의 포인터를 이용하여 삽입과 삭제를 제어한다. top포인터는 스택의 가장 위에 있는 데이터를 가리키며 push(데이터를 넣는 연산)나 pop(데이터를 빼는 연산)을 할 때 사용된다. bottom은 스택의 가장 밑바닥을 가리킨다. 쉽게 생각하면 상자의 바닥과 같은 역할이다. bottom포인터는 스택이 어느 방향으로 증가하는가에 따라 주소값이 달라질 수 있다.

 

스택

 

스택의 연산(Stack Operation)

---

스택을 사용하기 위해서는 스택을 제어하는 여러가지 연산이 필요하다. 스택을 제어하는 기본적인 연산은 다음과 같다.

 

• Push(S, x) : 스택 S에다 데이터 x를 넣는다.
• Pop(S) : 스택 S에서 1개의 데이터를 꺼낸다.

 

스택 연산 과정

 

처음에 스택을 만들게 되면 top은 -1로 초기화를 하게 된다. Push(S, A)는 스택 S에 A를 넣는 과정이다. Push를 할 때는 스택에 남은 공간이 있는지 확인하기 위해 top에 1을 더해주고 스택의 공간이 남아있다면 A를 Push하게 된다. Push(S, B)도 같은 연산을 하게 된다. Pop은 스택에서 가장 위에 있는 데이터를 꺼내게 된다. Pop을 하기 전 스택이 비었는지 확인하고 Pop을 한다. Pop을 할 때는 데이터를 꺼낸 후 top을 1 감소시킨다. 여기서 스택의 가장 위에 있는 'B'를 꺼내어 최종적으로 스택에는 'A'만 남게 된다.

 

 

스택의 응용(stack application)

---

스택은 다음과 같은 곳에 사용될 수 있다.

 

1. 시스템 스택(System stack) : 함수 호출시 리턴 주소를 기억
2. 회문 판별및 생성(Checking /creating Palindrome) : DNA 분석에서 쓰임
3. 프로그래밍 언어 문법 교정(correcting syntax of programming language)
4. 후위 표기법(postfix expression)

 

스택 구현(stack implementation)

---

구현은 아래 필자의 깃허브에 있으니 참고하길 바란다. 기본적인 원리만 구현을 했기 때문에 실제 사용에는 무리가 있다.참고만 하길 바란다.

GitHub - LimeTree0/Data-Structure