4.1 Stack Abstract Data Type

You might have seen a "stack" of food plates kept one above the other as shown in the diagram below

We can see that the first plate kept on the table is usually the last one to be used (Unless somebody decides to pull the last plate first and damage the remaining ones!) The final plate kept on the top of others is usually the first one to be reused to serve food.

In computer science we also have a similar data structure whose name also resonates the same phenomenon. This data structure is called the stack.

A stack is a last-in first-out or LIFO list because the last element to be "pushed" on the stack will be the first one to be "popped" out. Only one element can be accessed in a stack at any given point of time - the most recently inserted element onto the stack.

To be more specific, a stack is a data structure with the property that only the top element of the stack is accessible. In a stack, the top element is the data value that was most recently stored on the stack. LIFO is the name of the storage policy used for stacks.

Stack is also used in programming languages during program execution. A stack stores information about the parameters and return points for all the methods that are currently being executed.

Specifications of the Stack Abstract Data Type

Since a stack allows the access to the top element only, we can perform only the following operations : peek,pop, push and test for an empty stack. Peek means to inspect the top element. Pop means to retrieve the top element. The method push means to insert a new element at the top of the stack. The method isEmpty() is used to test for an empty stack while the method size() returns the total number of elements in the stack. The table below is a snapshot of all the operations possible for a Stack ADT.

Stack Methods	Behaviour
boolean isEmpty()	Returns true if the stack is empty; otherwise, returns false
E peek()	Returns the element at the top of the stack without removing it
E pop()	Returns the element at the top of the stack and removes it
E push(E obj)	Pushes an element onto the top of the stack and returns theelement pushed
int size()	Returns the number of elements in the stack

We will name the Stack interface as Stack<E>

The Java implementation for this interface is implemented below.

/**
 *  A Stack is a data structure in which objects are inserted into
    and removed from the same end (i.e., Last-In, First-Out).
    @param <E> The element type denoted by the generic parameterised type E,
    which allows a stack to contain elements of any specific reference type

 * Created by Ganesh.r.hegde on 07-Apr-18.
 */
public interface Stack<E> {

    /**Pushes an element onto the top of the stack and returns the item pushed.
     *
     * @param i The element to be inserted
     * @return The element inserted
     */
    E push(E i);


    /**
     * Returns the element at the top of the stack without removing it.
     * @post The stack remains unchanged
     * @return The element at the top of the stack
     */
    E peek();

    /**
     * Returns the number of elements in the stack
     * @return The number of elements in the stack
     */
    int size();


    /**
     * Returns the object at the top of the stack and removes it.
     * @post The stack reduces by one in size
     * @return The element at the top of the stack (or null if empty)
     */
    E pop();


    /**
    * Returns true if the stack has no elements or false otherwise
    * @return true if the stack is empty or else returns false
    */
    boolean isEmpty();
}

EXAMPLE 4.1

Let us consider a stack of fruit names of type Stack<String>

4.1 Stack Abstract Data Type