
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


dim stack$(10)   ' stack of ten
global stack$
global stackEnd
 
for i = 1 to 5                                      ' push 5 values to the stack
 a$ = push$(chr$(i + 64))
 print "Pushed ";chr$(i + 64);" stack has ";stackEnd
next i
 
print "Pop Value:";pop$();" stack has ";stackEnd  ' pop last in
print "Pop Value:";pop$();" stack has ";stackEnd  ' pop last in
 
e$ = mt$()                                        ' MT the stack
print "Empty stack. stack has ";stackEnd
 
' ------ PUSH the stack
FUNCTION push$(val$)
stackEnd = stackEnd + 1                            ' if more than 10 then lose the oldest
if stackEnd > 10 then
   for i = 0 to 9
      stack$(i) = stack$(i+1)
   next i
   stackEnd   = 10
end if
stack$(stackEnd) = val$
END FUNCTION
 
' ------ POP the stack -----
FUNCTION pop$()
if stackEnd = 0 then 
   pop$     = "Stack is MT"
  else
   pop$     = stack$(stackEnd)                        ' pop last in
   stackEnd = max(stackEnd - 1,0)
end if
END FUNCTION
 
' ------ MT the stack ------
FUNCTION mt$()
  stackEnd = 0
END FUNCTION