Swift Language
स्विफ्ट के साथ एल्गोरिदम
खोज…
परिचय
एल्गोरिथ्म कंप्यूटिंग के लिए एक रीढ़ है। किस परिस्थिति में किस एल्गोरिथम का उपयोग करना है, इसका चुनाव करना एक अच्छे प्रोग्रामर से औसत को अलग करता है। इसे ध्यान में रखते हुए, यहाँ कुछ बुनियादी एल्गोरिदम की परिभाषाएँ और कोड उदाहरण हैं।
सम्मिलन सॉर्ट
कंप्यूटर विज्ञान में सम्मिलन सॉर्ट अधिक बुनियादी एल्गोरिदम में से एक है। प्रविष्टि सॉर्ट एक संग्रह के माध्यम से तत्वों को रैंक करता है और उनके मूल्य के आधार पर तत्वों को रखता है। सेट को सॉर्ट किए गए और बिना हल किए हुए हिस्सों में विभाजित किया गया है और सभी तत्वों को हल करने तक दोहराया जाता है। सम्मिलन प्रकार में O (n2) की जटिलता है। आप इसे विस्तार में रख सकते हैं, जैसे नीचे दिए गए उदाहरण में, या आप इसके लिए एक विधि बना सकते हैं।
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
छंटाई
बबल शॅाट
यह एक सरल सॉर्टिंग एल्गोरिथ्म है जो बार-बार सूची के माध्यम से क्रमबद्ध किया जाता है, आसन्न वस्तुओं के प्रत्येक जोड़े की तुलना करता है और गलत क्रम में होने पर उन्हें स्वैप कर देता है। सूची में पास तब तक दोहराया जाता है जब तक कि कोई स्वैप की आवश्यकता न हो। यद्यपि एल्गोरिथ्म सरल है, यह अधिकांश समस्याओं के लिए बहुत धीमा और अव्यवहारिक है। इसमें O (n2) की जटिलता है लेकिन इसे सम्मिलन प्रकार की तुलना में धीमा माना जाता है।
extension Array where Element: Comparable {
func bubbleSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryIndex in 0..<self.count {
let passes = (output.count - 1) - primaryIndex
//"half-open" range operator
for secondaryIndex in 0..<passes {
let key = output[secondaryIndex]
//compare / swap positions
if (key > output[secondaryIndex + 1]) {
swap(&output[secondaryIndex], &output[secondaryIndex + 1])
}
}
}
return output
}
}
सम्मिलन सॉर्ट
कंप्यूटर विज्ञान में सम्मिलन सॉर्ट अधिक बुनियादी एल्गोरिदम में से एक है। प्रविष्टि सॉर्ट एक संग्रह के माध्यम से तत्वों को रैंक करता है और उनके मूल्य के आधार पर तत्वों को रखता है। सेट को सॉर्ट किए गए और बिना हल किए हुए हिस्सों में विभाजित किया गया है और सभी तत्वों को हल करने तक दोहराया जाता है। सम्मिलन प्रकार में O (n2) की जटिलता है। आप इसे विस्तार में रख सकते हैं, जैसे नीचे दिए गए उदाहरण में, या आप इसके लिए एक विधि बना सकते हैं।
extension Array where Element: Comparable {
func insertionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
let key = output[primaryindex]
var secondaryindex = primaryindex
while secondaryindex > -1 {
if key < output[secondaryindex] {
//move to correct position
output.remove(at: secondaryindex + 1)
output.insert(key, at: secondaryindex)
}
secondaryindex -= 1
}
}
return output
}
}
चयन छांटना
चयन प्रकार इसकी सादगी के लिए विख्यात है। यह सरणी में पहले तत्व से शुरू होता है, यह एक न्यूनतम मूल्य (या अधिकतम, क्रमबद्धता के आधार पर) के रूप में मूल्य की बचत करता है। यह तब सरणी के माध्यम से पुनरावृत्त करता है, और रास्ते में मिलने वाले किसी भी अन्य मान से कम मान को बदल देता है। उस न्यूनतम मान को तब सरणी के सबसे बाएं भाग में रखा जाता है और प्रक्रिया को अगले सूचकांक से, सरणी के अंत तक दोहराया जाता है। चयन प्रकार में O (n2) की जटिलता है, लेकिन इसे समकक्ष - चयन प्रकार से धीमा माना जाता है।
func SelectionSort () -> Array {// trivial case guard self.ount के लिए जांच करें> 1 और {{self self लौटें}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
त्वरित क्रमबद्ध - O (n लॉग एन) जटिलता समय
क्विकसॉर्ट उन्नत एल्गोरिदम में से एक है। यह O (n लॉग एन) की एक समय जटिलता की सुविधा देता है और एक विभाजन और जीत की रणनीति को लागू करता है। इस संयोजन के परिणामस्वरूप उन्नत एल्गोरिथम प्रदर्शन होता है। क्विकर पहले एक बड़े सरणी को दो छोटे उप-सरणियों में विभाजित करता है: निम्न तत्व और उच्च तत्व। Quicksort फिर से उप-सरणियों को सॉर्ट कर सकता है।
कदम हैं:
एक तत्व चुनें, जिसे एक धुरी कहा जाता है, सरणी से।
सरणी को फिर से व्यवस्थित करें ताकि धुरी से कम मूल्यों वाले सभी तत्व धुरी से पहले आए, जबकि धुरी की तुलना में अधिक मान वाले सभी तत्व इसके बाद आते हैं (समान मान किसी भी तरह से जा सकते हैं)। इस विभाजन के बाद, धुरी अपनी अंतिम स्थिति में है। इसे विभाजन ऑपरेशन कहा जाता है।
उपरोक्त चरणों को छोटे मानों के साथ तत्वों के उप-सरणी में और अलग-अलग मानों के साथ तत्वों के उप-सरणी में अलग से लागू करें।
म्यूटिंग क्विक क्वॉर्ट () -> एरे {
func qSort(start startIndex: Int, _ pivot: Int) {
if (startIndex < pivot) {
let iPivot = qPartition(start: startIndex, pivot)
qSort(start: startIndex, iPivot - 1)
qSort(start: iPivot + 1, pivot)
}
}
qSort(start: 0, self.endIndex - 1)
return self
}
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
var wallIndex: Int = startIndex
//compare range with pivot
for currentIndex in wallIndex..<pivot {
if self[currentIndex] <= self[pivot] {
if wallIndex != currentIndex {
swap(&self[currentIndex], &self[wallIndex])
}
//advance wall
wallIndex += 1
}
}
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
चयन छांटना
चयन प्रकार इसकी सादगी के लिए विख्यात है। यह सरणी में पहले तत्व से शुरू होता है, यह एक न्यूनतम मूल्य (या अधिकतम, क्रमबद्धता के आधार पर) के रूप में मूल्य की बचत करता है। यह तब सरणी के माध्यम से पुनरावृत्त करता है, और रास्ते में मिलने वाले किसी भी अन्य मान से कम मान को बदल देता है। उस न्यूनतम मान को तब सरणी के सबसे बाएं भाग में रखा जाता है और प्रक्रिया को अगले सूचकांक से, सरणी के अंत तक दोहराया जाता है। चयन प्रकार में O (n2) की जटिलता है, लेकिन इसे समकक्ष - चयन प्रकार से धीमा माना जाता है।
func selectionSort() -> Array<Element> {
//check for trivial case
guard self.count > 1 else {
return self
}
//mutated copy
var output: Array<Element> = self
for primaryindex in 0..<output.count {
var minimum = primaryindex
var secondaryindex = primaryindex + 1
while secondaryindex < output.count {
//store lowest value as minimum
if output[minimum] > output[secondaryindex] {
minimum = secondaryindex
}
secondaryindex += 1
}
//swap minimum value with array iteration
if primaryindex != minimum {
swap(&output[primaryindex], &output[minimum])
}
}
return output
}
स्पर्शोन्मुख विश्लेषण
चूंकि हमारे पास चुनने के लिए कई अलग-अलग एल्गोरिदम हैं, जब हम एक सरणी को क्रमबद्ध करना चाहते हैं, तो हमें यह जानना होगा कि यह कौन सा काम करेगा। इसलिए हमें अल्गोरिटम की गति और विश्वसनीयता को मापने की कुछ विधि की आवश्यकता है। यहीं से एसिम्प्टोटिक विश्लेषण अंदर आता है। एसिम्प्टोटिक विश्लेषण एल्गोरिदम की दक्षता का वर्णन करने की प्रक्रिया है क्योंकि उनका इनपुट आकार (n) बढ़ता है। कंप्यूटर विज्ञान में, एसिम्पोटिक्स को आम तौर पर बिग ओ नोटेशन के रूप में जाना जाता है।
- रेखीय समय O (n) : जब सरणी में प्रत्येक आइटम का मूल्यांकन एक फ़ंक्शन के लिए किया जाता है ताकि वह लक्ष्य प्राप्त कर सके, तो इसका मतलब है कि फ़ंक्शन कम प्रभावशील हो जाता है क्योंकि तत्वों की संख्या बढ़ रही है। इस तरह का एक कार्य रैखिक समय में चलने के लिए कहा जाता है क्योंकि इसकी गति इसके इनपुट आकार पर निर्भर है।
- बहुपद समय O (n2) : यदि किसी फ़ंक्शन की जटिलता तेजी से बढ़ती है (जिसका अर्थ है कि किसी फ़ंक्शन के सरणी जटिलता के n तत्वों के लिए n वर्ग है) तो वह कार्य बहुपद में होता है। ये आमतौर पर नेस्टेड लूप के साथ कार्य करते हैं। दो नेस्टेड लूप्स का परिणाम O (n2) जटिलता, तीन नेस्टेड लूप्स परिणाम O (n3) जटिलता, और इसी तरह ...
- लॉगरिदमिक समय हे (लॉग एन): लॉगरिदमिक समय फ़ंक्शन की जटिलता तब कम हो जाती है जब इसके इनपुट का आकार (एन) बढ़ता है। ये प्रोग्रामर के प्रकार हैं जिनके लिए हर प्रोग्रामर प्रयास करता है।
त्वरित क्रमबद्ध - O (n लॉग एन) जटिलता समय
क्विकसॉर्ट उन्नत एल्गोरिदम में से एक है। यह O (n लॉग एन) की एक समय जटिलता की सुविधा देता है और एक विभाजन और जीत की रणनीति को लागू करता है। इस संयोजन के परिणामस्वरूप उन्नत एल्गोरिथम प्रदर्शन होता है। क्विकर पहले एक बड़े सरणी को दो छोटे उप-सरणियों में विभाजित करता है: निम्न तत्व और उच्च तत्व। Quicksort फिर से उप-सरणियों को सॉर्ट कर सकता है।
कदम हैं:
एक तत्व चुनें, जिसे एक धुरी कहा जाता है, सरणी से।
सरणी को फिर से व्यवस्थित करें ताकि धुरी से कम मूल्यों वाले सभी तत्व धुरी से पहले आए, जबकि धुरी की तुलना में अधिक मान वाले सभी तत्व इसके बाद आते हैं (समान मान किसी भी तरह से जा सकते हैं)। इस विभाजन के बाद, धुरी अपनी अंतिम स्थिति में है। इसे विभाजन ऑपरेशन कहा जाता है।
उपरोक्त चरणों को छोटे मानों के साथ तत्वों के उप-सरणी में और अलग-अलग मानों के साथ तत्वों के उप-सरणी में अलग से लागू करें।
mutating func quickSort() -> Array<Element> { func qSort(start startIndex: Int, _ pivot: Int) { if (startIndex < pivot) { let iPivot = qPartition(start: startIndex, pivot) qSort(start: startIndex, iPivot - 1) qSort(start: iPivot + 1, pivot) } } qSort(start: 0, self.endIndex - 1) return self}
म्यूटिंग फ़ेक qPartition (start startIndex: Int, _ pivot: Int) -> इंट {
var wallIndex: Int = startIndex //compare range with pivot for currentIndex in wallIndex..<pivot { if self[currentIndex] <= self[pivot] { if wallIndex != currentIndex { swap(&self[currentIndex], &self[wallIndex]) } //advance wall wallIndex += 1 } }
//move pivot to final position
if wallIndex != pivot {
swap(&self[wallIndex], &self[pivot])
}
return wallIndex
}
ग्राफ, ट्राइ, स्टैक
ग्राफ़
कंप्यूटर विज्ञान में, एक ग्राफ एक अमूर्त डेटा प्रकार है जो गणित से अप्रत्यक्ष ग्राफ और निर्देशित ग्राफ अवधारणाओं को लागू करने के लिए है। एक ग्राफ डेटा संरचना में वर्टिकल या नोड्स या बिंदुओं का एक परिमित (और संभवतः उत्परिवर्तित) सेट होता है, साथ में एक अप्रत्यक्ष ग्राफ के लिए इन वर्टिकल के अनऑर्डिनेट जोड़े के एक सेट या एक निर्देशित ग्राफ के लिए ऑर्डर किए गए जोड़े का एक सेट होता है। इन जोड़े को एक अप्रत्यक्ष ग्राफ़ के लिए किनारों, आर्क, या लाइनों के रूप में जाना जाता है और तीर के रूप में, निर्देशित किनारों, निर्देशित आर्क्स या निर्देशित ग्राफ़ के लिए निर्देशित लाइनें। कोने ग्राफ संरचना का हिस्सा हो सकते हैं, या पूर्णांक सूचकांकों या संदर्भों द्वारा दर्शाए गए बाहरी निकाय हो सकते हैं। एक ग्राफ डेटा संरचना प्रत्येक किनारे को कुछ किनारे मूल्य, जैसे कि प्रतीकात्मक लेबल या एक संख्यात्मक विशेषता (लागत, क्षमता, लंबाई, आदि) के साथ जोड़ सकती है। (विकिपीडिया, स्रोत )
//
// GraphFactory.swift
// SwiftStructures
//
// Created by Wayne Bishop on 6/7/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class SwiftGraph {
//declare a default directed graph canvas
private var canvas: Array<Vertex>
public var isDirected: Bool
init() {
canvas = Array<Vertex>()
isDirected = true
}
//create a new vertex
func addVertex(key: String) -> Vertex {
//set the key
let childVertex: Vertex = Vertex()
childVertex.key = key
//add the vertex to the graph canvas
canvas.append(childVertex)
return childVertex
}
//add edge to source vertex
func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
//create a new edge
let newEdge = Edge()
//establish the default properties
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
print("The neighbor of vertex: \(source.key as String!) is \(neighbor.key as String!)..")
//check condition for an undirected graph
if isDirected == false {
//create a new reversed edge
let reverseEdge = Edge()
//establish the reversed properties
reverseEdge.neighbor = source
reverseEdge.weight = weight
neighbor.neighbors.append(reverseEdge)
print("The neighbor of vertex: \(neighbor.key as String!) is \(source.key as String!)..")
}
}
/* reverse the sequence of paths given the shortest path.
process analagous to reversing a linked list. */
func reversePath(_ head: Path!, source: Vertex) -> Path! {
guard head != nil else {
return head
}
//mutated copy
var output = head
var current: Path! = output
var prev: Path!
var next: Path!
while(current != nil) {
next = current.previous
current.previous = prev
prev = current
current = next
}
//append the source path to the sequence
let sourcePath: Path = Path()
sourcePath.destination = source
sourcePath.previous = prev
sourcePath.total = nil
output = sourcePath
return output
}
//process Dijkstra's shortest path algorthim
func processDijkstra(_ source: Vertex, destination: Vertex) -> Path? {
var frontier: Array<Path> = Array<Path>()
var finalPaths: Array<Path> = Array<Path>()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0
for x in 0..<frontier.count {
let itemPath: Path = frontier[x]
if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}
}
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//preserve the bestPath
finalPaths.append(bestPath)
//remove the bestPath from the frontier
//frontier.removeAtIndex(pathIndex) - Swift2
frontier.remove(at: pathIndex)
} //end while
//establish the shortest path as an optional
var shortestPath: Path! = Path()
for itemPath in finalPaths {
if (itemPath.destination.key == destination.key) {
if (shortestPath.total == nil) || (itemPath.total < shortestPath.total) {
shortestPath = itemPath
}
}
}
return shortestPath
}
///an optimized version of Dijkstra's shortest path algorthim
func processDijkstraWithHeap(_ source: Vertex, destination: Vertex) -> Path! {
let frontier: PathHeap = PathHeap()
let finalPaths: PathHeap = PathHeap()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//construct the best path
var bestPath: Path = Path()
while frontier.count != 0 {
//use the greedy approach to obtain the best path
bestPath = Path()
bestPath = frontier.peek()
//enumerate the bestPath edges
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.enQueue(newPath)
}
//preserve the bestPaths that match destination
if (bestPath.destination.key == destination.key) {
finalPaths.enQueue(bestPath)
}
//remove the bestPath from the frontier
frontier.deQueue()
} //end while
//obtain the shortest path from the heap
var shortestPath: Path! = Path()
shortestPath = finalPaths.peek()
return shortestPath
}
//MARK: traversal algorithms
//bfs traversal with inout closure function
func traverse(_ startingv: Vertex, formula: (_ node: inout Vertex) -> ()) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
var vitem: Vertex = graphQueue.deQueue() as Vertex!
//add unvisited vertices to the queue
for e in vitem.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
/*
notes: this demonstrates how to invoke a closure with an inout parameter.
By passing by reference no return value is required.
*/
//invoke formula
formula(&vitem)
} //end while
print("graph traversal complete..")
}
//breadth first search
func traverse(_ startingv: Vertex) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
vitem!.visited = true
print("traversed vertex: \(vitem!.key!)..")
} //end while
print("graph traversal complete..")
} //end function
//use bfs with trailing closure to update all values
func update(startingv: Vertex, formula:((Vertex) -> Bool)) {
//establish a new queue
let graphQueue: Queue<Vertex> = Queue<Vertex>()
//queue a starting vertex
graphQueue.enQueue(startingv)
while !graphQueue.isEmpty() {
//traverse the next queued vertex
let vitem = graphQueue.deQueue() as Vertex!
guard vitem != nil else {
return
}
//add unvisited vertices to the queue
for e in vitem!.neighbors {
if e.neighbor.visited == false {
print("adding vertex: \(e.neighbor.key!) to queue..")
graphQueue.enQueue(e.neighbor)
}
}
//apply formula..
if formula(vitem!) == false {
print("formula unable to update: \(vitem!.key)")
}
else {
print("traversed vertex: \(vitem!.key!)..")
}
vitem!.visited = true
} //end while
print("graph traversal complete..")
}
}
Trie
कंप्यूटर विज्ञान में, एक ट्राइ, जिसे डिजिटल ट्री और कभी-कभी रेडिक्स ट्री या प्रीफ़िक्स ट्री भी कहा जाता है (जैसा कि वे उपसर्गों द्वारा खोजा जा सकता है), एक प्रकार का खोज ट्री है - एक ऑर्डर किया गया ट्री डेटा स्ट्रक्चर जो डायनामिक सेट या एसोसिएटिव को स्टोर करने के लिए उपयोग किया जाता है सरणी जहां कुंजी आमतौर पर तार होते हैं। (विकिपीडिया, स्रोत )
//
// Trie.swift
// SwiftStructures
//
// Created by Wayne Bishop on 10/14/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
public class Trie {
private var root: TrieNode!
init(){
root = TrieNode()
}
//builds a tree hierarchy of dictionary content
func append(word keyword: String) {
//trivial case
guard keyword.length > 0 else {
return
}
var current: TrieNode = root
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("current has \(current.children.count) children..")
//iterate through child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
break
}
}
//new node
if childToUse == nil {
childToUse = TrieNode()
childToUse.key = searchKey
childToUse.level = current.level + 1
current.children.append(childToUse)
}
current = childToUse
} //end while
//final end of word check
if (keyword.length == current.level) {
current.isFinal = true
print("end of word reached!")
return
}
} //end function
//find words based on the prefix
func search(forWord keyword: String) -> Array<String>! {
//trivial case
guard keyword.length > 0 else {
return nil
}
var current: TrieNode = root
var wordList = Array<String>()
while keyword.length != current.level {
var childToUse: TrieNode!
let searchKey = keyword.substring(to: current.level + 1)
//print("looking for prefix: \(searchKey)..")
//iterate through any child nodes
for child in current.children {
if (child.key == searchKey) {
childToUse = child
current = childToUse
break
}
}
if childToUse == nil {
return nil
}
} //end while
//retrieve the keyword and any descendants
if ((current.key == keyword) && (current.isFinal)) {
wordList.append(current.key)
}
//include only children that are words
for child in current.children {
if (child.isFinal == true) {
wordList.append(child.key)
}
}
return wordList
} //end function
}
(गिटहब, स्रोत )
ढेर
कंप्यूटर विज्ञान में, एक स्टैक एक अमूर्त डेटा प्रकार है जो दो प्रमुख संचालन के साथ तत्वों के संग्रह के रूप में कार्य करता है: पुश, जो संग्रह में एक तत्व जोड़ता है, और पॉप, जो सबसे हाल ही में जोड़े गए तत्व को हटाता है जो अभी तक हटाया नहीं गया था। जिस क्रम में एक स्टैक से तत्व निकलते हैं, वह अपने वैकल्पिक नाम, LIFO (पिछले में, पहले आउट के लिए) को जन्म देता है। इसके अतिरिक्त, एक स्टैकिंग ऑपरेशन स्टैक को संशोधित किए बिना शीर्ष तक पहुंच प्रदान कर सकता है। (विकिपीडिया, स्रोत )
नीचे लाइसेंस जानकारी और मूल कोड स्रोत पर देखें ( github )
//
// Stack.swift
// SwiftStructures
//
// Created by Wayne Bishop on 8/1/14.
// Copyright (c) 2014 Arbutus Software Inc. All rights reserved.
//
import Foundation
class Stack<T> {
private var top: Node<T>
init() {
top = Node<T>()
}
//the number of items - O(n)
var count: Int {
//return trivial case
guard top.key != nil else {
return 0
}
var current = top
var x: Int = 1
//cycle through list
while current.next != nil {
current = current.next!
x += 1
}
return x
}
//add item to the stack
func push(withKey key: T) {
//return trivial case
guard top.key != nil else {
top.key = key
return
}
//create new item
let childToUse = Node<T>()
childToUse.key = key
//set new created item at top
childToUse.next = top
top = childToUse
}
//remove item from the stack
func pop() {
if self.count > 1 {
top = top.next
}
else {
top.key = nil
}
}
//retrieve the top most item
func peek() -> T! {
//determine instance
if let topitem = top.key {
return topitem
}
else {
return nil
}
}
//check for value
func isEmpty() -> Bool {
if self.count == 0 {
return true
}
else {
return false
}
}
}
MIT लाइसेंस (MIT)
कॉपीराइट (c) 2015, वेन बिशप और अर्बटस सॉफ्टवेयर इंक।
इस सॉफ़्टवेयर और संबंधित दस्तावेज़ फ़ाइलों ("सॉफ़्टवेयर") की प्रतिलिपि प्राप्त करने वाले किसी भी व्यक्ति को बिना किसी प्रतिबंध के सॉफ़्टवेयर का उपयोग करने, कॉपी करने, संशोधित करने, मर्ज करने के अधिकार सहित बिना किसी प्रतिबंध के, सॉफ़्टवेयर की अनुमति देने के लिए अनुमति दी गई है , सॉफ्टवेयर की प्रतियों को प्रकाशित, वितरित, उपविषय, और / या बेचने के लिए, और उन व्यक्तियों को अनुमति देने के लिए जिन्हें सॉफ्टवेयर ऐसा करने के लिए सुसज्जित है, निम्न स्थितियों के अधीन:
उपरोक्त कॉपीराइट नोटिस और यह अनुमति नोटिस सॉफ़्टवेयर की सभी प्रतियों या पर्याप्त भागों में शामिल किया जाएगा।
सॉफ़्टवेयर किसी भी प्रकार, किसी भी तरह की वारंटी के बिना "IS" के रूप में प्रदान किया जाता है, जो कि मर्चेंटैबिलिटी के वेरिएंट के लिए सीमित नहीं है, एक आंशिक गरीब और गैर सरकारी संगठन के लिए उपयुक्त है। किसी भी सूची में दिए गए ऑटो या कॉपीराइटर किसी भी क्लैम, डैमेज या अन्य लायबिलिटी के लिए उत्तरदायी नहीं होंगे, जो अनुबंध, टिकट या अन्य वॉइस, किसी भी तरह के एक्शन में हैं, जो सॉफ्टवेयर के उपयोग से संबंधित हैं या उपयोग नहीं कर रहे हैं। सॉफ्टवेयर।
