• Stack can be defined as a Data Structure that serves as saving the data in a particular fashion.
• In linear data structures like an array and linked list a user is allowed to insert or delete any element to and from any location respectively.
• However, in a Stack, both, insertion and deletion, is permitted at one end only.
• A Stack works on the LIFO (Last In – First Out) basis, i.e, the first element that is inserted in the stack would be the last to be deleted; or the last element to be inserted in the stack would be the first to be deleted.

• Push: Adding a new item to the Stack Data Structure, in other words pushing new item to Stack DS.

If Stack is full, then it is said to be in an overflow condition

• Pop: Removing an item from the stack, i.e. popping an item out.

If a stack is empty then it is said to be in an underflow condition

• Peek: This basically returns the topmost item in the stack, in other words, peek that what is the topmost item.
• IsEmpty: This returns True If the stack is empty else returns False

Stack as a data structure can be represented in two ways.

1. Stack as an Array.
2. Stack as a struct
3. Stack as a Linked List.

There are a number of operations we can perform on a stack as per our need which are as follows:

• Push().
• Pop().
• Top/Peak().
• isEmpty().

The time complexity of each of these operations is constant time, i.e , O(1).

• When we require to add an element to the stack we perform Push() operation.
• Push() operation is synonymous of insertion in a data structure.

• When we require to remove an element to the stack we perform Pop() operation.
• Pop() operation is synonymous of deletion in a data structure.

• This operation returns the top most or peak element of the stack.
• The value of top changes with each push() or pop() operation.

• When we require to add an element to the stack we perform Push() operation.
• Push() operation is synonymous of insertion in a data structure.

• Top: An integer variable Top is used, to keep track of topmost element in the stack
• When we initialise the stack, there is no element in a stack so, Top value is initialised to Top = -1 
• The value is -1 as if use an array to implement stack if there is 1 element the location would be a[0], thus, for no element we use – 1.
• Push: on pushing new element the Top value increments by 1, top++
• Pop: on popping a new element the top value decrements by 1, top–
• Before pushing we check if the stack is full or not
• Before popping we check if the stack is empty or not

  
// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n STACK EMPTY \n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("\nAfter popping out\n");
  printStack(s);
}
  

  
#include <iostream>
using namespace std;
int stack[100], n=100, top=-1;
void push(int val) {
   if(top>=n-1)
   cout<< "Stack Overflow"<< endl;
   else {
      top++;
      stack[top]=val;
   }
}
void pop() {
   if(top<=-1)
   cout<<"Stack Underflow"<=0) {
      cout<<"Stack elements are:";
      for(int i=top; i>=0; i--)
      cout<< stack[i] <<" ";
      cout<< endl;
   } else
   cout<<"Stack is empty";
}
int main() {
   int ch, val;
   cout<<"1) Push in stack"<< endl;
   cout<<"2) Pop from stack"<< endl;
   cout<<"3) Display stack"<< endl;
   cout<<"4) Exit"<< endl;
   do {
      cout<<"Enter choice: "<< endl;
      cin>>ch;
      switch(ch) {
         case 1: {
            cout<<"Enter value to be pushed:"<< endl;
            cin>>val;
            push(val);
            break;
         }
         case 2: {
            pop();
            break;
         }
         case 3: {
            display();
            break;
         }
         case 4: {
            cout<<"Exit"<< endl;
            break;
         }
         default: {
            cout<<"Invalid Choice"<< endl;
         }
      }
   }while(ch!=4);
   return 0;
}
  

  

class Stack {
  private int arr[];
  private int top;
  private int capacity;

  // Creating a stack
  Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
  }

  // Add elements into stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlow\nProgram Terminated\n");
      System.exit(1);
    }

    System.out.println("Inserting " + x);
    arr[++top] = x;
  }

  // Remove element from stack
  public int pop() {
    if (isEmpty()) {
      System.out.println("STACK EMPTY");
      System.exit(1);
    }
    return arr[top--];
  }

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

  // Check if the stack is empty
  public Boolean isEmpty() {
    return top == -1;
  }

  // Check if the stack is full
  public Boolean isFull() {
    return top == capacity - 1;
  }

  public void printStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String[] args) {
    Stack stack = new Stack(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    System.out.println("\nAfter popping out");

    stack.printStack();

  }
}
	

Output : C

	
Stack: 1 2 3 4 
Item popped= 4

After popping out
Stack: 1 2 3 
	

Output : C++

	
1) Push in stack
2) Pop from stack
3) Display stack
4) Exit
Enter choice: 
1
Enter value to be pushed:
10
Enter choice: 
1
Enter value to be pushed:
20
Enter choice: 
1
Enter value to be pushed:
34
Enter choice: 
2
The popped element is 34
Enter choice: 
3
Stack elements are:20 10 
Enter choice:
4
Exit
	

Output : Java

	
Inserting 1Inserting 2
Inserting 3
Inserting 4

After popping out
1
2
3 
	

Let us understand the concept of Stack. As we have learned about stack above, it stores the data in a particular fashion where the element can only be inserted or deleted at one end only.

Let us consider a stack of books as shown in the image.

• This pile of books would have been formed by placing one book on the other like first the blue book and then on top of it the red book then on top of the red book came the yellow book and so on.
• The functioning of the Stack is similar to this.
• If we look at the stack in the image.
  • First the element 42 would have been added to an empty stack.
  • Then on the top of it, the second element 18 would be added.
  • On the top of 18, the next element 12 would have been added and so on.
• Similarly, if we pick out the books out of the stack we will have to begin from top. For instance if we want to remove the yellow book we will have to first remove the pink book, then the blue book and then the green book and then we will finally be able to remove the yellow book.
• Same happens in the case of the stack. To delete the element 12 , we will have to first remove 22 then 34 and then we can delete the element 12.
• With this example we can be certain that a stack structure works on a LIFO basis, i.e , the last element to be inserted would be deleted first.