[알고리즘] Stack

 

 

Stack

---

Stack은 선형 자료구조이며 가장 기초적이고 중요한 개념이다. 선형 자료구조란 '자료가 일렬로 존재하는 구조'를 의미한다. 예를들면 stack, queue, linked list 등 이다. stack에서 꼭 알아야 할 것은 바로 LIFO이다. LIFO는 Last in First out이며 '가장 마지막에 들어온 값이 가장 먼저 나간다는 뜻'을 가진다. 즉 데이터가 삽입되는 구멍과 삭제되는 구멍이 동일하다고 이해하면 되겠다. 아래 그림을 보면 좀더 쉽게 이해할 수 있다.

 

간단하게 예를 들면, 상자 안에 책을 눕혀서 국어책-수학책-영어책 순으로 넣는다면 뺄때는 영어책-수학책-국어책 순으로 빼게 될 것이다. 상자를 부시지 않는 이상 국어책을 빼기 전까지는 수학책 영어책을 빼낼 수 없다 (어떻게서든지 빼낼수 있지 않은가라는 **소리는 멈춰!)

 

알고리즘에서 stack 자료구조를 사용해서 풀수 있는 문제는 '뒤로가기', '수식 후위연산 계산' 등이 있다. 위 예제는 stack을 사용한 대표적인 예제이다. 또한 문자열이나 데이터를 앞뒤로 반복해서 훑거나 전진, 후진을 할때 stack을 사용할 수 있을 것으로 보인다.

 

 

Keywords

---

LIFO	Last in First out
pop	스택에서 가장 마지막에 들어간 (가장 위에 있는) 데이터를 추출
push	스택에 가장 위 부분에 데이터를 삽입
peek	스택에서 가장 마지막에 들어간 (가장 위에 있는) 데이터를 반환
isEmpty	스택이 비어있을때는 true, 아니면 false를 반환

* 추출은 자료구조에서 데이터를 제거 후 반환하는 것을 의미

* 반환은 자료구조에서 데이터를 제거하지 않고 값만 반환하는 것을 의미

 

 

Implementation

---

Stack은 대부분의 프로그래밍 언어에서 기본 라이브러리로 제공한다. Python3에서는 list 자체에 스택 함수가 포함되어있다. 

my_stack = []
print(my_stack)
my_stack.append(1) # push
print(my_stack)
my_stack.append(2)
print(my_stack)
my_stack.append(3)
print(my_stack)
my_stack.append(4)
print(my_stack)
my_stack.pop() # pop
print(my_stack)
my_stack.pop()
print(my_stack)
print(my_stack[-1]) # peek

위 코드처럼 push와 pop, peek를 사용하면 된다.

Java도 마찬가지로 java.util.Stack 라이브러리를 통해서 stack을 구현할 수 있다. Java 에서는 Generic으로 타입을 고정하여 stack을 사용할 수 있다. Java에서는 stack이 따로 구별되어 구현되어있기 때문에 push와 pop, peek 이름 그대로 메서드를 호출해서 사용하면 된다. 

C#의 경우도 System.Collections.Generic에 Stack<T>이 따로 구현되어 있기 때문에 여기서 가져다가 사용하면 된다. 

 

 

Hardware stack

---

아키텍쳐 수준에서도 스택을 사용한다. 메모리 구조를 살펴보면 heap - stack - static - code 와 같은 구조로 이루어져 있다(이에 대한 자세한 설명은 따로 정리해서 업로드할 예정이다). 여기서도 stack이 사용되며, 프로그램 실행시에도 함수가 호출되면 stack으로 관리하게 된다. 그래서 '지역변수는 stack에서 관리된다'라는 말을 들어봤을수도 있다. 

 

 

Reference

---

 

스택 - 위키백과, 우리 모두의 백과사전