CS Code

Coding, quiz & more

Stack Data Structure

In this tutorial, we are going to learn the Stack Data Structure and how to implement stack in C, C++, Java, Python .

Stack is a Linear Data Structure in which operation performed from one side only i.e. Top Of The Stack.

The real life example of stack is pile of plates where plates are simply placed top of each other.

Stack Representation

The plate at 1st position is pushed first and the plate at 5th position is pushed at the end. This means order of operation in stack is LIFO(Last In First Out) or FILO(First In Last Out).

Operations of Stack

Following basic operations are performed in the stack:

  1. Push: Add an element to top of the stack. If stack is full then its overflow condition.
  2. Pop: Remove an element from top of the stack. If stack is empty then its underflow condition.
  3. Peek or Top: Show element at top of the stack without removing it.
  4. isEmpty: Returns True if stack is empty else return False
  5. isFull: Returns True if stack is full else return False

Time Complexity of array based stack for push(), pop(), peek(), isEmpty() & isFull() is O(1) i.e. constant time.

Applications of Stack

  • Infix to Post-fix conversion
  • Undo-Redo functionality in editors, browsers.
  • To go backward and forward in web browsers.
  • In Depth First Search(DFS) algorithms.
  • String reversal

Stack Implementations using array 

#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("Overflow");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n Underflow \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);

  printStack(s);
}

#include <iostream>
#include <stdlib.h>

using namespace std;

#define MAX 10
int size = 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("Overflow");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

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

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// 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);

  printStack(s);
}

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 to stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlow\n");
      System.exit(1);
    }

    arr[++top] = x;
  }

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

  //  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();

    stack.printStack();

  }
}

# Creating a stack
def create_stack():
    stack = []
    return stack


# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0


# Adding items into the stack
def push(stack, item):
    stack.append(item)


# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "underflow"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("Elements in the stack " + str(stack))

‹ Array Data Structure
› Queue Data Structure

Back to top