Stack Data structure is a simple algorithm in a data structure which allows to add and remove the element in particular order.

Stack Data structure

What is Stack ?: The stack is a linear type of Data Structure. It follows a particular order in which operations on the Stack are performed. The operations such as adding an element, removing an element or displaying stack element are performed on the stack.
The stack Data structure is like a container which works on a FIRST IN LAST OUT or LAST IN FIRST OUT fashion.

Like a container, the stack has a top from which the operations are performed.

Stack Data structure
Stack Data structure

Note:- Stack Data structure has limited access. The element has inserted and removed from the one end only which is known as Stack Top.

Stack Example

Consider a container or CD’S that is we put CD’S on one another and if we want to take CD’S out then we have to remove the CD which is at the topmost after that the second one and so on.
This illustration state it works like a stack or how a stack works.

Operation performed on a stack

1. Top
It is an end of the stack from which elements are added and removed. It is also used to return the topmost element in a stack.

2. Create
This operation is to create an empty stack it is the first step. and when we create a stack first step is to Assign the top value to -1.

3. Push
The push operation in a stack means to insert or to add an element to stack. Push always inserts the elements to the top of the stack.

4. Pop
The pop operation in a stack means to delete or remove element from a stack. The pop function returns the value at the stack top.

5. Empty
This operation is to check whether the stack is empty or not.

6. Destroy
This operation is to destroy stack (I destroy the complete stack permanently).

Note:-
The top is a pointer which points to a top of a stack and initially, it is a pointing to – 1.
A new element added at the top (operation push).
Element deleted from top (operation pop).
The push, pop are main operations of the stack.

Stack example

Consider, stack with size = 3. Initially top = -1.

Stack Data structure1. Push: add value 10 to stack

Stack Data structure2. Push: add value 20 to stack

Stack Data structure3. Push: add value 30 to stack

Stack Data structure4. Push: add value 40 to stack but our stack is full as (top=size-1) stack is full.

5. Pop: Delete value 30

6. Pop: Delete value 20

Stack Data structure6. Pop: Delete value 10

Stack Data structure7. Pop: Now, top==-1 therefore stack is empty.
This whole example illustrates how the stack works step by step.

Stack algorithm

  1. Set Stack top==-1
  2. Write function Push() data to stack
  3. Function to Remove data from stack pop()
  4. Function to display stack element.

Flowchart for stack

Flowchart for Stack Data structure
Flowchart for Stack

Stack program in c

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

int stack[5];
void push();
int pop();
void traverse();
int is_empty();
int top_element();
int top = 0;

int main()
{
int element, choice;

for (;;)
{
printf("Stack Operations.\n");
printf("1. Insert into stack (Push operation).\n");
printf("2. Delete from stack (Pop operation).\n");
printf("3. Print top element of stack.\n");
printf("4. Check if stack is empty.\n");
printf("5. Traverse stack.\n");
printf("6. Exit.\n");
printf("Enter your choice.\n");
scanf("%d",&choice);

switch (choice)
{
case 1:
if (top == 5)
printf("Error: Overflow\n\n");
else {
printf("Enter the value to insert.\n");
scanf("%d", &element);
push(element);
}
break;

case 2:
if (top == 0)
printf("Error: Underflow.\n\n");
else {
element = pop();
printf("Element removed from stack is %d.\n", element);
}
break;

case 3:
if (!is_empty()) {
element = top_element();
printf("Element at the top of stack is %d\n\n", element);
}
else
printf("Stack is empty.\n\n");
break;

case 4:
if (is_empty())
printf("Stack is empty.\n\n");
else
printf("Stack is not empty.\n\n");
break;

case 5:
traverse();
break;

case 6:
exit(0);
}
}
}

void push(int value) {
stack[top] = value;
top++;
}

int pop() {
top--;
return stack[top];
}

void traverse() {
int d;

if (top == 0) {
printf("Stack is empty.\n\n");
return;
}

printf("There are %d elements in stack.\n", top);

for (d = top - 1; d >= 0; d--)
printf("%d\n", stack[d]);
printf("\n");
}

int is_empty() {
if (top == 0)
return 1;
else
return 0;
}

int top_element() {
return stack[top-1];
}

Output :

Complexity of Stack

The time complexity for Stack

The time complexity for push: When we add an element to stack we make one movement so time complexity for push operation is O(1).
The time complexity for pop: When we delete element from stack we make one movement so time complexity for pop operation is O(1).
The worst time complexity for Stack: To pop all element from queue O(n).

Space complexity for stack:

Worst-case O(n) and best case O(1)

Application of stack

  • It is used to convert infix to postfix.
  • To solve expressions.
  • It is used to programming language where temporary variable stored on Stack.

 

Write A Comment