Stack Data Structure in Java

Author:
A stack is an ordered list in which insertion and deletion are done at one end, called a top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First Out (LIFO) or First in Last Out (FILO) list.

Stack Real-World Examples

1.  In the below diagram, the first image shows a container filled with balls we will try to always take the last inserted ball so it is a last in first out. The second image is a list of mail envelopes and most people will always take the topmost envelope and then the second top etc.
Stack Data Structure Overview

2. A pile of plates in a cafeteria is a good example of a stack. The plates are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is taken from the top of the stack. The first plate placed on the stack is the last one to be used.

Let us first familiarize ourselves with a few concepts that are used in stack implementation.

Stack Concepts

  1. When an element is inserted in a stack, the concept is called a push.
  2. When an element is removed from the stack, the concept is called pop.
  3. Trying to pop out an empty stack is called underflow (treat as Exception).
  4. Trying to push an element in a full stack is called overflow (treat as Exception).

Main Stack operations

Push Operation

The process of putting a new data element onto the stack is known as a Push Operation.
Push operation involves a series of steps −

Step 1 − Check if the stack is full.

Step 2 − If the stack is full, produce an error and exit.

Step 3 − If the stack is not full, increment the top to a point next empty space.

Step 4 − Add data element to the stack location, where the top is pointing.

Step 5 − Returns success.
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of the pop() operation, the data element is not actually removed, instead, top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data elements and deallocates memory space.

A Pop operation may involve the following steps −

Step 1 − Check if the stack is empty.

Step 2 − If the stack is empty, produce an error and exit.

Step 3 − If the stack is not empty, access the data element at which the top is pointing.

Step 4 − Decreases the value of the top by 1.

Step 5 − Returns success.

Auxiliary stack operations

  • int top(): Returns the last inserted element without removing it.
  • int size(): Returns the number of elements stored in the stack.
  • int isEmptyStack(): Indicates whether any elements are stored in the stack or not.
  • int isFullStack(): Indicates whether the stack is full or not.

Stack Implementation in Java

There are many ways of implementing Stack; below are the commonly used methods.
  1. Stack Implementation using Array in Java
  2. Dynamic Stack Implementation using Array in Java
  3. Stack Implementation using Linked List in Java
  4. Stack Implementation using Array List
Click on each link to navigate to a separate dedicated blog post to implement Stack.

Applications of Stack

Following are some of the applications in which stacks play an important role.

Direct applications

  • Balancing of symbols
  • Infix-to-postfix conversion
  • Evaluation of postfix expression
  • Implementing function calls (including recursion)
  • Finding of spans (finding spans in stock markets, refer to Problems section)
  • Page-visited history in a Web browser [Back Buttons]
  • Undo sequence in a text editor
  • Matching Tags in HTML and XML

Indirect applications

  • Auxiliary data structure for other algorithms (Example: Tree traversal algorithms)
  • Component of other data structures (Example: Simulating queues, Queues)

Comments

Post a Comment

Leave Comment