This is the 12th day of my participation in Gwen Challenge

Data structures and algorithms – stacks

How to understand “stack”?

A Stack, “Stack,” is like an array, but with limited functionality. The stack provides LIFO or LIFO. The last element to advance is the first element to be pushed out. (Very similar to the data structure, the queue is FIFO, or first in, first out.)

There is an example in daily life, for example, we put a mule plate at home. When we put the plate, we put it one by one from bottom to top, and when we get it, we also take it one by one from top to bottom. You can’t just pull it out of the middle; Last come out, first come out, this is the typical stack structure;

features

In terms of the operation characteristics of the stack, it is an “operation-constrained” linear table, allowing only insertion and deletion of data at one end.

thinking

Compared with data and linked lists, the data structure of stack only brings me limitations and no advantages. Why not just use arrays or linked lists? Why use this operation-constrained stack?

In fact, data and linked lists do provide a functional alternative to stacks. But you know, a particular data structure is an abstraction of a particular scenario. In addition, arrays and linked lists expose too many interfaces for operation. The operation is indeed flexible and free, but it is not controllable when used, and naturally it is more prone to error.

When a data set involves only inserting and deleting data at one end, and meets the last in, first out, first in, last out characteristics, we should prefer the stack data structure.

Swift implements a stack structure

Let’s use our old friend, Playground

Through array data structures: push, POP and PEEK methods

struct Stack<Element> {
    fileprivate var array:[Element] = []
    
    mutating func push(_ element:Element) {
        array.append(element)
    }
    
    mutating func pop(a)-> Element? {
        return array.popLast()
    }
    
    func peek(a)-> Element? {
        return array.last
    }
}

extension Stack: CustomStringConvertible {
    var description: String {
        let topDivider = "-----Stack---\n"
        let bottomDivider = "\n----------\n"
        // Review the previous simplification of trailing closures
        var list = array.map{ e in 
            return "\(e)"
        }
        var list2 = array.map{"\ [$0)"}
        let stackElements = list2.reversed().joined(separator: "\n")
        return topDivider + stackElements + bottomDivider
    }
}

var bookStack = Stack<String>()
bookStack.push(Journey to the West)
bookStack.push(Romance of The Three Kingdoms)
bookStack.push(A Dream of Red Mansions)
bookStack.push("Golden Vase plum")

print(bookStack)

/** -----Stack-- Jin Ping Mei A Dream of the Red Chamber ---------- */

extension Stack {
    var isEmpty: Bool {
        return array.isEmpty
    }
    var count : Int {
        return array.count
    }
}

Copy the code

Reference:

Segmentfault.com/a/119000001…

www.jianshu.com/p/f76e7d9aa…

How to implement browser forward and backward functions?