
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


@echo off
setlocal enableDelayedExpansion

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: LIFO stack usage

:: Define the stack
call :newStack myStack

:: Push some values onto the stack
for %%A in (value1 value2 value3) do call :pushStack myStack %%A

:: Test if stack is empty by examining the top "attribute"
if myStack.top==0 (echo myStack is empty) else (echo myStack is NOT empty)

:: Peek at the top stack value
call:peekStack myStack val && echo a peek at the top of myStack shows !val!

:: Pop the top stack value
call :popStack myStack val && echo popped myStack value=!val!

:: Push some more values onto the stack
for %%A in (value4 value5 value6) do call :pushStack myStack %%A

:: Process the remainder of the stack
:processStack
call :popStack myStack val || goto :stackEmpty
echo popped myStack value=!val!
goto :processStack
:stackEmpty

:: Test if stack is empty using the empty "method"/"macro". Use of the
:: second IF statement serves to demonstrate the negation of the empty
:: "method". A single IF could have been used with an ELSE clause instead.
if %myStack.empty% echo myStack is empty
if not %myStack.empty% echo myStack is NOT empty
exit /b

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: LIFO stack definition
 
:newStack stackName
set /a %~1.top=0
:: Define an empty "method" for this stack as a sort of macro
set "%~1.empty=^!%~1.top^! == 0"
exit /b
 
:pushStack stackName value
set /a %~1.top+=1
set %~1.!%~1.top!=%2
exit /b
 
:popStack stackName returnVar
:: Sets errorlevel to 0 if success
:: Sets errorlevel to 1 if failure because stack was empty
if !%~1.top! equ 0 exit /b 1
for %%N in (!%~1.top!) do (
  set %~2=!%~1.%%N!
  set %~1.%%N=
)
set /a %~1.top-=1
exit /b 0
 
:peekStack stackName returnVar
:: Sets errorlevel to 0 if success
:: Sets errorlevel to 1 if failure because stack was empty
if !%~1.top! equ 0 exit /b 1
for %%N in (!%~1.top!) do set %~2=!%~1.%%N!
exit /b 0