Stack Implementation In Java Data Structure

What is stack?

• A stack is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle.

• Objects can be inserted at any time, but only the last (the most-recently inserted) object can be removed.

• Inserting an item is known as “Pushing” onto the stack. “Popping” off the stack is synonymous with removing an item

• Used in Operating system to implement method calls, and in evaluating Expressions.

ADT Stack: Specification

Elements: The elements are of a generic type <Type>. (In a linked implementation an element is placed in a node)

Structure: the elements are linearly arranged, and ordered according to the order of arrival, most recently arrived element is called top.

Domain: the number of elements in the stack is bounded therefore the domain is finite. Type of elements: Stack

Elements: The elements are of a generic type <Type>. (In a linked implementation an element is placed in a node)

Structure: the elements are linearly arranged, and ordered according to the order of arrival, most recently arrived element is called top.

Domain: the number of elements in the stack is bounded therefore the domain is finite. Type of elements: Stack

Operations:

All operations operate on a stack S.

1.Method push (Type e)

requires: Stack S is not full.

input: Type e.

results: Element e is added to the stack as its most recently added elements.

output: none.

2.Method pop (Type e)

requires: Stack S is not empty.

input: none

results: the most recently arrived element in S is removed and its value assigned to e.

output: Type e.

3.Method empty (boolean flag)

input: none

results: If Stack S is empty then flag is true, otherwise false.

output: flag

4.Method Full (boolean flag).

requires:

input: none

results: If S is full then Full is true, otherwise Full is false.

output: flag.

Stack Interface

public interface Stack<T>{
public T pop( );
public void push(T e);
public boolean empty( );
public boolean full( );
}

ADT Stack (Linked-List)

Below the structure of stack implementation

Linked-List: Element

public class Node<T> {
 public T data;
 public Node<T> next;
 
 public Node () {
 data = null;
 next = null;
 }
 
 public Node (T val) {
 data = val;
 next = null;
 }

 // Setters/Getters?
}

Linked-List: Implementation

public class LinkedStack<T> implements Stack<T> {
 private Node<T> top;

 /* Creates a new instance of LinkStack */
 public LinkedStack() {
 top = null;
 }

Linked-List Array Representation

public class ArrayStack<T> implements Stack<L> {
 private int maxsize;
 private int top;
 private T[] nodes;

 /** Creates a new instance of ArrayStack */
 public ArrayStack(int n) {
 maxsize = n;
 top = -1;
 nodes = (T[]) new Object[n];
 }

public boolean empty(){
 return top == -1;
 }

 public boolean full(){
 return top == maxsize - 1;
 }

public void push(T e){
 nodes[++top] = e;
 }
 
 public T pop(){
 return nodes[top--];
 }
}

Applications of Stacks

Some applications of stacks are:

• Balancing symbols.

• Computing or evaluating postfix expressions.

• Converting expressions from infix to postfix.

Contact us to get any help in stack using java data structure at realcode4you@gmail.com and get instant help with an affordable prices.