[알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin

목차

 

스택 자료구조 개념

 

스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이 있습니다.

 

1. push: 스택에서 가장 위에 element를 추가합니다. 

2. pop: stack에 가장 위에 있는 element를 제거합니다.

 

이 의미는 한쪽에서만 데이터를 추가하고 제거할 수 있다는 뜻입니다. 우리는 이러한 stack 구조를 LIFO(last-in-first-out - 가장 마지막으로 추가한 게 가장 먼저 나가는 구조)라고 부릅니다.  

 

 

스택을 코드로 표현하면 아래와 같습니다.

 

interface Stack<Element> {
	
    fun push(element:Element)
    
    fun pop(): Element?
    
}

 

스택은 프로그래밍에서 두드러지게 사용됩니다. 예를 들어: 

 

- 안드로이드에서 뷰를 컨트롤할 때 fragment를 가장 위에 보여줬다가, 뒤로 가기를 누르면 가장 위에 있는 프라그 먼트를 삭제합니다. 

 

- 메모리를 할당할 때도 stack을 사용합니다. 

 

- search, conquer알고리즘, path out of maze 또한 stack을 사용합니다. 

 

---

 

스택 자료구조 및 [필수] 구현 요소

 

Stack 자료구조에서 가장 중요한 것은 push pop이 들어가야 합니다. 그러므로 push pop이 구현 가능하도록 데이터 저장을 arrayList로 해주겠습니다.

 

class Stack<T: Any>() {
	
    //ArrayList를 storage타입으로 가져가겠습니다. 왜냐하면 push와 pop을 모두 사용할수있기때문입니다.
	private val storage = arrayListOf<T>()
    
    //디버그를 위해 toString을 추가해주었습니다.
    override fun toString() = buildString{
    	appendln("----top----")
        storage.asReversed().forEach{
        	appendln("$it")
        }
    	appendln("-----------")
    }
    //stack에 가장 중요한 요소인 push, pop을 구현하겠습니다.
    
    override fun push(element:Element){
    	storage.add(element)
    }
    
    override fun pop():Element? {
    	if(storage.size ==0){
        	return null
        }
        return storage.removeAt(storage.size - 1)
    }
}

 

위 코드를 이용해서 stack을 만들어보겠습니다. 

 

"using a stack" example {
 	val stack = StackImpl<Int>().apply {
 		push(1)
 		push(2)
 		push(3)
 		push(4)
 	}
 	print(stack)
 	val poppedElement = stack.pop()
 	if (poppedElement != null) {
 		println("Popped: $poppedElement")
 	}
 	print(stack)
}

 

위코드를 실행해주면 아래와 같은 결과가 나옵니다. 

 

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4
----top----
3
2
1
-----------

 

---

 

스택 자료구조 [선택] 구현 요소

 

스택 자료구조를 구현할 때 push와 pop이 필수요소였다면 선택적인 요소들도 있습니다.

 

Peek

 

Peek는 스택에 가장 위 element를 반환하는 함수입니다. peek 함수에서

 

Count

 

count속성은 스택에 element개수를 리턴합니다.

 

override fun peek():Element?{
	return storage.lastOrNull()
}

override val count:Int
	get() = storage.size

 

---

 

정적 팩토리 메서드 사용

 

정적 팩토리 메서드란 객체 생성의 역할을 하는 클래스 메서드입니다. 더 쉽게 설명하면 메서드를 이용해 클래스를 생성하는 것을 의미합니다.

 

스택 구현 클래스를 만들겠습니다. 

 

companion object {
	fun<Element> create(items: Iterable<Element>):
    Stack<Element>{
    	val stack = StackImpl<Element>()
        for(item in items){
        	stack.push(item)
        }
        return stack
    }
}

 

정적 팩토리 메서드를 사용해서 리스트를 stack으로 바꿔보겠습니다.메인 문에서 써보겠습니다.

 

"initializing a stack from a list" example{
	val list = listOf("A", "B", "C", "D")
    val stack = StackImpl.create(list)
    print(stack)
    
}

 

---

 

참고

 

Announcing Data Structures & Algorithms in Kotlin, Second Edition!