Stack is one of the most used data structures in computer science. It is a linear data structure which supports ordering of elements in Last In First Out order(LIFO).

The very typical real world example is a stack of plates, where new plates are put on the top of the existing ones and the top ones are the first one to be removed.

There are numerous applications which involve stack in computer science, some of them are,

- Compilers/Run time environments, which use it to store recursive calls.
- Tree Traversals
- Software Applications which provide Undo/Redo operations like text editors.
- Evaluation of mathametical notations like Infix/Postfix etc.

Stack provides the following basic operations,

**Push**

Pushes the element to the top of the stack.**Pop**

Pops or removes the top element of the stak.**Top**

Returns the top element of the stack.**isEmpty**

Returns true if the stack is empty or returns a false otherwise.**Size**

Returns a integer value which is the number of elements currently in the stack.

###### Implementation

Typically stack is implemented using,

- Array or a Dynamic Array
- Linked List

The major operations in a stack involve adding and removing elements at the top, if we use an array to implement it, we will end up moving the array elements one step to the right every time there's a push or pop operation which is very expensive.

On the other hand, a linked list allows addition and removal of an element at the start in constant time. Hence we will use a single linkedlist to implement a stack.

We can start with an empty linkedlist where 'head' is null, use it to append elements or remove for push and pop operations.

###### Psuedo Code

**Push**

```
if head is null
create node with input value
assign head to the new node
else
create node with input value
point's new node's next to head
make the new node as head
```

**Pop**

```
if head is null
return null
else
store head value to temp
point head to the head's next
return the temp
```

**Top**

```
if head is null
return null
else
return head's value
```

**isEmpty**

```
return head==null
```

Below is the full java implementation for stack using linkedlist,

```
/*
* Author : Venkatesh Thallam
*/
/*
* Node Definition for the underlying linked list we use to implement stack
* */
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public class StackImplementation {
Node head;
StackImplementation() {
head = null;
}
public static void main(String[] args) {
StackImplementation stack = new StackImplementation();
stack.push(8);
stack.push(28);
stack.push(38);
stack.push(48);
stack.push(68);
stack.pop();
stack.push(98);
System.out.println(stack.size());
System.out.println(stack.isEmpty());
System.out.println(stack.top());
}
/*
* Pushes an element to the top of the stack
*/
public void push(int val) {
if (head == null) {
head = new Node(val);
} else {
Node newhead = new Node(val);
newhead.next = head;
head = newhead;
}
}
/*
* Pops the top element and returns it
*/
public Integer pop() {
if (head == null)
return null;
else {
Integer poppedval = head.val;
head = head.next;
return poppedval;
}
}
/*
* Returns a boolean that tells if a stack is empty
*/
public boolean isEmpty() {
return head == null;
}
/*
* Returns the total elements currently in the stack
*/
public int size() {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
/*
* Returns the top element of the stack.
*/
public Integer top() {
if (head != null)
return head.val;
else
return null;
}
}
```

###### Time Complexity

The time complexity for each of the stack operations is below,

- Push - O(1)
- Pop - O(1)
- Top - O(1)
- isEmpty - O(1)
- Size - O(n), since this requires checking all values of stack.