Scribd Logo
Upload

Welcome to Scribd!

  • 17 views

    Stack Organization

    Uploaded by

    DEEPANSHU MISHRA
    The document discusses stacks and their operations. It describes how a stack is organized using registers and memory. A stack pointer tracks the top of the stack. Elements are added using push which increments the pointer and writes to memory. Elements are removed using pop which reads from the top, decrements the pointer, and may flag empty status. Stacks are useful for subroutine calls, infix to postfix conversion, and arithmetic evaluation by storing operands and results.

    Copyright:

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

    Stack Organization

    Uploaded by

    DEEPANSHU MISHRA
    17 views31 pages
    The document discusses stacks and their operations. It describes how a stack is organized using registers and memory. A stack pointer tracks the top of the stack. Elements are added using push which increments the pointer and writes to memory. Elements are removed using pop which reads from the top, decrements the pointer, and may flag empty status. Stacks are useful for subroutine calls, infix to postfix conversion, and arithmetic evaluation by storing operands and results.

    Original Description:

    COA

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses stacks and their operations. It describes how a stack is organized using registers and memory. A stack pointer tracks the top of the stack. Elements are added using push which increments the pointer and writes to memory. Elements are removed using pop which reads from the top, decrements the pointer, and may flag empty status. Stacks are useful for subroutine calls, infix to postfix conversion, and arithmetic evaluation by storing operands and results.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    17 views31 pages

    Stack Organization

    Uploaded by

    DEEPANSHU MISHRA
    The document discusses stacks and their operations. It describes how a stack is organized using registers and memory. A stack pointer tracks the top of the stack. Elements are added using push which increments the pointer and writes to memory. Elements are removed using pop which reads from the top, decrements the pointer, and may flag empty status. Stacks are useful for subroutine calls, infix to postfix conversion, and arithmetic evaluation by storing operands and results.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 31

    Stack Organization

    by
    Upendra Mishra
    KIET Group of Institutions, Delhi-NCR, Ghaziabad
    Contents
    • Stack
    • Operations on Stack
    • Types of Stack
    • Applications of Stack
    What is Stack?
    How to work with Stack?
    • Operations on Stack
    • Push: to insert an element into the stack
    • Pop: To remove the top element from the stack

    • A register is used to store the address of the topmost element of the stack
    which is known as Stack pointer (SP).

    • The stack pointer register SP contains a binary number whose value is equal to
    the address of the word that is currently on top of the stack.
    Register Stack:
    • A stack can be placed in a portion of a large
    memory or it can be organized as a collection
    of a finite number of memory words or
    registers.
    • Example: A register stack of 64 words or
    registers
    Initially:
    FULL=0
    EMPTY=1
    SP=0
    Register Stack (contd..)
     FULL=0 (Stack is not full) • FULL is a one-bit flag register for showing the
     FULL=1 (Stack is full) status of stack whether it is Full (containing all
    64 elements) or not.

     EMPTY =0 (Stack is Not empty) • EMPTY is also a one-bit flag register for showing
    the status of stack whether it is Empty
     EMPTY = 1 (Stack is Empty) (containing no element) or not

    • DR is the data register that holds the binary data


    to be written in to or read out of the stack.
    Register Stack (contd..)
    PUSH Operation: • PUSH Operation: The push operation is
    • SP ←SP + 1 (Increment stack pointer) implemented with the shown sequence
    of micro-operation.
    • M [SP] ← DR (Write item on top of the
    stack)
    • The stack pointer is incremented so that
    it points to the address of the next-
    • if (SP==0) then (Full ← 1) (Check if stack higher word.
    is full)
    • Empty ← 0 (Marked the stack not • A memory write operation inserts the
    empty) word from DR into the top of the stack.
    Note that SP holds the address of the top
    Add element A to the Stack
    • Initially:
    FULL=0
    EMPTY=1
    SP=0
    Push an element:
    SP= SP+1 = 0+1 =1
    M[SP] DR ( M[1]=A)
    If (SP==0) then (Full 1 )
    EMPTY=0
    111111
    + 1
    1000000
    Add an element B to the Stack
    • Given
    FULL=0
    EMPTY=0
    SP=1

    Push an element:
    SP= SP+1 = 1+1 =2
    M[SP] DR
    ( M[2]=B)
    If (SP==0) No
    EMPTY=0
    Add an element C to the Stack
    • Given
    FULL=0
    EMPTY=0
    SP=2
    Push an element:
    SP= SP+1 = 2+1 =3
    M[SP] DR ( M[3]=C)
    If (SP==0) No
    EMPTY=0
    Removing an element from the stack
    • POP operation: • The top item is read from the
    • DR← M [SP] (Read item from the top of stack) stack into DR.
    • SP ← SP-1 Decrement stack Pointer
    • If ( SP==0) then (Empty ← 1) Check if stack • The stack pointer is then
    is empty decremented.
    • FULL ← 0 (Mark the stack not full)
    • If its value reaches zero, the
    stack is empty, so Empty is set to
    1.
    Removing the top element from the stack
    Given
    Full = 0
    Empty= 0
    SP=3

    Pop an item
    DR← M [SP]  DR= M[3]= C
    SP= SP-1  SP=3-1= 2
    If (SP==0) then (Empty 1)
    FULL=0
    000000
    - 1
    111111
    Important Point
    • The first item stored in the stack is at address 1.

    • The second last (or prior to last) item stored in the stack is at
    address 63.

    • The last item is stored at address 0.


    Stack Pointer Movement
    Memory Stack:
    Memory Stack:
    • Push Operation:
    • A new item is inserted with the push operation
    as follows.

    • SP← SP-1 (Decrement stack Pointer)


    • M [SP] ← DR (Write item on top of the
    stack)
    Memory Stack:
    • A new item is deleted with a pop operation
    as follows.

    • DR← M [SP] (Read item from the top of


    stack)

    • SP←SP + 1 (increment stack Pointer)


    Applications of Stack
    • Subroutines Call
    • Zero-address Instruction Implementation
    • Infix notation to Post-fix notation
    • Evaluation of Arithmetic Expressions
    Precedence and Associativity
    Instruction
    • Instruction: An Instruction is a command given to the computer to
    perform a specific function.
    • Instruction format:
    • i) Operation Code(Opcode):Specifies Operation to be performed.
    • ii) Specifies which addressing mode is used.
    • iii) Specify a memory address or register address.

    Operation Mode Field Address Field


    Code(Opcode)
    • Evaluate the arithmetic statement
    • X= (A+B)*(C+D)
    • Assume that A,B,C,& D are Memory addresses.
    Problem
    Problem2
    Thank
    You

    You might also like