
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


' FB 1.05.0 Win64
 
' stack_rosetta.bi
' simple generic Stack type
 
#Define Stack(T) Stack_##T
 
#Macro Declare_Stack(T)
Type Stack(T)
 Public:
    Declare Constructor()
    Declare Destructor()
    Declare Property capacity As Integer
    Declare Property count As Integer 
    Declare Property empty As Boolean
    Declare Property top As T 
    Declare Function pop() As T   
    Declare Sub push(item As T)
  Private:
    a(any) As T 
    count_ As Integer = 0  
    Declare Function resize(size As Integer) As Integer    
End Type
 
Constructor Stack(T)()
  Redim a(0 To 0) '' create a default T instance for various purposes 
End Constructor
 
Destructor Stack(T)()
  Erase a
End Destructor
 
Property Stack(T).capacity As Integer
  Return UBound(a)
End Property
 
Property Stack(T).count As Integer
  Return count_
End Property
 
Property Stack(T).empty As Boolean
  Return count_ = 0
End Property
 
Property Stack(T).top As T
  If count_ > 0 Then
    Return a(count_)
  End If
  Print "Error: Attempted to access 'top' element of an empty stack"
  Return a(0)  '' return default element 
End Property
 
Function Stack(T).pop() As T
  If count_ > 0 Then
    Dim value As T = a(count_)
    a(count_) = a(0)  '' zero element to be removed
    count_ -= 1
    Return value
  End If
  Print "Error: Attempted to remove 'top' element of an empty stack"
  Return a(0)  '' return default element
End Function
 
Sub Stack(T).push(item As T)
  Dim size As Integer = UBound(a)
  count_ += 1
  If count_ >  size Then
    size = resize(size)
    Redim Preserve a(0 to size)
  End If
  a(count_) = item   
End Sub
 
Function Stack(T).resize(size As Integer) As Integer
  If size = 0 Then
    size = 4
  ElseIf size <= 32 Then
    size  = 2 * size
  Else
    size += 32
  End If
  Return size
End Function
 
#EndMacro