Stack and Queue in Swift. Palindrome Test App

Theory of Stack and Queue

Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the stacks following operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top.

Queue is a container of objects that are inserted and removed according to the first-in first-out (FIFO) principle. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue following operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item.

Definitions getting from https://www.cs.cmu.edu

Task 

Determine that a given string is a palindrome. A palindrome is a phrase which reads the same backward and forward.

Algorithm

Version 1

1. First loop. For each character symbol of string add to queue and to stack.
2. Second loop. From 0 to N - 1 (where N = length of string) get symbol  from queue and from stack (when queue we get symbol from begin, when stack we get symbol from end) and compare them. Because if any pair is not equals then it is not palindrome.

Version 2
We can improve this algorithm. Not check the whole word but only half of it, because it will be enough for determine palindrome.

Implementation

Queue Implementation

import Foundation

// FIFO - First In First Out
class Queue {
    var arr: [Character]
    
    init() {
        self.arr = [Character]()
    }
    
    // add new element to queue
    func enqueue(ch: Character) -> Void {
        self.arr.append(ch)
    }
    
    // get the head of queue - the first element
    func peek() -> Character? {
        return self.arr.first
    }
    
    // get the first element and remove it from queue
    func dequeue() -> Character {
        return self.arr.removeFirst()
    }
}

Stack Implementation

import Foundation

// LIFO - Last In First Out
class Stack {
    var arr: [Character]
    
    init() {
        self.arr = [Character]()
    }
    
    // get the head of stack - the last element
    func peek() -> Character? {
        return self.arr.last
    }
    
    // get the last element from the stack and remove it form stack
    func pop() -> Character {
        return self.arr.removeLast()
    }
    
    // add new element to the stack
    func push(ch: Character) -> Void {
       self.arr.append(ch)
    }
    
}

Checking for Palindrome

@IBAction func checkButtonTapped(_ sender: UIButton) {
    if let str = textField.text, str.count > 0 {
        let count = str.count
        var isPalindrome = true
        let queue = Queue()
        let stack = Stack()
        for ch in str {
            queue.enqueue(ch)
            stack.push(ch)
        }
        for _ in 0...(count - 1) {
            if queue.dequeue() != stack.pop() {
                isPalindrome = false
                break
            }
        }
            
        if isPalindrome {
            resultLabel.text = "Palindrome Found!"
        } else {
            resultLabel.text = "NOT Palindrome!"
        }
    } else {
        resultLabel.text = "Empty String"
    }
}

Checking for Palindrome(Improved - Check only half of word)

@IBAction func checkButtonTapped(_ sender: UIButton) {
    if let str = textField.text, str.count > 0 {
        let count = str.count
        var isPalindrome = true
        let queue = Queue()
        let stack = Stack()
        for ch in str {
            queue.enqueue(ch)
            stack.push(ch)
        }
        for _ in 0...(count / 2) {
            if queue.dequeue() != stack.pop() {
                isPalindrome = false
                break
            }
        }
            
        if isPalindrome {
            resultLabel.text = "Palindrome Found!"
        } else {
            resultLabel.text = "NOT Palindrome!"
        }
    } else {
        resultLabel.text = "Empty String"
    }
}

Results

Results - Not Palindrome

Results - Palindrome

Source Code

Source code for this demo project can be found here: PalindromeTest