1

With high hopes I typed with Ada.Containers. to see the autocomplete list, and did not see Stack or anything resembling it listed. Does the Ada standard library really not come with a stack implementation?

On Rosetta Code I found this stack implementation, which is very much lacking as it runs to the allocator for every single node being added.

I feel like there must be some "other Ada standard library" I must be missing out on, as I keep running into basic library features that are apparently missing.

TamaMcGlinn
  • 2,840
  • 23
  • 34

2 Answers2

6

I don't believe I've actually used a stack in 50 years of (mainly real-time, control systems) programming. Part of the reason for there being no standard Ada.Containers.Stacks might be that educators would lose one of the introductory topics in a Data Structures For Beginners course :-)

The AI that introduced the Containers states that

[it] provides a number of useful containers for Ada. Only the most useful containers are provided. Ones that are relatively easy to code, redundant, or rarely used are omitted from this set, even if they are generally included in containers libraries

and that

You can use a vector to implement a stack in the traditional way:

      package Stacks is new Ada.Containers.Vectors (ET);
      use Stacks;

      Stack : Stacks.Vector;

      procedure Push (E : in ET) is
      begin
         Append (Stack, New_Item => E);
      end;

      function Top return ET is
      begin
         return Last_Element (Stack);
      end;

      procedure Pop is
      begin
         Delete_Last (Stack);
      end;

which then gives the opportunity to create bounded stacks and to pre-allocate unbounded stacks if appropriate (i.e. you know the typical maximum depth but want to allow for deeper ones occasionally).

Simon Wright
  • 25,108
  • 2
  • 35
  • 62
  • @TamaMcGinn, I would have rolled that edit back because (a) why not capitalize Stack? (b) "use in anger" => use for a real task, see [here](http://onlineslangdictionary.com/meaning-definition-of/use-in-anger) (c) I don’t think anyone could have spent nearly 50 years programming in Ada. Not sure why it won’t let me. – Simon Wright Jul 02 '20 at 12:46
  • Oh, pardon me! Only just spotted this comment. I believe SO sends the author a notification, but if someone else picks up the review of the edit earlier, then that review stands even if the author was only given 10 minutes to review the edit in the interim - still, you should certainly be allowed to roll back the edit. – TamaMcGlinn Oct 31 '20 at 13:11
  • 1
    Regarding 'use in anger' I was surprised to learn a new phrase as an adult native English speaker. But SO is [supposed to use 'basic English'](https://stackoverflow.design/content/guidelines/principles/) so I would still recommend avoiding the phrase. I honestly thought it was autocompletese for 'Ada'. – TamaMcGlinn Oct 31 '20 at 13:14
4

You can just use Ada.Containers.Vectors.Vector as a stack like you can do in most other programming languages.

  • V.Append (E) is push
  • V.Last_Element is the current top element
  • V.Delete_Last is pop

Generally, stack describes the semantic of a data structure. You can assign this semantic to different kinds of data structures, like dynamic arrays (Vector being one) or linked lists (the solution you linked).

The standard library provides functionality by implementing well-defined, versatile data structures. It is up to you as user to select a data structure that fits your required semantic well.

flyx
  • 35,506
  • 7
  • 89
  • 126
  • 2
    The PragmAda Reusable Components (https://github.com/jrcarter/PragmARC) has both bounded and unbounded stacks. – Jeffrey R. Carter Jun 09 '20 at 08:50
  • @JeffreyR.Carter Your comment would make a fine answer, it doesn't seem to have anything to do with this particular answer you chose to comment on. However, your stack implementation (I couldn't find the bounded version) is static only, i.e. you can't make two stacks. – TamaMcGlinn Jun 09 '20 at 14:27
  • You're right: There are only unbounded stacks. I apologize for the misstatement. There are both bounded and unbounded forms of most data structures, and I forgot that the stacks, being rarely used, lack the bounded form, though that could be easily built atop the bounded list if there were demand for it. As for your assertion that "you can't make two stacks," that is clearly false. Given an instance `Stacks` of one of the stack components, one can declare `S1, S2 : Stacks.Handle;` and have two stacks. – Jeffrey R. Carter Jun 10 '20 at 07:07