Category: Stack and Queue

In C language, a stack is an abstract data type that represents a collection of elements with two main operations: push and pop. It follows the Last In First Out (LIFO) principle, which means that the element added last to the stack will be the first one to be removed.

The stack can be implemented in C language using various data structures such as arrays, linked lists, and dynamic arrays. The most common implementation is using an array because it is simple and efficient.

In a stack implemented using an array, the top of the stack is represented by an index variable that points to the last element inserted in the stack. When an element is pushed into the stack, the top index is incremented, and when an element is popped, the top index is decremented.

Here is an example of defining a stack using an array in C language:

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

In this example, we defined a stack of a maximum size of 100, which is represented by the stack array. The top variable is initially set to -1, indicating that the stack is empty.

To perform stack operations, such as push and pop, we can use functions that manipulate the stack elements and the top index.

Here are the common operations that can be performed on a stack in C language:

Push

The push operation adds a new element to the top of the stack. The prototype of the push function is as follows

void push(int item);

Where item is the data item to be added to the stack.

Pop

The pop operation removes the top element from the stack. The prototype of the pop function is as follows

int pop();

The pop function returns the data item that was removed from the stack.

Peek

The peek operation returns the top element of the stack without removing it. The prototype of the peek function is as follows

int peek();

The peek function returns the data item at the top of the stack.

isEmpty

The isEmpty operation checks if the stack is empty. The prototype of the isEmpty function is as follows

int isEmpty();

The isEmpty function returns 1 if the stack is empty and 0 otherwise.

isFull

The isFull operation checks if the stack is full. This operation is only applicable when the stack is implemented using an array. The prototype of the isFull function is as follows

int isFull();

The isFull function returns 1 if the stack is full and 0 otherwise.

Here is an example implementation of these operations

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

void push(int item) {
    if (top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = item;
    }
}

int pop() {
    int item;
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        item = stack[top];
        top--;
        return item;
    }
}

int peek() {
    if (top < 0) {
        printf("Stack is Empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

int isEmpty() {
    if (top < 0) {
        return 1;
    } else {
        return 0;
    }
}

int isFull() {
    if (top >= MAX_SIZE - 1) {
        return 1;
    } else {
        return 0;
    }
}

In C language, a stack can be implemented using an array or a linked list. Here is an example implementation of a stack using an array:

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

// Push operation
void push(int item) {
    if (top >= MAX_SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = item;
    }
}

// Pop operation
int pop() {
    int item;
    if (top < 0) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        item = stack[top];
        top--;
        return item;
    }
}

// Display operation
void display() {
    int i;
    if (top < 0) {
        printf("Stack is Empty\n");
    } else {
        printf("Stack elements are:\n");
        for (i = top; i >= 0; i--)
            printf("%d\n", stack[i]);
    }
}

In this implementation, the push operation adds an element to the top of the stack, the pop operation removes the top element from the stack, and the display operation displays all the elements of the stack.

Here is an example implementation of a stack using a linked list:

struct Node {
    int data;
    struct Node* next;
};

struct Node* top = NULL;

// Push operation
void push(int item) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = item;
    newNode->next = top;
    top = newNode;
}

// Pop operation
int pop() {
    int item;
    struct Node* temp;
    if (top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        temp = top;
        item = temp->data;
        top = top->next;
        free(temp);
        return item;
    }
}

// Display operation
void display() {
    struct Node* temp;
    if (top == NULL) {
        printf("Stack is Empty\n");
    } else {
        temp = top;
        printf("Stack elements are:\n");
        while (temp != NULL) {
            printf("%d\n", temp->data);
            temp = temp->next;
        }
    }
}

In this implementation, the push operation creates a new node with the given data and adds it to the top of the stack, the pop operation removes the top node from the stack and returns its data, and the display operation displays all the elements of the stack.