Stacks

• Stack


  A Last In, First Out (LIFO) data structure where items are added to the top and removed from the top
• Stack


  • Used in calculations
  • Used to hold return addresses when subroutines are called
  • Used when navigating back through web pages
  • Used when undoing operations in a word processing package
• Implementation of a stack

  Can be implemented as either a static or dynamic data structure
• Static data structure implementation of a stack

  • Uses an array
  • Has a pointer to the top of the stack
  • Has a variable holding the size of the array (maximum size of the stack)
• Operations on a stack

  • push(item)
  • pop()
  • peek()
  • isEmpty()
  • isFull()
• push(item)


  Adds a new item to the top of the stack
• pop()


  Removes and returns the top item from the stack
• peek()


  Returns the top item from the stack but does not remove it
• isEmpty()


  Tests to see whether the stack is empty, and returns a Boolean value
• isFull()


  Tests to see whether the stack is full, and returns a Boolean value
• Stack operation


  1. s.isEmpty()

  2. s.push('Blue')

  3. s.push('Red')

  4. .push('Green')

  5. s.isEmpty

  6. s.peek()

  7. s.pop(
• isEmpty


  1. if top == -1 then

  2. return True

  3. else

  4. return False

  5. endif
• isFull


  1. if top == maxSize then

  2. return True

  3. else

  4. return False

  5. endif
• push (item)


  1. if is Full then

  2. print ("Stack is full")

  3. else

  4. top = top + 1

  5. s (top) = item

  6. endif
• A stack will always have a maximum size, because memory cannot grow indefinitely
• If the stack is implemented as an array, a full stack can be tested for by examining the value of the stack pointer
• An attempt to push another item onto the stack would cause overflow so an error message can be given to the user to avoid this
• If the stack pointer is -1, the stack is empty and underflow will occur if an attempt is made to pop an item
• Call stack


  A major use of the stack data structure is to store information about the active subroutines while a computer program is running
• Holding return addresses


  The call stack keeps track of the address of the instruction that control should return to when a subroutine ends (the return address)
• Nested subroutines


  1. Several subroutines may be nested, so that the stack may contain several return addresses which will be popped as each subroutine completes

  2. For example, a subroutine which draws a robot may call subroutines drawCircle, drawRectangle etc

  3. Subroutine drawRectangle may in turn call a subroutine drawline
• Recursive subroutine


  1. A recursive subroutine may contain several calls to itself, so that with each call, a new item (the return address) is pushed onto the stack

  2. When the recursion finally ends, the return addresses that have been pushed onto the stack are popped
• Some languages, such as Python, make it very easy to implement a stack using the built-in dynamic list data structure, with the top of the stack being the last element of the list
• The function len(a) can be used to determine whether the stack is empty, and if it is not, pop() will remove and return the top element
• The built-in method append(item) will append or push an item onto the top of the stack (the last element of the list)
• pop function


  1. if isEmpty then

  2. print ("Stack is empty")

  3. else

  4. items(top)

  5. top top-1

  6. return item

  7. endif

  8. endfunction
• Stack


  A data structure where items are pushed onto the stack each time a routine is called and popped one after the other each time the end of the subroutine is reached
• If the programmer makes an error and the recursion never ends

  Sooner or later memory will run out, the stack will overflow and the program will crash
• Holding parameters


  Parameters required for a subroutine (such as, for example, the centre coordinates, line colour and thickness for a circle subroutine) may be held on the call stack
• Each call to a subroutine will be given separate space on the call stack for these parameter values
• Local variables


  A subroutine frequently uses local variables which are accessible and usable only within the subroutine, and these may also be held in the call stack
• Each separate call to a subroutine gets its own space for its local variables
• Storing local variables on the call stack is much more efficient than using dynamic memory allocation, which uses heap space
• Call stack


  A call stack is composed of stack frames, where each stack frame corresponds to a call to a subroutine which has not yet terminated
• The stack pointer points to the top of the stack