Short Stories

31 pages
6 views

Stacks, Queues, and Linked Lists

of 31
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Stacks, Queues, and Linked Lists
Transcript
  1Stacks, Queues, and Linked Lists S TACKS ,Q UEUES , AND L INKED L ISTS •Stacks•Queues•Linked Lists•Double-Ended Queues•Case Study: A Stock Analysis Applet  2Stacks, Queues, and Linked Lists Stacks •Astack isacontainerofobjectsthatareinsertedandremoved according to thelast-in-first-out (LIFO) principle.•Objectscanbeinsertedatanytime,butonlythelast(the most-recently inserted) object can be removed.•Inserting an item is known as “pushing” onto thestack. “Popping” off the stack is synonymous withremoving an item.•A PEZ ®  dispenser as an analogy:  3Stacks, Queues, and Linked Lists The Stack Abstract Data Type •A stack is anabstract data type (ADT) that supportstwo main methods:-push( o ):Inserts object  o  onto top of stack   Input  : Object;  Output  : none-pop():Removes the top object ofstack andreturnsit;ifstackisemptyanerroroccurs  Input  : none;  Output  : Object•The following support methods should also bedefined:-size():Returnsthenumberofobjectsinstack   Input  : none;  Output  : integer-isEmpty():Returnabooleanindicatingifstackisempty.  Input  : none;  Output  : boolean-top():return the top object of the stack,withoutremoving it; if the stack isempty an erroroccurs.  Input  : none;  Output  : Object  4Stacks, Queues, and Linked Lists A Stack Interface in Java •While,thestackdatastructureisa“built-in”classof Java’s  java.util package,itispossible,andsometimespreferable to define your own specific one, like this: public interface Stack {  // accessor methods public int size(); // return the number of// elements in the stack public boolean isEmpty(); // see if the stack// is empty public Object top() // return the top element throws StackEmptyException; // if called on//an empty stack// update methods public void push (Object element); // push an// element onto the stack public Object pop() // return and remove the// top element of the stack throws StackEmptyException; // if called on// an empty stack }  5Stacks, Queues, and Linked Lists An Array-Based Stack •Create a stack using an array by specifying amaximum size  N   for our stack, e.g.  N   = 1,000.•The stack consists of an  N  -element array  S   and aninteger variable  t  , the index of the top element inarray  S  .•Array indices start at 0, so we initialize  t   to -1•Pseudo-code Algorithm  size():return  t   +1 Algorithm  isEmpty():return ( t  <0) Algorithm  top(): if   isEmpty() then throw a StackEmptyExceptionreturn  S  [ t  ] ... S  0 1 2  N  − 1 t  ...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks