DS Menu

Stacks using Array

Definition of Stack

A stack is a linear data structure that follows a particular order for performing operations. This order is usually LIFO (Last In, First Out), meaning the last element added to the stack is the first one to be removed. It's analogous to a stack of plates where you add a new plate to the top and also take one off from the top.

Key Operations of Stack

Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.
Peek or Top: Returns the top element without removing it from the stack.
IsEmpty: Checks if the stack is empty.

Stack Implementation Using an Array

1: Initialize the Stack

Define the Stack: An array and a variable to keep track of the index of the top element. Initially, the top is set to -1 to indicate the stack is empty.
Specify Stack Capacity: Decide the maximum number of elements the stack can hold (the size of the array).

Pseudocode

maxSize := maxValue
stackArray := array of size maxSize
top := -1  // Indicates that the stack is initially empty

2: Push Operation

Check for Overflow: Before adding a new element, check if the stack is already full. If the top is equal to the maximum size minus one, the stack is full.
Add Element: Increment the top index and insert the new element at this position in the array.

Pseudocode

// Add an item to the stack
function push(item)
    if top = maxSize - 1
        display "Stack Overflow"
    else:
        top := top + 1
        stackArray[top] := item

3: Pop Operation

Check for Underflow: Before removing an element, check if the stack is empty. If the top is -1, the stack is empty.
Remove Element: Remove the element at the top of the stack and decrement the top index.

Pseudocode

// Check if the stack is empty
function isEmpty():
    return top == -1

// Remove an item from the stack
function pop()
    if top = -1
        display "Stack Underflow"
        return null
    else:
        item := stackArray[top]
        top := top - 1
        return item

4: Peek Operation

Retrieve Top Element: Return the element at the top index in the array. Check if the stack is not empty before performing this operation.

Pseudocode

// Get the top item of the stack without removing it
function peek():
    if top = -1
        display "Stack is empty"
        return null
    else:
        return stackArray[top]

C Program to implement Stack uing array

Program:


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

#define MAX_SIZE 10

int stack[MAX_SIZE],top=-1;

// Function to check if the stack is empty
bool isEmpty() {
    return top == -1;
}

// Function to add an item to the stack
void push(int item) {
    if (top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = item;
    }
}

// Function to remove an item from the stack
int pop() {
    if (isEmpty()) {
        printf("Stack Underflow\n");
        return -1; // Indicating underflow
    } else {
        return stack[top--];
    }
}

// Function to get the top item of the stack
int peek() {
    if (isEmpty()) {
        printf("Stack is Empty\n");
        return -1; // Indicating empty stack
    } else {
        return stack[top];
    }
}

// Function to show all the items from stack
void show()
{
    int i;
    for(i=top;i>-1;i--)
        printf("%d\n",stack[i]);
}

// Main function
int main() {
    int ch,data;
    do{
        printf("\n1. push\n2. pop\n3. peek\n4. show\n5. exit");
        printf("\nEnter your choice:   ");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("enter data to push:  ");
                    scanf("%d",&data);
                    push(data);
                    break;
            case 2: printf("Popped: %d\n", pop());
                    break;
            case 3: printf("Top element: %d\n", peek());
                    break;
            case 4: show();
                    break;
            case 5: break;
            default: printf("Enter valid choice");
        }
    }while(ch!=5);
    return 0;
}

Next Topic :Stacks using linkedlist