Creation of Stack (Linked List Implementation)
class Stack {
private:
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
Node* top;
public:
// Constructor to initialize stack
Stack() {
top = nullptr;
}
};
First, we will create a class named
Stack.-
It will contain a
struct Nodewith the following properties:-
int data: Stores the value of the node. -
Node* next: Points to the next node in the stack. -
Node(int val): Constructor to initializedatawithvalandnextwithnullptr.
-
-
It will contain a property
top:-
Node* top: Points to the top node of the stack.
-
-
We will declare a constructor
Stack():- It will initialize the
toppointer tonullptr, indicating an empty stack.
- It will initialize the
Push Operation
void push(int item) {
Node* newNode = new Node(item);
newNode->next = top;
top = newNode;
}
We will define a method push(int item):
- It will take an integer
itemas input, which is the value to be pushed onto the stack. - We will create a new
Nodewithitemas its value. - We will set the
nextpointer of the new node to the currenttopnode. - We will update
topto point to the new node.
Pop Operation
int pop() {
if (isEmpty()) {
cout << "Underflow: Stack is empty.\n";
return -1;
}
Node* temp = top;
int poppedValue = temp->data;
top = top->next;
delete temp;
return poppedValue;
}
We will define a method pop():
- It will return an integer, which is the value removed from the top of the stack.
- We will check if the stack is empty (using
isEmpty()); if so, it will print "Underflow: Stack is empty." and return-1. - Otherwise, we will:
- Store the
topnode in a temporary pointertemp. - Retrieve the value from
tempand store it inpoppedValue. - Update
topto point to the next node in the stack. - Delete the
tempnode to free up memory. - Return the
poppedValue.
- Store the
Peek Operation
int peek() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return -1;
}
return top->data;
}
We will define a method peek():
- It will return an integer, which is the value at the top of the stack.
- We will check if the stack is empty (using
isEmpty()); if so, it will print "Stack is empty." and return-1. - Otherwise, it will return the value of the
topnode.
isEmpty Operation
bool isEmpty() {
return top == nullptr;
}
We will define a method isEmpty():
- It will return a boolean value indicating whether the stack is empty.
- It will return
trueiftopisnullptr, indicating that the stack is empty. - Otherwise, it will return
false.
Full Code Implementation
#include <iostream>
using namespace std;
class Stack {
private:
struct Node {
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
Node* top;
public:
// Constructor to initialize stack
Stack() {
top = nullptr;
}
// Destructor to free allocated memory
~Stack() {
while (!isEmpty()) {
pop();
}
}
// Push operation
void push(int item) {
Node* newNode = new Node(item);
newNode->next = top;
top = newNode;
}
// Pop operation
int pop() {
if (isEmpty()) {
cout << "Underflow: Stack is empty.\n";
return -1;
}
Node* temp = top;
int poppedValue = temp->data;
top = top->next;
delete temp;
return poppedValue;
}
// Peek operation
int peek() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return -1;
}
return top->data;
}
// Check if stack is empty
bool isEmpty() {
return top == nullptr;
}
};
Top comments (0)