Stack Abstract Data Type using Ada

The stack Abstract Data Type is one of the simplest data types to create and understand. There are fundamentally two kinds of stack types.

·         bounded stacks which have a pre-determined capacity

·         unbounded stacks which can grow to the limits of computer memory.

Every stack implementation has some common subprograms.

• ·         Is_Empty – This function returns true if the stack is empty and false if it is not empty
• ·         Size – A function returning number of elements currently contained by the stack
• ·         Top – A function returning the top element of a stack that is not empty
• ·         Push – Push a data element onto the stack
• ·         Pop – A procedure that pops the top element off the stack, passing the popped element out as a parameter
• ·         Clear – A procedure that empties the stack
• ·         Display – A procedure that displays the current contents of the stack

A bounded stack may also have the function Is_Full, which returns true if the stack is full and returns false if it is not full. Notice that Is_Empty is not simply the inverse of Is_Full. A bounded stack with a capacity of 10 elements may contain 0 elements, in which case it is empty, or it may contain some number of elements from 1 through 9, in which case it is neither empty nor full, or it may contain 10 elements, in which case it is full.

Unbounded Stack

Unbounded stacks are commonly implemented as specialized linked lists. Every Push operation results in the dynamic allocation of a new item onto the stack. Every Pop operation results in one item from the stack being freed back to the program heap.

The following implementation of an unbounded stack is defined in an Ada generic package, allowing instances of the unbounded stack to be created containing any data type. 

Ada does provide a pre-defined doubly linked list package as part of its standard container library, but this example re-invents a simple singly linked list to give a complete example of how the unbounded stack can be implemented.

The package specification defines the API for the stack abstract data type:

generic    type Element_Type is private;       with function Image (Item : in Element_Type) return String;    package Unbounded_Stack is    type Stack is tagged private;    function Is_Empty (S : in Stack) return Boolean;       function Size (S : in Stack) return Natural;       function Top (S : in Stack) return Element_Type with      Pre => not S.Is_Empty;       procedure Push (S : in out Stack; Value : in Element_Type) with      Post => S.Size = S'Old.Size + 1;       procedure Pop (S : in out Stack; Value : out Element_Type) with       Pre  => not S.Is_Empty,      Post => S.Size = S'Old.Size - 1;       procedure Clear (S : in out Stack) with      Post => S.Is_Empty;       procedure Display (S : Stack);    private       type Cell;       type Cell_Access is access Cell;       type Cell is record       Value : Element_Type;       Next  : Cell_Access;    end record;    type Stack is tagged record       Head  : Cell_Access := null;       Count : Natural     := 0;    end record; end Unbounded_Stack;

The package specification defines two generic parameters which must be specified when an instance of the package is created. The first generic parameter is the data type that the stack will contain. The second generic parameter is a function taking an instance of the stack element type and returning a string representation of the value of that data type.

Several of the functions and procedures have preconditions and/or post-conditions associated with them. These pre and post conditions specify the requirements of those functions and procedures.

Function or Procedure Name	Condition	Description
Top	Pre => not S.Is_Empty	This precondition requires the stack to not be empty before calling the Top function.
Push	Post => S.Size = S'Old.Size + 1	Upon completion of this procedure the size of the stack must increase by 1.
Pop	Pre  => not S.Is_Empty, Post => S.Size = S'Old.Size - 1	This procedure cannot be called when the stack is empty. Upon completion of this procedure the size of the stack must decrease by 1.
Clear	Post => S.Is_Empty	Upon completion of this procedure the stack will be empty.

The private part of the package specification defines the data types needed to implement a linked list.

The package body contains the implementation of all the functions and procedures defined in the package specification.

with Ada.Unchecked_Deallocation; with Ada.Text_IO; use Ada.Text_IO; package body Unbounded_Stack is    procedure free is new Ada.Unchecked_Deallocation (Cell, Cell_Access);    --------------    -- Is_Empty --    --------------    function Is_Empty (S : in Stack) return Boolean is    begin       return S.Count = 0;    end Is_Empty;    ----------    -- Size --    ----------    function Size (S : in Stack) return Natural is    begin       return S.Count;    end Size;    ---------    -- Top --    ---------    function Top (S : in Stack) return Element_Type is    begin       return S.Head.Value;    end Top;    ----------    -- Push --    ----------    procedure Push (S : in out Stack; Value : in Element_Type) is       C : Cell_Access := new Cell;    begin       C.Value := Value;       C.Next  := S.Head;       S.Head  := C;       S.Count := S.Count + 1;    end Push;    ---------    -- Pop --    ---------    procedure Pop (S : in out Stack; Value : out Element_Type) is       C : Cell_Access := S.Head;    begin       Value   := S.Head.Value;       S.Head  := S.Head.Next;       S.Count := S.Count - 1;       free (C);    end Pop;    -----------    -- Clear --    -----------    procedure Clear (S : in out Stack) is       C : Cell_Access := S.Head;    begin       while S.Head /= null loop          C       := S.Head;          S.Head  := S.Head.Next;          S.Count := S.Count - 1;          free (C);       end loop;    end Clear;    -------------    -- Display --    -------------    procedure Display (S : Stack) is       C : Cell_Access := S.Head;    begin       if S.Is_Empty then          Put_Line ("The stack is empty.");       end if;       for I in 1 .. S.Count loop          Put_Line (Image (C.Value));          C := C.Next;       end loop;    end Display; end Unbounded_Stack;

Bounded Stack

The bounded stack is also implemented as a generic package. Instead of using a linked list which can be enlarged with each Push operation, the bounded stack uses an array defined when an instance of the bounded stack is declared.

You will also notice that the Is_Full function has been defined for the bounded stack. Additionally, the Push procedure now has a precondition requiring the stack not to be full when Push is called. The names and interfaces for all other functions and procedures are identical between the bounded stack and the unbounded stack.

generic       type Element_Type is private;       with function Image (Item : in Element_Type) return String;    package Bounded_Stack is       type Stack (Size : Positive) is tagged private;    function Is_Empty (S : in Stack) return Boolean;       function Is_Full (S : in Stack) return Boolean;       function Count (S : in Stack) return Natural;       function Top (S : in Stack) return Element_Type with      Pre => not S.Is_Empty;       procedure Push (S : in out Stack; Value : in Element_Type) with       Pre  => not S.Is_Full,      Post => S.Count = S'Old.Count + 1;       procedure Pop (S : in out Stack; Value : out Element_Type) with       Pre  => not S.Is_Empty,      Post => S.Count = S'Old.Count - 1;       procedure Clear (S : in out Stack) with      Post => S.Is_Empty;       procedure Display (S : in Stack);    private       type Buff_T is array (Positive range <>) of Element_Type;       type Stack (Size : Positive) is tagged record       Buff  : Buff_T (1 .. Size);       Index : Positive := 1;       Tally : Natural  := 0;    end record; end Bounded_Stack;

The implementation of the bounded stack differs from the unbounded stack because stack elements are never dynamically allocated or de-allocated.

with Ada.Text_IO; use Ada.Text_IO; package body Bounded_Stack is    --------------    -- Is_Empty --    --------------    function Is_Empty (S : in Stack) return Boolean is    begin       return S.Tally = 0;    end Is_Empty;    -------------    -- Is_Full --    -------------    function Is_Full (S : in Stack) return Boolean is    begin       return S.Tally = S.Size;    end Is_Full;    -----------    -- Count --    -----------    function Count (S : in Stack) return Natural is    begin       return S.Tally;    end Count;    ---------    -- Top --    ---------    function Top (S : in Stack) return Element_Type is    begin       return S.Buff(S.Index - 1);    end Top;    ----------    -- Push --    ----------    procedure Push (S : in out Stack;  Value : in Element_Type) is    begin       S.Buff(S.Index) := Value;       S.Tally         := S.Tally + 1;       S.Index         := S.Index + 1;    end Push;    ---------    -- Pop --    ---------    procedure Pop (S : in out Stack; Value : out Element_Type) is    begin       S.Tally := S.Tally - 1;       S.Index := S.Index - 1;       Value   := S.Buff(S.Index);    end Pop;    -----------    -- Clear --    -----------    procedure Clear (S : in out Stack) is    begin       S.Tally := 0;       S.Index := 1;    end Clear;    -------------    -- Display --    -------------    procedure Display (S : in Stack) is    begin       if S.Tally = 0 then          Put_Line("The stack is empty.");       else          for I in reverse 1..S.Index - 1 loop             Put_Line(Image(S.Buff(I)));          end loop;       end if;    end Display; end Bounded_Stack;

Since the API for both the bounded and unbounded stack packages are so similar the use of these packages is very similar.

Using the unbounded stack package

with Ada.Text_IO; use Ada.Text_IO; with Unbounded_Stack; procedure Main is    package Int_Stack is new Unbounded_Stack (Integer, Integer'Image);    use Int_Stack;    S : Stack;    V : Integer; begin    Put_Line ("Push 5 values on the stack");    for I in 1 .. 5 loop       S.Push (I);    end loop;    S.Display;    Put_Line ("Pop 2 values off of stack");    for I in 1 .. 2 loop       S.Pop (V);       Put_Line ("Popped value" & V'Image);    end loop;    S.Display;    Put_Line ("The top of the stack is" & S.Top'Image);    S.Clear;    S.Display; end Main;

Using the bounded stack package

with Ada.Text_IO; use Ada.Text_IO; with bounded_stack; procedure Main is    package Int_Stack is new bounded_stack (integer, integer'image);    use Int_Stack;    S : Stack (10);    V : Integer; begin    Put_Line ("Push 5 values on the stack");    for I in 1 .. 5 loop       S.Push (I);    end loop;    S.Display;    Put_Line ("Pop 2 values off of stack");    for I in 1 .. 2 loop       S.Pop (V);       Put_Line ("Popped value" & V'Image);    end loop;    S.Display;    Put_Line ("Push 5 values on the stack");    for I in 1 .. 5 loop       S.Push (I);    end loop;    S.Display;    Put_Line ("The top of the stack is" & S.Top'Image);    S.Clear;    S.Display; end Main;

In the bounded stack instance the variable S is declared to be a stack with a capacity of 10 elements. This is done in the line

S : Stack (10);

The (10) sets the Size parameter of the Stack record to 10 for this instance.