Question? Leave a message!




Stacks and Queues

Stacks and Queues 11
GraceRogers Profile Pic
GraceRogers,Greece,Professional
Published Date:12-07-2017
Website URL
Comment
Stacks and Queues Chris Kiekintveld CS 2401 (Fall 2010) Elementary Data Structures and Algorithms Two New ADTs   Define two new abstract data types   Both are restricted lists   Can be implemented using arrays or linked lists   Stacks   “Last In First Out” (LIFO)   Queues   “First In First Out” (FIFO) Java Programming: Program Design Including Data Structures 2 Stacks   List of the same kind of elements   Addition and deletion of elements occur only at one end, called the top of the stack   Computers use stacks to implement method calls   Stacks are also used to convert recursive algorithms into nonrecursive algorithms Java Programming: Program Design Including Data Structures 3 Conceptual Stacks Figure 17-1 Various types of stacks Java Programming: Program Design Including Data Structures 4 Stacks (continued)   Stacks are also called Last Input First Output (LIFO) data structures   Operations performed on stacks   Push: adds an element to the stack   Pop: removes an element from the stack   Peek: looks at the top element of the stack Java Programming: Program Design Including Data Structures 5 Stacks (continued) Figure 17-3 Stack operations Java Programming: Program Design Including Data Structures 6 Stacks (continued) Figure 17-4 UML diagram of the interface StackADT Java Programming: Program Design Including Data Structures 7 StackException Class   Adding an element to a full stack and removing an element from an empty stack would generate errors or exceptions   Stack overflow exception   Stack underflow exception   Classes that handle these exceptions   StackException extends RunTimeException   StackOverflowException extends StackException   StackUnderflowException extends StackException Java Programming: Program Design Including Data Structures 8 Implementation of Stacks as Arrays   The array implementing a stack is an array of reference variables   Each element of the stack can be assigned to an array slot   The top of the stack is the index of the last element added to the stack   To keep track of the top position, declare a variable called stackTop Java Programming: Program Design Including Data Structures 9 Implementation of Stacks as Arrays (continued) Figure 17-6 Example of a stack Java Programming: Program Design Including Data Structures 10 Constructors   Default constructor public StackClass() maxStackSize = 100; stackTop = 0; //set stackTop to 0 list = (T) new ObjectmaxStackSize; //create the array //end default constructor Java Programming: Program Design Including Data Structures 11 Initialize Stack   Method initializeStack public void initializeStack() for (int i = 0; i stackTop; i++) listi = null; stackTop = 0; //end initializeStack Java Programming: Program Design Including Data Structures 12 Empty Stack   Method isEmptyStack public boolean isEmptyStack() return (stackTop == 0); //end isEmptyStack Java Programming: Program Design Including Data Structures 13 Full Stack   Method isFullStack public boolean isFullStack() return (stackTop == maxStackSize); //end isFullStack Java Programming: Program Design Including Data Structures 14 Push   Method push public void push(T newItem) throws StackOverflowException if (isFullStack()) throw new StackOverflowException(); liststackTop = newItem; //add newItem at the //top of the stack stackTop++; //increment stackTop //end push Java Programming: Program Design Including Data Structures 15 Peek   Method peek public T peek() throws StackUnderflowException if (isEmptyStack()) throw new StackUnderflowException(); return (T) liststackTop - 1; //end peek Java Programming: Program Design Including Data Structures 16 Pop   Method pop public void pop() throws StackUnderflowException if (isEmptyStack()) throw new StackUnderflowException(); stackTop; //decrement stackTop liststackTop = null; //end pop Java Programming: Program Design Including Data Structures 17 Linked Implementation of Stacks   Arrays have fixed sizes   Only a fixed number of elements can be pushed onto the stack   Dynamically allocate memory using reference variables   Implement a stack dynamically   Similar to the array representation, stackTop is used to locate the top element  stackTop is now a reference variable Java Programming: Program Design Including Data Structures 18 Linked Implementation of Stacks (continued) Figure 17-13 Nonempty linked stack Java Programming: Program Design Including Data Structures 19 Default Constructor   Default constructor public LinkedStackClass() stackTop = null; //end constructor Java Programming: Program Design Including Data Structures 20