Phabstractic: Stack Data Type

asherwunk/phabstractic now implements a stack data type (an extension of AbstractList implementing ListInterface)

Stack

I quote Wikipedia in my explanation of a stack data structure:

In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out). Additionally, a peek operation may give access to the top without modifying the stack.

Stacks are extremely useful abstract data types.  They are implemented in many programming languages, and sometimes even make up the core of the programming language (such as PostScript, a language I learned when I worked at the financial statement printing firm).  They are so useful they are often implemented in hardware for various purposes, and even in virtual machines such as the Java Virtual Machine.  One application they have is in syntax parsing and expression evaluation for constructions such as interpreters and compilers.

A stack can be visualized as the following (also from Wikipedia):

ListInterface

First Stack inherits from AbstractList and thus implements ListInterface (github):

NOTE – ::top() is like ::peek() as reference in Wikipedia.

AbstractList

As noted Stack inherits from AbstractList (github):

Stack Specifics

We implement the Stack LIFO by simply using an array in PHP.  This array grows and shrinks accordingly.  We mostly just wrap functionality around the idea that the last element of the internal array is the top of the stack.  Doing that, it’s simply a matter of pushing and popping an array using the built-in PHP array functions.  A function of interest, however, would be exchange and roll:

These are functions inspired from PostScript, which is where this class found inspiration.

Something to note about indexing that’s very important.  We don’t index from the beginning of the private array, we index from the end of the array as if we’re delving into the stack. You can observe this here:

We also define a bottom method as well as a top method.

A nice thing about concrete implementation is you can do things like implement \ArrayAccess.  Note that ArrayAccess methods index using the index() method, which accesses the private array from the end (see above):

Conclusion

Stacks are very important pieces of code.  They are used in numerous many places including parsing syntax trees, calling subroutines, managing memory, and artificial intelligence.  The ability to ‘remember’ state as you put and pull states off the stack is essential in being able to operate on memory.

(View on GitHub)

This is part of the Phabstractic Library.

If you appreciate my programming please help support me through my Patreon.

photo credit: Reynisdrangar via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: