×

Courses

Chapters

>
<

Data Structure

Stack | CrackEase

Stack

Introduction to Stack

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Elements are added and removed from the same end called the top. Stacks can be implemented using arrays or linked lists.

More about Stacks
  • In a stack, insertion and deletion are performed at one end (the top).
  • Stack supports operations like push, pop, peek/top, and isEmpty.
  • Stacks are commonly used for expression evaluation, function call management (call stack), undo features, and more.
Stack Operations
  • Push: Add an item to the stack (may cause overflow if full).
  • Pop: Remove the top item (may cause underflow if empty).
  • Peek/Top: Return the top item without removing it.
  • isEmpty: Check if the stack has no items.
Representation of stack

Stacks can be implemented using:

  1. Array
  2. Structure (in C)
  3. Linked List
How stack works?
  • Top: Index of the current top element (initially -1 for empty stack).
  • Push: Increment top and place new element at items[top].
  • Pop: Return items[top] and decrement top.
  • Always check for overflow (top == MAX-1) before push and underflow (top == -1) before pop.
Code for Stack in C Program (using structure)
  
// 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) {
  return s->top == MAX - 1;
}

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

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

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

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

// Driver code
int main() {
  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);

  free(s);
  return 0;
}
  

  
#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"<>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:34 20 10 
Enter choice:
4
Exit

Output : Java

	
Inserting 1
Inserting 2
Inserting 3
Inserting 4

After popping out
1
2
3
Understanding the concept of Stack

Let us understand the concept of Stack. As we have learned above, a stack stores data where elements can only be inserted or removed at one end (the top).

For example, a pile of books is a real-world stack: the last book placed on the pile is the first one you remove.

Time Complexity For Various Stack Operations
PushPopDisplaySpace Complexity
O(1)O(1)O(n)O(n)
Footer Content | CrackEase
→
←