New Stack ADT

Related Projects Collections
1

Hello.

Can you consider adding an implementation of Stack data structure.

Stacks are very useful for instance in Search and conquer algorithms using backtracking, Implementing navigation or to keeping track of the "most recently used" feature, Balancing symbols, in Reverse Polish notation, just to mention a few.

Stack implementation will be based on ContiguousArray but will not adapt the Swift Collections protocol just to make it simple to use.
Stack offer only two ways of accessing the data: push and pop.
It will include peek operation just to take a look at the top of the Stack without mutating its contents.

isEmpty and count properties.

And initializers from Sequence and array literal.

Please let me know if you find it interesting

2

So maybe just using ContiguousArray with append() and popLast()?

Then you can just use it as a stack? Or am I missing something?

2 Likes
3

I think the better way to do this is to implement your own custom stack protocol with methods you require that will be applied on a collection. And you should choose your collection depending on situation, yeah it can vary from time to time.

For example in C++ stack is an adaptor that you can apply to your collections like arrays, lists and etc.

4

Hi, thanks you both for your comments. Stack is a very simple structure but perhaps for that reason there are a lot of custom implementations in every code. This is the main purpose of the Stack, to provide only the operations that are necessary and to eliminate the rest that only distort and may break the implicit integrity of the stack.

5

Here is one I’ve used from time to time:

struct Stack<Element> {
    private var storage: [Element] = []

    mutating func push(_ element: Element) {
        storage.append(element)
    }

    mutating func pop() -> Element? {
        storage.popLast()
    }

    mutating func removeAll() {
        storage.removeAll()
    }

    var isEmpty: Bool {
        storage.isEmpty
    }

    var top: Element? {
        storage.last
    }
}

extension Stack: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self.storage = elements
    }
}

But this is probably too simple to warrant inclusion in the Collections package.

1 Like
6

Yes, that's precisely the point. Stack is very simple but its main purpose is that its implementation is always the same and anyone who needs it will have it available.

I agree that it is extremely simple but I think that having this structure provides the same basis for all algorithms and applications to be developed. I do not think that whether it is simple or difficult should be a criterion for deciding whether or not to include it in the library.

Thinks that by using this structure, any modification that implies a performance improvement would be available to all the programs that would have implemented it.

I believe that in this case, the simplest is also the best.
Thanks for your answer.

2 Likes
7

Hello friends. Thanks for your comments. Now I think I have a better idea about the type of work being done in this group. My intention was to help other people programming common tasks. I will try to have in the future better ideas and more aligned with the objective

8

I agree with Joakim. We already have a great stack implementation in the Swift Standard Library: it is called Array. Introducing a new wrapper type that simply maps directly to a restricted subset of Array's API does not seem like a desirable addition to the Collections package.

Although simple API adapter types are very useful engineering tools that document expectations and guide usage, I don't think we need to standardize them -- I feel they work best when individually created as needed, specifically tailored for each individual case. I think it's a good idea to routinely create such new types as a matter of habit. I believe collecting them into a central package would be avoiding their true benefits.

3 Likes