Stack Data Type#

A Stack is a simple data type that abstracts the idea of a stack of blocks[1], delicious ice-cream[2], or a stack of plates[3]:

A stack of blocks Four scoops of ice cream A stack of plates

The items that are used to build a Stack are all homogeneous, of the same data type. Access to a Stack is only at the top:

  • see the item on the top (peek)

  • place a new item on the top (push)

  • remove an item from the top (pop)

  • see whether the stack is empty (empty).

If we were to pull the first yellow plate straight out of the stack, the green and grey plates would likely be smashed. All activity on the stack must happen at the top. To get the first grey plate, we would need to take off the top green plate and only then take off the top grey plate.

The last item that gets placed onto the stack must be the first item that gets taken out of the stack. That is: stacks are Last In First Out (LIFO) data structures. Sometimes stacks are also called First In Last Out (FILO).

Some versions of stacks contain extra methods such as isFull for determining whether there is still room for more items and search to determine where an item is within the Stack.

Java Stack Library#

We can find the Java documentation for our version of Java online, just as for any of the libraries that come as expansions to Java’s base. Check the Stack library. Here is the most essential portion of the Java Stack ADT:

The Java Stack ADT
This is enough to start using stacks. We know, “in the background,” that there must be either an array or a linked list to handle the storage of the items, but that is really none of our concern as long as we are not writing a life-critical application. We simply make stacks by creating a `Stack` with the constructor, and then we use the stack by sending dot messages to our object.



OOPs Pattern

  • Import the data type, i.e. the library.

  • Make an object of the data type.

  • Send messages to the object.