Stack
A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages.
It is named stack because it has the similar operations as the real-world stacks, for example – a
pack of cards or a pile of plates, etc.
The stack follows the LIFO (Last in - First out) structure where the last element inserted would be
the first element deleted.
Stack Representation
A Stack ADT allows all data operations at one end only. At any given time, we can only access
the top element of a stack.
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations on Stacks
Stack operations usually are performed for initialization, usage and, de-initialization of the stack
ADT.
The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the status
of the stack.
Stack uses pointers that always point to the topmost element within the stack, hence called as
the top pointer.
Insertion: push()
push() is an operation that inserts elements into the stack. The following is an algorithm that
describes the push() operation in a simpler way.
Algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.
Example
import [Link].*;
import [Link].*;
public class StackExample {
public static void main (String[] args) {
Stack<Integer> stk = new Stack<Integer>();
// inserting elements into the stack
[Link](52);
[Link](19);
[Link](33);
[Link](14);
[Link](6);
[Link]("The stack is: " + stk);
}
}
Output
The stack is: [52, 19, 33, 14, 6]
Deletion: pop()
pop() is a data manipulation operation which removes elements from the stack. The following
pseudo code describes the pop() operation in a simpler way.
Algorithm
1 − Checks if the stack is empty.
2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.
Example
import [Link].*;
import [Link].*;
public class StackExample {
public static void main (String[] args) {
Stack<Integer> stk = new Stack<Integer>();
// Inserting elements into the stack
[Link](52);
[Link](19);
[Link](33);
[Link](14);
[Link](6);
[Link]("The stack is: " + stk);
// Deletion from the stack
[Link]("\nThe popped element is: ");
Integer n = (Integer) [Link]();
[Link](n);
}
}
Output
The stack is: [52, 19, 33, 14, 6]
The popped element is: 6
peek()
The peek() is an operation retrieves the topmost element within the stack, without deleting it. This
operation is used to check the status of the stack with the help of the top pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END
Example
import [Link].*;
import [Link].*;
public class StackExample {
public static void main (String[] args) {
Stack<Integer> stk = new Stack<Integer>();
// inserting elements into the stack
[Link](52);
[Link](19);
[Link](33);
[Link](14);
[Link](6);
[Link]("The stack is: " + stk);
Integer pos = (Integer) [Link]();
[Link]("\nThe element found is " + pos);
}
}
Output
The stack is: [52, 19, 33, 14, 6]
The element found is 6
isFull()
isFull() operation checks whether the stack is full. This operation is used to check the status of the
stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END
Example
import [Link].*;
public class StackExample {
private int arr[];
private int top;
private int capacity;
StackExample(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
public void push(int key) {
if (isFull()) {
[Link]("Stack is Full\n");
return;
}
arr[++top] = key;
}
public static void main (String[] args) {
StackExample stk = new StackExample(5);
[Link](1); // inserting 1 in the stack
[Link](2);
[Link](3);
[Link](4);
[Link](5);
[Link]("Stack Full? " + [Link]());
}
}
Output
Stack Full? true
isEmpty()
The isEmpty() operation verifies whether the stack is empty. This operation is used to check the
status of the stack with the help of top pointer.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
Example
import [Link].*;
import [Link].*;
public class StackExample {
public static void main (String[] args) {
Stack<Integer> stk = new Stack<Integer>();
// Inserting elements into the stack
[Link](52);
[Link](19);
[Link](33);
[Link](14);
[Link](6);
[Link]("Stack empty? "+ [Link]());
}
}
Output
Stack empty? false