Make writing a habit together! This is the second day of my participation in the “Gold Digging Day New Plan · April More text challenge”. Click here for more details.

What is a stack

A stack is a linear data structure that is often used to store a series of elements of the same type.

It is very similar to an array or queue, except in the order in which elements are added or removed. For the stack, it is Last In First Out order, that is, Last In First Out – LIFO.

To understand the stack, you can imagine a situation: you have a pile of books on your desk, and the book on top of the pile must be the last one to be placed on it. And if you want to read one of them, you pick it up from the top, book by book. This structure corresponds to the stack structure.

Now that you understand what a stack is, let’s look at what functions you need to implement to implement a stack.

Functions that need to be implemented

Func isEmpty() -> Bool // whether the stack isEmpty func count() -> Int // how many elements are in the stack func push(_ newElement: Func pop() -> Element? Func top() -> Element? Func removeAll() // removeAll elements from the stackCopy the code

Because in Swift, Array actually provides the same function as stack. So, this time we’re using Array to store data underneath.

Full implementation of stack:

class Stack<Element: Equatable> { private var _content = [Element]() func isEmpty() -> Bool { return _content.isEmpty } func count() -> Int {  return _content.count } func push(_ newElement: Element) { _content.append(newElement) } func pop() -> Element? { guard count() > 0 else { return nil } return _content.popLast() } func top() -> Element? { guard count() > 0 else { return nil } return _content.last } func removeAll() { _content.removeAll() } }Copy the code

Code explanation:

  • IsEmpty /count/removeAll calls the corresponding Array implementation directly.
  • Push: Adds elements at the top of the stack, corresponding to the end of the Array, so call Append to add elements.
  • Pop: To remove the element at the top of the stack, call popLast of Array to remove the element at the bottom.
  • Top: Retrieves the element at the top of the stack. The last property of the Array returns the last element of the Array.

While Array in Swift is powerful, encapsulating a stack with it yourself is not farting. In my opinion, if I use Array instead of stack, I will often make some mistakes because of the deviation of popLast for push and pop. For example, pop calls removeFirst in a moment of confusion, resulting in some silly errors.

Classic topic

Valid parentheses

LeetCode, here is the link.

This problem is solved with the help of last in, first out of the stack:

  • We first use hash tables to store three types of parentheses:let dict = ["(":")", "[":"]", "{":"}"].
  • Iterate over the current string:
    • If the current character is an open parenthesis, it is pushed.
    • If the current character is a close parenthesis, the top element of the stack is removed.
      • If the stack is empty, the current closing bracket is redundant and returns false.
      • Checks whether the removed top element matches the current bracketed element. If not, return false.
      • If a match is matched, the traversal continues.
  • If the string is iterated:

* If the stack is not empty, there are extra open parentheses, return false.

Code implementation:

let dict = ["(":")", "[":"]", "{":"}"] func isValid(_ s: String) -> Bool { let stack = Stack<String>() for char in s { let subStr = String(char) if dict.keys.contains(subStr) { stack.push(subStr) } else if stack.isEmpty() || dict[stack.pop()!] ! = subStr { return false } } return stack.isEmpty() }Copy the code