Handbook of Computer Science(cs) and IT

Stack

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the TOP of the stack.

It is a LIFO (Last In First Out) kind of data structure.

e.g., If a person wants to put a plate on the pile of plates, he has to place it on the top (this is how stack grows) and if he want to take a plate from the pile of plates he has to take it from the top (this is how stack shrinks).

Operations on Stack

There are two operations including in stack as given below

• PUSH (when an item is added to stack)

PUSH (s, i); Adds the item i to the top of stack.

• POP (when an item is removed from stack)

POP (s); Removes the top element and returns it as a function value.

Key Points

• Because of the PUSH operation which adds elements to a stack is sometimes called a pushdown list.
• If a stack contains a single item and the stack is popped, then the resulting stack contains no items and is called empty stack.
• The result of an illegal attempt to POP or access an item from empty stack is called underflow.
• Underflow can be avoided by ensuring that the stack is not empty.

Implementation of Stack

A stack can be implemented using two ways

1. Array 2. Linked list

But since array sized is defined at compile time, it can’t grow dynamically^. Therefore, an attempt to insert/push an element into stack (which is implemented through array) can cause a stack overflow situation, if it is already full.

So, to avoid the above mentioned problem we need to use linked list t_o implement a stack, because linked list can_. grow dynamically and shrink _et runtime. We need to have an additional pointer (TOP) that will always point to the first node in the stack or the top of the stack (in case of linked list implementation of stack).

Applications of Stack

There are many applications of stack some of the important applications ar_e given below

Function Calls

Different ways of organising the data are known as data structures. The compiler uses one such data structure called stack for implementing normal as well as recursive function calls.

# include <stdio.h>

int add (int, int);

void main ( )

{

Int a = 5, b= 2, c;

c= add (a, b);

printf ( “sum = %d” , c);

}

int add (int i , int j)

}

{

int sum,

sum= i + i;

return sum;

}

Expression Evaluation

How a stack can be used for checking on syntax of an expression.

• infix expression It is the one, where the binary operator comes between the operands e.g., A + 8* C.
• Postfix expression Here, the binary operator comes after the operands g., ABC* +
• Prefix expression Here, the binary operator proceeds the operands.

e.g.,+ A^* BC

This prefix expression is equivalent to A + (B * C) infix expression. Prefix notation is also known as Polish notation.

Postfix notation is also known as suffix or Reverse Polish notation.

Operator precedence

Exponential operator A has highest precedence.

Multiplication/Division *,/ operators have next precedence. Addition/Subtraction +, — operators have least precedence.

Reversing a List

First push all the elements of string in stack and then pop elements.