Stack in Data Structure | Board Infinity

Introduction

A stack is a linear data structure in which operations are done in a specific order. The order might be LIFO (Last In, First Out) or FILO (First In, Last Out).

Stack example

There are numerous real-world examples of stacks. Consider the canteen, where plates are heaped on top of one another. The plate at the top is the first to be removed, implying that the plate at the bottom is the one that remains in the stack for the longest duration. As a result, it can be observed to follow the LIFO (Last In, First Out)/FILO (First In, Last Out) order.

Applications of Stack in Real Life

Bangles: Women wear their bangles one by one, and in order to remove the first one, they must first remove the last one.
Books and Clothes: A excellent illustration of the stack is items piled on top of one another.
Floors in a Building: If a person lives on the top floor and want to come out, he or she must first walk down to the first floor.
Browsers: The stack is used by online browsers to keep track of the history of websites. If you click back, the previous site appears quickly.
Mobile Phone: Mobile call logs use the stack; you must scroll to view a first person’s call log.
Garage: if a garage's width is not sufficient. We need to remove all the vehicles that came after the initial one in order to remove it.

C++ stack implementation

push: Adds a new element to the top of the stack, on top of the top element that is already there.
pop: Removes the top element from the stack, which makes it one size smaller.
isEmpty: Returns true If the stack is empty, which means that its size is 0. Or else, it returns false.
isFull: Returns true if the stack is full, which means that its size has reached the limit of what can be stored on it. If the stack is not full, it returns false.
peek: Returns the stack's top element without changing the stack.
size: Returns the number of items in the stack.

Syntax

#include <iostream>
#include <cstdlib>
using namespace std;

// Define the default capacity of the stack
#define SIZE 10

// A class to represent a stack
class Stack
{
int *arr;
int top;
int capacity;

public:
Stack(int size = SIZE); // constructor
~Stack(); // destructor

void push(int);
int pop();
int peek();

int size();
bool isEmpty();
bool isFull();
};

// Constructor to initialize the stack
Stack::Stack(int size)
{
arr = new int[size];
capacity = size;
top = -1;
}

// Destructor to free memory allocated to the stack
Stack::~Stack() {
delete[] arr;
}

// Utility function to add an element `x` to the stack
void Stack::push(int x)
{
if (isFull())
{
cout << "Overflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}

cout << "Inserting " << x << endl;
arr[++top] = x;
}

// Utility function to pop a top element from the stack
int Stack::pop()
{
// check for stack underflow
if (isEmpty())
{
cout << "Underflow\nProgram Terminated\n";
exit(EXIT_FAILURE);
}

cout << "Removing " << peek() << endl;

// decrease stack size by 1 and (optionally) return the popped element
return arr[top--];
}

// Utility function to return the top element of the stack
int Stack::peek()
{
if (!isEmpty()) {
return arr[top];
}
else {
exit(EXIT_FAILURE);
}
}

// Utility function to return the size of the stack
int Stack::size() {
return top + 1;
}

// Utility function to check if the stack is empty or not
bool Stack::isEmpty() {
return top == -1; // or return size() == 0;
}

// Utility function to check if the stack is full or not
bool Stack::isFull() {
return top == capacity - 1; // or return size() == capacity;
}

int main()
{
Stack pt(3);

pt.push(1);
pt.push(2);

pt.pop();
pt.pop();

pt.push(3);

cout << "The top element is " << pt.peek() << endl;
cout << "The stack size is " << pt.size() << endl;

pt.pop();

if (pt.isEmpty()) {
cout << "The stack is empty\n";
}
else {
cout << "The stack is not empty\n";
}

return 0;
}

Output:

Inserting 1
Inserting 2
Removing 2
Removing 1
Inserting 3
The top element is 3
The stack size is 1
Removing 3
The stack is empty

Time Complexity: O(1).

write your code here: Coding Playground