Operations

The basic operations that can be performed on stack are as follows:

1. PUSH

The process of adding a new element to the top of stack is called PUSH operation. Pushing an element in the stack invoke adding of element, as the new element will be inserted at the top after every push operation the top is incremented by one. In case the array is full and no new element can be accommodated, it is called STACK-FULL condition. This condition is called STACK OVERFLOW.

Algorithm:

1. Initialize set top = -1
2. Repeat steps 3 to 5 until top< MAX Size -1
3. Read, Item
4. Set top = top +1
5. Set Stack [top] = Item
6. Print “Stack Overflow”

2. POP

The process of deleting an element from the top of stack is called POP operation. After every pop operation the stack is decremented by one. If there is no element on the stack and the pop is performed then this will result into STACK UNDERFLOW condition. 

Algorithm:

1. Repeat steps 2 to 4 until top>= 0
2. Set item = stack [top]
3. Set top = top-1
4. Print, No deleted is, Item
5. Print stack under flows.

APPLICATIONS OF STACKS

• Stacks are widely used in evaluation of arithmetic expressions.

• Reversing a List.

• Polish Notations.

• Conversion of infix to Postfix Expression.

• Evaluation of Postfix Expression.

• Conversion an infix into prefix Expression.

• Evaluation of Prefix Expression

Listing: Following C program is showing implementation of stack using array.

Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.

// C program for array implementation of stack

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

// A structure to represent a stack

struct Stack

{

int top;

unsigned capacity;

int* array;

};

// function to create a stack of given capacity. It initializes size of

// stack as 0

struct Stack* createStack(unsigned capacity)

{

struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

stack->capacity = capacity;

stack->top = -1;

stack->array = (int*) malloc(stack->capacity * sizeof(int));

return stack;

}

// Stack is full when top is equal to the last index

int isFull(struct Stack* stack)

{ return stack->top == stack->capacity - 1; }

// Stack is empty when top is equal to -1

int isEmpty(struct Stack* stack)

{ return stack->top == -1; }

// Function to add an item to stack. It increases top by 1

void push(struct Stack* stack, int item)

{


if (isFull(stack))

return;

stack->array[++stack->top] = item;

printf("%d pushed to stack\n", item);

}

// Function to remove an item from stack. It decreases top by 1

int pop(struct Stack* stack)

{

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack->top--];

}

// Function to get top item from stack

int peek(struct Stack* stack)

{

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack->top];

}

// program to test above functions

int main()

{

struct Stack* stack = createStack(100);

push(stack, 10);

push(stack, 20);

push(stack, 30);

printf("%d popped from stack\n", pop(stack));

printf("Top item is %d\n", peek(stack));

return 0;

}

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top item is 20