Last active
September 11, 2017 10:06
-
-
Save loromits/78bce21f1d605c255d29c8e7572ed42f to your computer and use it in GitHub Desktop.
Simple Stack data structure implementation in Swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct Stack<Element> { | |
fileprivate class Node { | |
let value: Element | |
var previousNode: Node? | |
init(_ value: Element, previousNode: Node?) { | |
self.value = value | |
self.previousNode = previousNode | |
} | |
} | |
fileprivate var topNode: Node? | |
init() {} | |
init<S: Sequence>(_ s: S) where S.Iterator.Element == Element { | |
for entry in s { | |
push(entry) | |
} | |
} | |
mutating func rotateLeft(_ count: Int) { | |
guard count > 0 else { return } | |
var cnt = count | |
var insertionCursor = topNode | |
while cnt != 0 && insertionCursor?.previousNode != nil { | |
cnt -= 1 | |
insertionCursor = insertionCursor?.previousNode | |
} | |
let tailNode = insertionCursor?.previousNode | |
insertionCursor?.previousNode = topNode | |
topNode = topNode?.previousNode | |
insertionCursor?.previousNode?.previousNode = tailNode | |
} | |
mutating func swap() { | |
rotateLeft(1) | |
} | |
mutating func rotateRight(_ count: Int) { | |
guard count > 0 else { return } | |
var cnt = count - 1 | |
var extractionParentCursor = topNode | |
while cnt != 0 && extractionParentCursor?.previousNode?.previousNode != nil { | |
cnt -= 1 | |
extractionParentCursor = extractionParentCursor?.previousNode | |
} | |
let extractedNode = extractionParentCursor?.previousNode | |
let tailNode = extractedNode?.previousNode | |
extractedNode?.previousNode = topNode?.previousNode | |
extractionParentCursor?.previousNode = tailNode | |
topNode = extractedNode | |
} | |
mutating func duplicate() { | |
if let topValue = topNode?.value { | |
topNode = Node(topValue, previousNode: topNode) | |
} | |
} | |
mutating func push(_ value: Element) { | |
topNode = Node(value, previousNode: topNode) | |
} | |
mutating func pop() -> Element? { | |
let oldNode = topNode | |
topNode = oldNode?.previousNode | |
return oldNode?.value | |
} | |
func peek() -> Element? { | |
return topNode?.value | |
} | |
} | |
extension Stack where Element: Equatable { | |
static func ==(lhs: Stack, rhs: Stack) -> Bool { | |
var (lhsCursor, rhsCursor) = (lhs.topNode, rhs.topNode) | |
while let lhsValue = lhsCursor?.value, | |
let rhsValue = rhsCursor?.value, | |
lhsValue == rhsValue { | |
(lhsCursor, rhsCursor) = (lhsCursor?.previousNode, rhsCursor?.previousNode) | |
} | |
return lhsCursor == nil && rhsCursor == nil | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment