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 Node
with 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 initializedata
withval
andnext
withnullptr
.
-
-
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
top
pointer 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
item
as input, which is the value to be pushed onto the stack. - We will create a new
Node
withitem
as its value. - We will set the
next
pointer of the new node to the currenttop
node. - We will update
top
to 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
top
node in a temporary pointertemp
. - Retrieve the value from
temp
and store it inpoppedValue
. - Update
top
to point to the next node in the stack. - Delete the
temp
node 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
top
node.
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
true
iftop
isnullptr
, 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;
}
};