Stack Notes

Stacks     

• A stack is a data structure in which all the  access is restricted to the most recently  inserted items. 

• If we remove this item, then we can  access the next-to-last item inserted, and  etc.

 • A stack is also a handy aid for algorithms  applied to certain complex data structures.

Stack Model     

• Input to a stack is by push     

• Access is by top     

• Deletion is by pop                                                         

    

Example     

• Stack contains 3, 4 

• Push item 9  – Now the stack contains 3,4, 9   

 • If we pop now, we get 9 

• If we pop again, we get 4                        

                    

   

Stack Properties    

• The last item added to the stack is placed  on the top and is easily accessible.     

• Thus the stack is appropriate if we expect  to access on the top item, all other items  are inaccessible.                                                            

    

 Important stack applications     

• Compiler Design

• Mathematical Expression Evaluation 

• Balanced Spell Checker 

• Simple Calculator                                                                  

    

The stack operations    

• clear() – Clear the stack 

• isEmpty()  – Check to see if the stack is empty

 • push(el)  – Put the element   el on top of the stack.

 • pop() – Take the topmost element from stack.

 • topEl() – Return the topmost element in the stack  without removing it.                                         

    

 Implementation Of Stacks    

• There are two basic ways to arrange for  constant time operations.   – The first is to store the items contiguously in  an array.  – And the second is to store items non- contiguously  in a linked list                                                            

   

Array Implementation    

• To push an item into an empty stack, we  insert it at array location 0. ( since all java  arrays start at  0)   • To push the next item into the location 0  over the location to make room for new  item.                                                              

• This is easily done by defining an auxiliary  integer variable  known as stack pointer, which  stores the array index currently being used as  the top of the stack.

 • A stack can be implemented with an array and  an integer. 

• The integer  TOS (top of stack) provides the  array index of the top element of the stack,  when  TOS is  –1 , the stack is empty.                  

  Stacks specifies two data fields   such as 

 •   The array (which is expanded as needed  stores  the items in the stack)            

•   TopOfStack ( TOS ) ( gives the index of  the current top of the stack, if stack is  empty, this index is –1.)            

 

Algorithms For Pushing & Popping  contd…    

PUSH 

• If stack is not full .

 •  then  Add 1 to the stack pointer. 

•  Store item at stack pointer location.                                             

   POP

 •  If stack is not empty

•  then  Read item at stack pointer location. 

•  Subtract 1 from the stack pointer.                                             

    

     Efficiency of Stacks    

• Items can be both pushed and popped  from the stack implemented in the Stack  class in constant O(1) time. 

 • That is, the time is not dependent on how  many items are in the stack, and is  therefore very quick.  

• No comparisons or moves are necessary.