Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    Stacks

    Uploaded by

    anuragdharmadhikari1
    Handwritten Notes on STACKS in DSA.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Stacks

    Uploaded by

    anuragdharmadhikari1
    10 views5 pages
    Handwritten Notes on STACKS in DSA.

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Handwritten Notes on STACKS in DSA.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    10 views5 pages

    Stacks

    Uploaded by

    anuragdharmadhikari1
    Handwritten Notes on STACKS in DSA.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 5

    Stacks

    Stack is an important element that stores its elements


    in an ordered manner. A stack is a liner data
    structure that uses the principle of LIFO i.e. Last-
    In -First-Out.
    When a function calls another function the address of
    the function is stored / pushed into the stack memory
    (at the top) that helps to maintain a record of the
    function that is being called. This also eliminates the
    function that are used and removes them from the top
    of stack memory, this is called the pop operation.

    Array representation of stacks


    In a computer memory, stacks can be represented as a
    linear array.
    Every stack has a variable called:
    TOP -- Used to store the address of the top most
    element in the stack.
    MAX – Used to store the maximum number of elements
    of the stack.
    *If the TOP is NULL this implies that the stack is empty,
    whereas if the TOP = MAX -1 this implies that the stack
    is full.

    Operations on a Stack
    A stack supports three operations: PUSH, POP, PEEK.
    PUSH operation adds an element to the top of the stack memory.
    Before addition of the new element we must first check if the
    memory is available for the addition of the element by using
    TOP = MAX -1.
    If the condition is not fulfilled then the element is not added.
    ALGORITHM:
    Step 1: IF TOP = MAX – 1
    PRINT “OVERFLOW” GO TO Step 4
    [ END OF IF ]
    Step 2: SET TOP = TOP + 1
    Step 3: SET STACK [ TOP ] = VALUE
    Step 4: END

    POP operation removes the added element from the top of the stack
    memory.
    The condition to check before pop is that whether the stack is empty
    or not, because if the stack is empty the no element can be removed
    from the stack i.e. TOP = NULL is not acceptable.
    If the top is not null then the pop operation can be implemented
    successfully, if the top is empty then we can change the condition to
    TOP = MAX – 1. This method is called as TOP decrement.
    ALGORITHM:
    STEP 1: IF TOP = NULL
    PRINT “UNDERFLOW”
    GOTO STEP 4
    [ END OF IF ]
    STEP 2: SET VAL = STACK [ TOP ]
    STEP 3: SET TOP = TOP – 1
    STEP 4: END

    PEEK operation returns the value of the top most element stored in
    the stack memory without deleting it from the stack.
    ALGORITHM:
    STEP 1: IF TOP = NULL
    PRINT “STACK IS EMPTY”
    GOTO STEP 3
    STEP 2: RETURN STACK [TOP]
    STEP 3: END
    LINKED LIST REPRESENTATION OF STACK

    In a linked stack, every node has two parts – one that stores the data
    and the other which that stores the address of the next node. All
    insertions and deletions are done by the node pointed by the TOP.
    OPERATIONS ON A LINKED LIST

    PUSH OPERATION
    The new element is added at the topmost position of the stack.
    ALGORITH:
    STEP 1: ALLOCATE MEMORY FOR THE NEW NODE AND NAME IT AS
    NEW_NODE
    SETP 2: SET NEW_NODE -> DATA = VAL
    STEP 3: IF TOP = NULL
    SET NEW_NODE -> NEXT = NULL
    SET TOP = NEW_NODE
    ELSE
    SET NEW_NODE -> NEXT = TOP
    SET TOP = NEW_NODE
    [ END OF IF ]
    STEP 4: END

    POP OPERATION

    ALGORITHM:
    STEP 1: IF TOP = NULL
    PRINT “UNDERFLOW”
    GOTO STEP 5
    [ END OF IF ]
    STEP 2: SET PTR = TOP
    STEP 3: SET TOP = TOP ->NEXT
    STEP 4: FREE PTR
    STEP 5: END

    MULTIPLE STACKS
    A multiple stack is used for the efficient usage of the
    stack space in the memory. It allows the user to create
    an array such that the size of array will not exceeding
    the original requirement of size in the stack space.
    Here, to increase the size of an array stack the array is
    made in such a way that it exceeds its size, this index
    in the array is such a way that an array STACK [N] is
    used to represent two stacks, STACK[A] & STACK[B].
    The value of n is such that the combined size of both
    the stacks will never exceed N.

    APPLICATIONS OF STACKS
    1.Reversing a list: A number can be reversed
    by reading each element in an array starting
    from the first index and pushing it on a stack.
    *Program at last
    2.Parentheses checker: Used for the validity of
    parenthesis in any element expression.
    3.Conversion of an index expression into a
    postfix expression
    4.Evaluation of a postfix expression
    5.Conversion of an infix element into a prefix
    expression
    6.Evaluation of a prefix expression
    7.Recursion
    8.Tower of Honoi
    **Program code at last

    You might also like