[Data Structure] Stack

"스택"(Stack)은 말 그대로 "무언가를 쌓아 올린 것"을 의미한다.

대표적으로 프링글스 통이 있다. 프링글스 통 안에는 과자가 쌓여있고, 최근에 들어간 과자가 가장 먼저 나오는 구조이다. 

이러한 구조를 "스택"이다 부른다.

 

"스택"은 선형 자료구조로 다음과 같은 2가지 Main Operation을 제공하는 ADT이다. 

• push : 원소를 추가한다.
• pop : 가장 최근에 추가된 원소를 제거한다. 

ADT는 자료와 자료들의 연산에 대한 명세이다. 이를 구현한 것이 자료구조가 되며, 스택과 같이 대부분 ADT와 자료구조는 동일한 이름을 갖는다. 

 

앞선, 프링글스 통을 다시 살펴보자! 

프링글스 통은 입구 및 출구가 한개이기에, 가장 최근에 넣은 과자가 먼저 나올 수 있다. 

즉, 스택도 다음과 같은 구조이기에 가장 최근에 넣은 원소가 먼저 나올 수 있으며, 이를 LIFO(Last in first out)이라 부른다. 

또한, 이렇게 원소의 삽입 & 삭제 위치가 한정되는 특성 때문에 Restricted Structure이라고도 부른다. 

 

사용 

스택은 다양한 곳에서 사용된다. 대표적으로 DFS알고리즘에 사용되며, OS에서도 사용된다. 

Process는 OS에 의해 Address Space가 할당되며 여기에는 Data, Heap, Text, Stack 영역이 할당된다. 

 

이 스택 영역이 자료구조 스택이며, 함수(Procedure)이 수행될 때, return address, 로컬 변수 등이 저장된다.

하지만, 메모리 구조 상 이러한 스택 영역은 유한하기에, 해당 공간이 꽉 차게 되면 Stack Overflow가 발생된다.

 

흔히, 백준에서 Stack Overflow를 마주하게 되는데, 

이 역시 재귀 함수의 depth가 깊어지거나, local변수의 크기가 커지게 되는 등 스택 영역이 꽉 차게 되면서 발생하는 에러이다. 

 

 

구현

자료구조로서의 스택은 연결 리스트 혹은 배열로 구현할 수 있는데, 다음과 같은 특성을 갖는다.

• 원소의 추가 및 제거가 O(1) 

기본적으로 Swift에선 Stack을 제공하지 않기 때문에, 직접 구현해 보자. 

자세한 구현은 아래 링크에서 확인해볼 수 있다.

https://github.com/jungseokyoung-cloud/Data-Structure

GitHub - jungseokyoung-cloud/Data-Structure: Data Structures implemented with Swift

 

구현에 앞서, Stack에서 사용되는 기능들을 정리하면 다음과 같다.

public protocol Stack {
	associatedtype T
	
	var count: Int { get }
	var isEmpty: Bool { get }
	var top: T? { get }
	
	mutating func push(_ element: T)
	mutating func pop() -> T?
}

 

Static Array를 이용한 구현

Static Array는 배열의 크기가 고정되어 있기에, 생성 단계에서 Stack의 사이즈가 결정 난다. 

 

Swift에서 제공하는 Array는 기본적으로 Dynamic Array만을 제공하기에, Objective-C의 NSMutableArray를 사용해야 한다.

NSArray는 원소의 수정이 불가능하기 때문에, NSMutableArray를 사용했다. 

 

Swift의 Array는 스택 영역에 할당되지만, 

NSMutableArray는 힙 영역에 할당된다. 

즉, NSMutableArray는 let 키워드를 사용해도 subscripts를 통해 원소의 수정이 가능하다.

 

public struct StaticStack<T>: Stack {
	private let capacity: Int
	private let elements: NSMutableArray
	/// 스택의 위치를 나타내는 포인터로, 원소가 추가되는 위치이다.
	private var stackPointer = 0
	
	public var count: Int {
		return stackPointer
	}
	
	public var isFull: Bool {
		count == capacity
	}
	
	public var isEmpty: Bool {
		return stackPointer == 0
	}
	
	/// 최상단의 원소를 반환합니다.
	public var top: T? {
		guard !isEmpty else { return nil }
		
		return elements[stackPointer - 1] as? T
	}
	...
}

우선, 내부적으로 사용되는 변수들을 다음과 같이 추가해 주었다. 

 

다음과 같이 생성자는 capacity를 파라미터로 전달 받으며, 고정된 사이즈의 NSMutableArray를 추가해주었다. 

또한, elements는 let 키워드로 선언했기에, 사이즈의 변경은 불가능하다. 

// MARK: - Initializer
public init(capacity: Int = 10) {
	self.capacity = capacity
	self.elements = NSMutableArray(capacity: capacity)
}

 

마지막으로 push와 pop메서드이다. 

public mutating func push(_ element: T) {
	guard !isFull else { fatalError("Stack Overflow") }
	
	defer { stackPointer += 1 }
	self.elements[stackPointer] = element
}

@discardableResult
public mutating func pop() -> T? {
	guard !isEmpty else { return nil }
    
	stackPointer -= 1
	return elements[stackPointer] as? T
}

 

Linked List 

앞서 Static Array로 구현을 하게 되면 구현이 간단하다는 장점이 있지만, 컴파일 타임에 스택의 사이즈를 결정해야 한다는 단점이 존재한다. 

 

반면, Linked List를 사용하게 되면 동적으로 스택의 사이즈가 결정 나게 되지만, 연결리스트를 추가적으로 구현해야 한다는 단점이 존재한다. 

 

마지막 원소에 push와 pop이 O(1)에 결정나야 하기 때문에, 이중 연결리스트를 사용해 구현했다. 

이중 연결리스트의 대한 내용은 여기에서 볼 수 있다. 

https://seokyoungg.tistory.com/87#3.%20Double%20Linked%20List

[Data Structure] Array & Linked List(2) - Implementation

public struct LinkedStack<T>: Stack {
	fileprivate typealias Node = DoubleLinkedNode<T>
	
	private var head: Node?
	private weak var tail: Node?

	public private(set) var count: Int = 0
	
	public var isEmpty: Bool {
		head == nil
	}
	
	public var top: T? {
		return tail?.data
	}
	
	public init() { }
}

이후, tail 포인터를 조작해 push와 pop에는

이중 연결리스트에서 tail에서의 삽입, 삭제를 구현하면된다. 

 

Dynamic Array

마지막으로는 동적배열을 이용해 구현하는 방식이며, Swift에선 제일 간편한 방식이다.  

public struct DynamicStack<T>: Stack {
	private var elements: [T] = []
	
	public var count: Int {
		return elements.count
	}
	
	public var isEmpty: Bool {
		return elements.isEmpty
	}
	
	public var top: T? {
		return elements.last
	}
	
	public init() { }
}

// MARK: Public Methods
public extension DynamicStack {
	mutating func push(_ element: T) {
		elements.append(element)
	}
	
	mutating func pop() -> T? {
		return elements.popLast()
	}
}

 

 

References

위키백과 

• Stack(abstract data type)