Introduction

A stack is a linear data structure in programming languages. A graphical explanation of this structure would be a pack of cards piled up one of top of the other. The cards can be referred to as ‘stacked’. The last card is always on top of the stack. Therefore, stacks also follow the common convention of Last In First Out (LIFO) algorithm. However, FIFO (First In First Out) stacks can also be implemented. It mostly depends on the requirement of the work.

Basic Stack Operations

When talking about stacks, 4 basic operations are always implemented. The operations are as follows:

• Push – The Push operation is used when you want to add an element to the stack. Depending upon how you have structured the stack, the new element will either be added to the front or end of the stack. If the stack is already full, a stack overflow message will be displayed.
• Pop – The Pop function is used to eject or remove a member from the stack. Pop is diametrically opposite to Push as these two operations occur at opposite ends of the stack. If the stack is already full, an underflow message will be displayed.
• Peek – This function is mainly to check the top-most element of the stack. Peek returns the top-most element of the stack.
• isEmpty – This returns true if the stack is empty and false if the stack has at least one member.

Time Complexity

Stack is quite an efficient data structure where all the various operations mentioned above (push, pop, peek, isEmpty) take the same amount of time ad the complexity can be valued at O(1).

Implementation of Stacks

A stack is a concept that needs to be implemented using collections of data. There are two ways to implement a stack. You can either use arrays or linked lists. If you use arrays, the data will reside in a contiguous memory location. Linked Lists are more memory efficient but it is easier to work with arrays. The following code uses arrays to implement a stack.

Stack using Arrays in JAVA

class Stack {
static final int len = 1000;
int top;
//Creating a stack
int arr[] = new int [len];
boolean isEmpty ()
{
return (top < 0);
}
//Constructor
Stack()
{
top = -1
}
boolean push (int a)
{
if (top >= (len - 1)) {
System.out.println (“Stack Overflow”);
return false;
}
else {
arr[++top] = a;
System.out.println(a + “added to the stack”);
return true;
}
}
int pop()
{
if (top < 0) {
System.out.println (“Stack Underflow”);
return 0;
}
else {
int a = arr[top--];
return a;
}
}
int peek()
{
if(top < 0) {
System.out.println(“Stack Underflow”);
return 0;
}
else {
int p = arr[top];
return p;
}
}
//Main Class
class StackImplement {
public static void main (String args [])
{
Stack s = new Stack ();
s.push(78);
s.push(34);
s.push(56);
System.out.println(s.pop() + “removed from stack”);
}
}

OUTPUT

78 added to the stack
34 added to the stack
56 added to the stack
56 removed from stack

Stack using Linked List in JAVA

public class StackAsLinkedList {
StackNode root;
static class StackNode {
int data;
StackNode next;
StackNode(int data) {
this.data = data;
}
}
public boolean isEmpty() {
if (root == null) {
return true;
}
else
return false;
}
public void push(int data)
{
StackNode newNode = new StackNode(data);
if (root == null)
{
root = newNode;
}
else
{
StackNode temp = root;
root = newNode;
newNode.next = temp;
}
System.out.println(data + " pushed to stack");
}
public int pop()
{
int popped = Integer.MIN_VALUE;
if (root == null)
{
System.out.println("Stack is Empty");
}
else
{
popped = root.data;
root = root.next;
}
return popped;
}
public int peek()
{
if (root == null)
{
System.out.println("Stack is empty");
return Integer.MIN_VALUE;
}
else
{
return root.data;
}
}
//Main Class
public static void main(String[] args)
{
StackAsLinkedList sll = new StackAsLinkedList();
sll.push(100);
sll.push(200);
sll.push(350);
System.out.println(sll.pop() + " popped from stack");
System.out.println("Top element is " + sll.peek());
}
}

OUTPUT

100 pushed to stack
200 pushed to stack
350 pushed to stack
350 popped from stack
Top element is 200