
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A stack is a container of elements with   last in, first out   access policy.   Sometimes it also called LIFO.

The stack is accessed through its top.

The basic stack operations are:

   push   stores a new element onto the stack top;
   pop   returns the last pushed stack element, while removing it from the stack;
   empty   tests if the stack contains no elements.


Sometimes the last pushed stack element is made accessible for immutable access (for read) or mutable access (for write):

   top   (sometimes called peek to keep with the p theme) returns the topmost element without modifying the stack.


Stacks allow a very simple hardware implementation.

They are common in almost all processors.

In programming, stacks are also very popular for their way (LIFO) of resource management, usually memory.

Nested scopes of language objects are naturally implemented by a stack (sometimes by multiple stacks).

This is a classical way to implement local variables of a re-entrant or recursive subprogram. Stacks are also used to describe a formal computational framework.

See stack machine.

Many algorithms in pattern matching, compiler construction (e.g. recursive descent parsers), and machine learning (e.g. based on tree traversal) have a natural representation in terms of stacks.



Task

Create a stack supporting the basic operations: push, pop, empty.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


$ include "seed7_05.s7i";
 
const func type: stack (in type: baseType) is func
  result
    var type: stackType is void;
  begin
    stackType := array baseType;
 
    const proc: push (inout stackType: aStack, in baseType: top) is func
      begin
         aStack := [] (top) & aStack;
      end func;
 
    const func baseType: pop (inout stackType: aStack) is func
      result
        var baseType: top is baseType.value;
      begin
        if length(aStack) = 0 then
          raise RANGE_ERROR;
        else
          top := aStack[1];
          aStack := aStack[2 ..];
        end if;
      end func;
 
    const func boolean: empty (in stackType: aStack) is
      return length(aStack) = 0;
  end func;
 
const type: intStack is stack(integer);
 
const proc: main is func
  local
    var intStack: s is intStack.value;
  begin
    push(s, 10);
    push(s, 20);
    writeln(pop(s) = 20);
    writeln(pop(s) = 10);
    writeln(empty(s));
  end func;