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.
Comentários