# Implement stack using linked list

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:

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

### Implementation of stack

The stack can be implemented in two ways:

1. Statically:  Using arrays
2. 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:

1. Create a node for our new element.
2. Point to the next pointer of our element node to point to the head of the linked list.
3. Make the element node our top node.
4. 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

1. Check for underflow conditions in the stack.
2. Store the top node in a temp node and top node data in another variable.
3. Make the second node of our temp node a top.
4. Delete temp node.
5. 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--;
}
``````

## Java Code

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

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() {
}
``````

## Java Code

``````public boolean stackIsEmpty() {
}
``````

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--;
}
int stackSize() {
return size;
}
bool stackIsEmpty() {
}
int stackPeek() {
if (top == NULL) return -1;
}
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;
}
public int stackSize() {
return size;
}
public boolean stackIsEmpty() {
}
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 to Yash Mishra for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article