Data Structures & Algorithms in Swift: Part 1 — Stack
What is Stack?
Stack is a linear data structure which follows a particular order in terms of which operations are performed (LIFO — Last in first out). It is named as stack because it behaves like any real world stack that you may encounter. For example a stack of books or plates. If you consider a stack of books, we can place a new book or remove a book only from the top of the stack.
Operations on Stack
We will use an array for internal storage of the Stack as it gives us easy methods for adding & removing elements.
PUSH
Pushing an element means adding a new element to the top of the stack.
Since the push operation will just add a new element to the end of the array the time complexity of this operation would be O(1), but just in case if the array is full Swift will create a new array of double size and copy all the elements to it. This would mean that the time complexity in this case would be O(n).
POP
Popping an element means removing the top most element of the stack.
Pop…