Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    Stack

    Uploaded by

    Badnaam Raja
    The document discusses stacks, which are a linear data structure that follows the LIFO (last-in, first-out) principle. Stacks allow insertion and removal of elements from only one end, called the top. New elements can be pushed onto the stack, and the most recently added element can be popped off. The document provides examples of stack operations and applications, including reversing data, backtracking, function calls, and arithmetic expression evaluation. It also describes implementing a stack using either an array or linked list, with pointers or indexes to track the top element.

    Copyright:

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

    Stack

    Uploaded by

    Badnaam Raja
    19 views15 pages
    The document discusses stacks, which are a linear data structure that follows the LIFO (last-in, first-out) principle. Stacks allow insertion and removal of elements from only one end, called the top. New elements can be pushed onto the stack, and the most recently added element can be popped off. The document provides examples of stack operations and applications, including reversing data, backtracking, function calls, and arithmetic expression evaluation. It also describes implementing a stack using either an array or linked list, with pointers or indexes to track the top element.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses stacks, which are a linear data structure that follows the LIFO (last-in, first-out) principle. Stacks allow insertion and removal of elements from only one end, called the top. New elements can be pushed onto the stack, and the most recently added element can be popped off. The document provides examples of stack operations and applications, including reversing data, backtracking, function calls, and arithmetic expression evaluation. It also describes implementing a stack using either an array or linked list, with pointers or indexes to track the top element.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    19 views15 pages

    Stack

    Uploaded by

    Badnaam Raja
    The document discusses stacks, which are a linear data structure that follows the LIFO (last-in, first-out) principle. Stacks allow insertion and removal of elements from only one end, called the top. New elements can be pushed onto the stack, and the most recently added element can be popped off. The document provides examples of stack operations and applications, including reversing data, backtracking, function calls, and arithmetic expression evaluation. It also describes implementing a stack using either an array or linked list, with pointers or indexes to track the top element.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 15

    Stack Data Structure

    Prof. Jasmin T Jose


    SCOPE
    VIT Vellore
    Stack

    • A stack is a type of data structure that allows you access to a


    single element at any given time
    • LIFO structure (last-in first-out).
    • The stack is an ordered list but the insertions and deletions are
    restricted by certain rules.
    • Objects can be inserted at any time, but only the last (the
    most-recently inserted) object can be removed.
    • Inserting an item is known as “pushing” onto the stack.
    “Popping” off the stack is to removing an item.
    • Stack is an Abstract Data Type (ADT)
    Abstract Data Type (ADT)
    • A logical view of the data objects together
    with specifications of the operations required
    to create and manipulate them.
    • What is NOT an Abstract Data Type (in C)?
    – Int -int is a built-in type in the C language
    – Double-double is a built-in type in the C language
    – These data types are already built into the
    language.
    Abstract Data Type (ADT)

    • It is a data type that is NOT built into the language


    • It is a data type that we will “build”.
    • We will specify what it is, how it is used, etc.
    • It is often defined in terms of its behavior rather
    than its implemented representation
    • An abstract data type is defined indirectly, only by
    the operations that may be performed on it (i.e.
    behavior)
    Applications of Stack
    • Reversing Data: We can use stacks to reverse
    data. (example: files, strings). Very useful for
    finding palindromes.
    • Backtracking : Stacks can be used to backtrack
    to achieve certain goals.
    • Function calls: Perhaps the most important
    application of stacks is to implement function
    calls. Most compilers implement function calls
    by using a stack.
    Applications of Stack
    • Arithmetic expression evaluation:
    – An important application of stacks is in parsing.
    – In high level languages, infix notation cannot be
    used to evaluate expressions.
    – A common technique is to convert an infix
    notation into postfix notation, then evaluating it.
    Stack
    Operations on Stack
    Implementation of stack
    • In the array implementation, we would:
    – Declare an array of fixed size (which determines the maximum size of
    the stack).
    – Keep a variable which always points to the “top” of the stack.
    – Contains the array index of the “top” element.
    • In the linked list implementation, we would:
    – Maintain the stack as a linked list.
    – A pointer variable top points to the start of the list.
    – The first element of the linked list is considered as the stack top.
    Declaration and creation
    5
    4
    3
    2
    1
    0
    Push
    void push (int element)
    {
    if (top == (MAXSIZE-1))
    {
    printf(“\n Stack overflow”);
    exit(-1);
    }
    else
    {
    top ++;
    st[top] = element;
    }
    }
    POP
    int pop ()
    {
    if (top == -1)
    {
    printf(“\n Stack underflow”);
    exit(-1);
    }
    else
    {
    a = st[top]
    Top--;
    return a;
    }
    }
    Is empty
    int isempty()
    {
    if (top == -1)
    return 1;
    else
    return (0);
    }
    Is full
    int isfull()
    {
    if (top == (MAXSIZE–1))
    return 1;
    else
    return (0);
    }
    • Applications:
    – Reverse a string
    – Recursive functions
    – Undo operation(Ctrl z)
    – Parenthesis balancing
    – Infix to postfix or prefix conversion
    – Evaluation of postfix expression

    You might also like