Skip to main content

Stacks

What is a Stack?
A Stack ADT is an ordered list in which insertion and deletion are done at the top end of the list.
A stack follows LIFO(Last In First Out) Principle i.e, the last element inserted is the first one to be deleted.

Why do we need Stack?
Well, in many algorithms you want to add objects to a temporary list at some point and then pull them off this list again at a later time. Often the order in which you add and remove these objects matters.

Applications of Stack
  • Balancing of symbols
  • Infix-to-Postfix conversion
  • Evaluation of postfix expression
  • Implementing function calls(Recursive)
  • Forward and Backward feature in a browser.
  • Redo & Undo sequence in a text editor.
  • Matching tags in HTML & XML.
  • Used in other algorithms like Tree traversal, Tower of Hanoi, Stock span, N Queens, etc.

Stack Operations
Main stack operations
Push: Inserts data onto stack
Pop: Removes and returns the last inserted element from the stack.

Auxiliary stack operations
Top: Returns the last element without removing it.
isEmpty: Indicates whether any elements are stored in a stack or not.
isFull: Indicates whether the stack is full or not.


Implementation
  • Array
  • Linked list
1. Stack using Array

public struct Stack<T> {
    
  /// Datastructure consisting of a generic item.
  fileprivate var array = [T]()

  /// The number of items in the stack.
  public var count: Int {
    return array.count
  }

  /// Verifies if the stack is empty.
  public var isEmpty: Bool {
    return array.isEmpty
  }

  /**
     Pushes an item to the top of the stack.
     
     - Parameter element: The item being pushed.
  */
  public mutating func push(_ element: T) {
    array.append(element)
  }

  /**
     Removes and returns the item at the top of the stack.
     
     - Returns: The item at the top of the stack.
  */
  public mutating func pop() -> T? {
    return array.popLast()
  }

  /// Returns the item at the top of the stack.
  public var top: T? {
    return array.last
  }
}
Space Complexity for n push operations O(n)
Time Complexity of Push() O(1)
Time Complexity of Pop() O(1)
Time Complexity of isEmpty() O(1)
Time Complexity of isFull() O(1)
Time Complexity of top() O(1) // Array.last = O(1)
Time Complexity of size()O(1) // Array.count = O(1)

2. Stack using LinkedList

public final class LinkedStack<T>{
    
    /// Linked List's Node Class De claration
    public class LinkedListNode<T> {
        var value: T
        var next: LinkedListNode?
        
        public init(value: T) {
            self.value = value
        }
    }
    
    /// Typealiasing the node class to increase readability of code
    public typealias Node = LinkedListNode<T>
    
    
    /// The head of the Linked List
    private(set) var head: Node?
    
    /// Computed property to iterate through the linked list and return the last node in the list (if any)
    public var top: T? {
        guard let node = head else {
            return nil
        }
        return node.value
    }
    
    /// Computed property to check if the linked list is empty
    public var isEmpty: Bool {
        return head == nil
    }
    
    /// Computed property to iterate through the linked list and return the total number of nodes
    public var count: Int {
        guard var node = head else {
            return 0
        }
        
        var count = 1
        while let next = node.next {
            node = next
            count += 1
        }
        return count
    }
    /// Append a value to the end of the list
    ///
    /// - Parameter value: The data value to be appended
    public func push(_ value: T) {
        let newNode = Node(value: value)
        newNode.next = head
        head = newNode
    }
    
    /// remove last element from the list and return it's value
    @discardableResult public func pop() -> T {
        precondition(!isEmpty)
        var current = head
        defer {
            current = nil
        }
        
        head = current?.next
        return current!.value
    }
    
    /// Function to remove all nodes/value from the list
    public func deleteStack() {
        head = nil
    }
}

Space Complexity for n push operationsO(n)
Time Complexity of Push() O(1)
Time Complexity of Pop() O(1)
Time Complexity of isEmpty() O(1)
Time Complexity of top()O(1)
Time Complexity of deleteStack() O(1)

Comments

Popular posts from this blog

UIAlertController made easy

Once I read somewhere on the internet, creating an Alert in IOS is comparatively harder than JavaScript. I'm not a big fan of HTML & CSS, but I do know a little Javascript, creating an Alert popup in Javascript is pretty much easier, just like this. alert("I am an alert box!"); That's all it takes to create an alert using JS. If you want to try other types of popups using JS, check out here.
But, let's try with Swift. let alertVC = UIAlertController(title: "Alert", message: "Testing", preferredStyle: .alert) let okAction = UIAlertAction(title: "OK", style: .default, handler: nil) alertVC.addAction(okAction) Looking at the above, IOS needs a little extra code, doesn't it? But, that's not the end, let's make it lesser, reusable and better. How about this? alert(title: "Alert", message: "Auto dismiss in 4 sec") I've written an extension for UIViewController, which uses just the above…

Stack Problem - Balancing of Symbols

Stack Problem - Balancing of Symbols
Problem: Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.

Example:
Input: exp = “[()]{}{[()()]()}”
Output: Balanced Input: exp = “[(])”
Output: Not Balanced
Algorithm:
Create a stack.while ( end of input is not reached ) {If the character read is not a symbol to be balanced, ignore it.If the character is an opening delimiter like ( , {  or [ , PUSH it into the stack.If it is a closing symbol like ) , } , ] , then if the stack is empty report an error, otherwise POP the stack.If the symbol POP-ed is not the corresponding delimiter, report an error.At the end of the input, if the stack is not empty report an error.Implementation :
func balancingOfSymbols(string:String)->Bool{ guard string.count > 0else { return false } let symbols:[Character:Character] = ["{":"}","[":"]","(":")",] v…

Design Patterns in Swift

What is a Design pattern?
A design pattern is a general solution to a real-world problem that can be re-used.
Design patterns are formalized best practices that the programmer can use to solve common problems when designing an application or system.
They are templates designed to help us write efficient code which is easy to understand, also can be re-used.
It is not a finished design that can be transformed directly into source or machine code.

Why do we need Design patterns?
Saves Time: Design patterns can speed up the development process by providing tested, proven development paradigmsFuture bugs: Effective design pattern can solve issues that may not become visible until later in the implementation, which helps while designing software.Re-use: Reusing design patterns helps to prevent subtle issues that can cause major problems.Code Readability: Improves code readability for coders and architects familiar with the patterns. Best practices: Design patterns teaches us some of the best pra…