C++ Program to Implement Stack using array
Stack is the fundamental data structure that can operates the under the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. Implementing the stack using the array is one of the most straightforward methods in the terms of the both understanding and coding.
Implementation of Stack in C++
The stack can be implemented using the array organizes its the elements in contiguous memory locations. We can enclose this array in a class as a member and encapsulate the methods and data related to the stack in that class for easy and organized access.
class Stack {
public:
int stackArr[size];
int stackSize;
// constructors and methods
};
Basic Operations on a Stack in C++
1. Push operation
This operation can be used to adds the element to the top of the stack.
Algorithm
1. Check if stack is full. If it is indicate the overflow condition.
2. Increment the top index.
3. Place the new element at top position in the array.
2. Pop Operation
This operation can be used to removes and returns the top element of the stack.
Algorithm
1. Check if stack is empty. If it is indicates the underflow condition.
2. Retrieve the element at top index.
3. Decrement the top index.
4. Return the retrieved element.
3. Peek Operation
The operation can be used to returns the top element without the removing it from the stack.
Algorithm
1. Check if stack is empty. If it is return an error or special value indicating the stack is empty.
2. Return the element at top index without the modifying the top.
4. IsEmpty operation
This operation can checks if the stack contains no elements of the stack.
Algorithm
1. Return the true if the top index is -1 then otherwise return false.
4. IsFull Operation
This operation can checks if the stack has been reached its the maximum capacity of the stack.
Algorithm
1. Return the true if top index is equal to maximum index otherwise return false.
C++ Program to Implement Stack using array
// Include necessary libraries
#include <iostream>
using namespace std;
// Define Stack class
class Stack {
// Pointer to an array that stores elements of the stack
int* arr;
// Index of the top element in the stack
int top;
// Maximum size of the stack
int capacity;
public:
// Constructor to initialize the stack
Stack(int size)
{
// Allocate memory for the stack
arr = new int[size];
// Set the maximum size of the stack
capacity = size;
// Initialize the top of the stack as -1 indicating
// the stack is empty
top = -1;
}
// Destructor to deallocate memory
~Stack() { delete[] arr; }
// Function to add an element x in the stack
void push(int x)
{
// Check if the stack is full
if (isFull()) {
cout << "Overflow\n";
return;
}
cout << "Pushing " << x << "\n";
// Add element and increment top
arr[++top] = x;
}
// Function to remove an element from the stack
int pop()
{
// Check if the stack is empty
if (isEmpty()) {
cout << "Underflow\n";
return -1;
}
// Remove element and decrement top
return arr[top--];
}
// Function to return the top element of the stack
int peek()
{
if (!isEmpty())
return arr[top];
else
return -1;
}
// Function to return if the stack is empty
bool isEmpty() { return top == -1; }
// Function to return if the stack is full
bool isFull() { return top == capacity - 1; }
};
// Main function
int main()
{
// Create a stack of size 3
Stack stack(3);
// Push elements into the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Print the top element of the stack
cout << "The top element is " << stack.peek() << endl;
// Pop an element from the stack and print it
cout << "Popping " << stack.pop() << endl;
// Print the top element of the stack
cout << "The top element is " << stack.peek() << endl;
// Pop all elements from the stack
stack.pop();
stack.pop();
// Check if the stack is empty and print the result
if (stack.isEmpty()) {
cout << "The stack is empty" << endl;
}
else {
cout << "The stack is not empty" << endl;
}
return 0;
}
Output
Pushing 10 Pushing 20 Pushing 30 The top element is 30 Popping 30 The top element is 20 The stack is empty
Time and Space Complexity
- Time complexity: O(1)
- Space complexity: O(n), where n is number of elements in array
Applications of the Stack
- It can applies the Function Call Management.
- It can be applies on the Expression Evaluation to convert the infix expressions to postfix.
- It can be used in the Backtracking algorithms.
- It can be applies on the complier use stacks for the syntax checking and parsing.
- It can applies on the Undo Mechanisms like text editors.