**Pre-requisites: **Basic knowledge of stack and operations in the linked list.

**Introduction**

Stack is a linear data structure in which elements are stored like a *pile*** , **i.e. one on top of another.

The following diagram represents a simple stack

Following operations can be performed in the stack:

- push(): pushes an element at the top of the stack.
- pop(): removes an element from the top of the stack.
- size(): returns the size of the stack.
- isEmpty(): returns a boolean value for whether the stack is empty or not.
- peek()/top(): returns the top element of the stack.

**Implementation of stack**

The stack can be implemented in two ways:

- Statically: Using arrays
- Dynamically: Using a linked list

In this article, we’ll focus more on the implementation of a stack using a linked list.

**Approach**

Let’s focus on each and every operation of the stack and see how we can implement it using a linked list.

We can assume our linked list to be a horizontal stack where the operations like deletion and insertion would take place at the top of the stack or at the head of the linked list.

**To perform all the operations our head of the linked list would act as the top of the stack.**

**push(): pushing an element at the top of a stack**

Pushing the element at the top of the stack would mean the same as pushing an element at the end of the linked list.

We can insert it at the beginning of the linked list using the following steps:

- Create a node for our new element.
- Point to the next pointer of our element node to point to the head of the linked list.
- Make the element node our top node.
- Increment the size variable.

For a more detailed explanation of insertion at the beginning of a linked list, refer to this article.

Let’s see the function of this implementation

**Code:**

## C++ Code

```
void stackPush(int x) {
stackNode * element = new stackNode(x);
element -> next = top;
top = element;
cout << "Element pushed" << "\n";
size++;
}
```

## Java Code

```
public void stackPush(int x) {
stackNode element = new stackNode(x);
element.next = top;
top = element;
System.out.println("Element pushed");
size++;
}
```

**pop(): removing an element from the top of a stack**

Removing an element from the top of the stack is the same as removing the element from the beginning of our linked list.

**The following steps are involved in the pop() method**

- Check for
**underflow conditions**in the stack. - Store the top node in a temp node and top node data in another variable.
- Make the second node of our temp node a top.
- Delete temp node.
- Return the top node’s data.

The following function explains the approach

**Code:**

## C++ Code

```
int stackPop() {
if (top == NULL) {
return -1;
}
int topData = top -> data;
stackNode * temp = top;
top = top -> next;
delete temp;
size--;
return topData;
}
```

## Java Code

```
public int stackPop() {
if (top == null) return -1;
int topData = top.data;
stackNode temp = top;
top = top.next;
return topData;
}
```

**size(): returns the size of the stack**

For this, we maintain a size variable. After each push operation, we increment the **size** variable and after each pop operation, we decrement the **size** variable.

Let’s see the code implementation for this function.

**Code:**

## C++ Code

```
int stackSize() {
return size;
}
```

## Java Code

```
public int stackSize() {
return size;
}
```

**isEmpty(): returns a boolean value for whether the stack is empty or not.**

To do this, we check if our top is equal to NULL.

Code implementation is as follows:

**Code:**

## C++ Code

```
bool stackIsEmpty() {
return top == NULL;
}
```

## Java Code

```
public boolean stackIsEmpty() {
return top == null;
}
```

The following code compiles every function to form a complete stack implementation using a linked list.

**Code:**

## C++ Code

```
#include<iostream>
using namespace std;
struct stackNode {
int data;
stackNode * next;
int size;
stackNode(int d) {
data = d;
next = NULL;
}
};
struct stack {
stackNode * top;
int size;
stack() {
top = NULL;
size = 0;
}
void stackPush(int x) {
stackNode * element = new stackNode(x);
element -> next = top;
top = element;
cout << "Element pushed" << "\n";
size++;
}
int stackPop() {
if (top == NULL) {
return -1;
}
int topData = top -> data;
stackNode * temp = top;
top = top -> next;
delete temp;
size--;
return topData;
}
int stackSize() {
return size;
}
bool stackIsEmpty() {
return top == NULL;
}
int stackPeek() {
if (top == NULL) return -1;
return top -> data;
}
void printStack() {
stackNode * current = top;
while (current != NULL) {
cout << current -> data << " ";
current = current -> next;
}
}
};
int main() {
stack s;
s.stackPush(10);
cout << "Element popped: " << s.stackPop() << "\n";
cout << "Stack size: " << s.stackSize() << "\n";
cout <<"Stack empty or not? "<<s.stackIsEmpty()<<"\n";
cout << "stack's top element: " << s.stackPeek() << "\n";
return 0;
}
```

**Output:**

Element pushed

Element popped: 10

Stack size: 0

Stack empty or not? 1

stack’s top element: -1

## Java Code

```
class stack {
private class stackNode {
int data;
stackNode next;
stackNode(int d) {
data = d;
next = null;
}
}
stackNode top;
int size;
stack() {
this.top = null;
this.size = 0;
}
public void stackPush(int x) {
stackNode element = new stackNode(x);
element.next = top;
top = element;
System.out.println("Element pushed");
size++;
}
public int stackPop() {
if (top == null) return -1;
int topData = top.data;
stackNode temp = top;
top = top.next;
return topData;
}
public int stackSize() {
return size;
}
public boolean stackIsEmpty() {
return top == null;
}
public void printStack() {
stackNode current = top;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
class Main {
public static void main(String args[]) {
stack s = new stack();
s.stackPush(10);
s.stackPush(20);
s.printStack();
System.out.println("Element popped " + s.stackPop());
System.out.println("Stack size: " + s.stackSize());
System.out.println("Stack is empty or not: " + s.stackIsEmpty());
}
}
```

**Output:**

Element pushed

Element pushed

20 10

Element popped 20

Stack size: 2

Stack is empty or not: false

Special thanks toYash Mishrafor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article