​

​

​

​

​

​

​

Stack

​

​

​

Presented by

Pathapati Saroja

​

​

Stack:

• A stack is a ordered list in which insertions and deletions are made at one end called the top.
• The last inserted element into a stack is the element to be removed first, so it is known as Last-In-First-Out(LIFO).

Examples:

​

​

2

The stack is an abstract data structure in which elements are stored in LIFO manner

Abstract Data type(ADT):

• A useful tool for performing logical properties of a data type is ADT.
• The data type is a collection of values and a set of operations on those values.
• An ADT is a mathematical model for data types.

Stack ADT: (will share the screen shorts, its nothing but mathematical representations of the functions used in stack)

Applications:

● Reverse the given string

● Undo in text editor

● Recursion

● Check balances for paranthesis

● Infix to prefix/ postfix evaluation

● prefix/postfix evaluation

​

​

​

​

3

Stack Representations: can be done in two ways

1. Static representation( using arrays)

2. Dynamic representation (using linked list)

Basic Operations:

1. push(): inserting an element into the stack (before inserting we need to check

whether the stack is full, if it is we cannot insert otherwise we can)

2. pop(): deleting an element on the top of the stack (before deleting we will check whether the stack contains any elements or not. If there are no elements, we cannot delete an element otherwise we can perform deletion)

3. popitem(): after deleting the element we can display the element that is deleted.

4. top(): The element that is present on the top of the stack will be displayed.

​

​

​

4

5. isfull(): checks if the stack is full

6. isempty(): checks whether stack is empty.

​

1. push();

void push(int x)

{

if(top==MAXSIZE-1)//if(isfull())

printf("stack is full");

else

{

top++;

stack[top]=x;

}

}

​

​

​

5

2. pop():

int pop()

{

int y;

if(top==-1) //isempty()

return 0;

else

{

y=stack[top];

top--;

return y;

}

}

​

​

​

​

6

3. display():

void display()

{

int i;

printf("elements in stack are");

for(i=0;i<top;i++)

printf("%d\t",stack[i]);

}

Write program using main with switch case:

Case 1:push(a,n)//a-address of array and n- no. of elements

Case 2: int itempopped=pop()

Case 3:display()

​

​

​

7

Output:

10 20 30 40 50

Reversing strings:

• To reverse a string, the character of string are pushed onto the stack one by one as the string is read from left to right
• Once all the characters of string are pushed onto the stack,they are popped one by one. Since the last character pushed in comes out first ,subsequent pop operations results in the reversal of the string

​

​

​

8

void push(char x)

{

if(top == max-1)

printf("stack overflow");

else

stack[++top]=x;

}

void pop()

{

printf("%c",stack[top--]);

}

​

98+382/*2+-

-+98+*3/822

​

​

​

int main()

{

char str[]="srkr engg college";

int len = strlen(str);

int i;

for(i=0;i<len;i++)

push(str[i]);

for(i=0;i<len;i++)

pop();

return 0;

}

​

​

9

Output:

REVER

Balanced Parantheses

• Stack is also used to check whether the given arithmetic expression containing nested parentheses is properly parenthesized
• The program for checking the validity of an expression verifies that for each left parenthesis braces ,there is a corresponding closing symbol and symbols are properly nested

​

​

​

​

10

for (i = 0; a[i] != '\0';i++)

{

if (a[i] == '(')

{

push(a[i]);

}

else if (a[i] == ')')

{

pop();

}

}

find_top();

}

void push(char a)

{

stack[top] = a;

top++;

}

​

​

​

​

​

​

// to pop elements from stack

void pop()

{

if (top == -1)

{

printf("expression is invalid\n");

exit(0);

}

else

{

top--;

}

}

​

​

​

11

// to find top element of stack

void find_top()

{

if (top == -1)

printf("\nexpression is valid\n");

else

printf("\nexpression is invalid\n");

}

​

​

Thank you

12