Chris Kiekintveld CS 2401 (Fall 2010) Elementary Data Structures and Algorithms Stacks and QueuesTwo 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 2Java Programming: Program Design Including Data Structures 3 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 algorithmsJava Programming: Program Design Including Data Structures 4 Conceptual Stacks Figure 17-1 Various types of stacksJava Programming: Program Design Including Data Structures 5 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 stackJava Programming: Program Design Including Data Structures 6 Stacks (continued) Figure 17-3 Stack operationsJava Programming: Program Design Including Data Structures 7 Stacks (continued) Figure 17-4 UML diagram of the interface StackADTJava Programming: Program Design Including Data Structures 8 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 StackExceptionJava Programming: Program Design Including Data Structures 9 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 stackTopJava Programming: Program Design Including Data Structures 10 Implementation of Stacks as Arrays (continued) Figure 17-6 Example of a stackJava Programming: Program Design Including Data Structures 11 Constructors  Default constructor public StackClass() { maxStackSize = 100; stackTop = 0; //set stackTop to 0 list = (T[]) new Object[maxStackSize]; //create the array }//end default constructorJava Programming: Program Design Including Data Structures 12 Initialize Stack  Method initializeStack public void initializeStack() { for (int i = 0; i < stackTop; i++) list[i] = null; stackTop = 0; }//end initializeStackJava Programming: Program Design Including Data Structures 13 Empty Stack  Method isEmptyStack public boolean isEmptyStack() { return (stackTop == 0); }//end isEmptyStackJava Programming: Program Design Including Data Structures 14 Full Stack  Method isFullStack public boolean isFullStack() { return (stackTop == maxStackSize); }//end isFullStackJava Programming: Program Design Including Data Structures 15 Push  Method push public void push(T newItem) throws StackOverflowException { if (isFullStack()) throw new StackOverflowException(); list[stackTop] = newItem; //add newItem at the //top of the stack stackTop++; //increment stackTop }//end pushJava Programming: Program Design Including Data Structures 16 Peek  Method peek public T peek() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException(); return (T) list[stackTop - 1]; }//end peekJava Programming: Program Design Including Data Structures 17 Pop  Method pop public void pop() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException(); stackTop--; //decrement stackTop list[stackTop] = null; }//end popJava Programming: Program Design Including Data Structures 18 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 variableJava Programming: Program Design Including Data Structures 19 Linked Implementation of Stacks (continued) Figure 17-13 Nonempty linked stackJava Programming: Program Design Including Data Structures 20 Default Constructor  Default constructor public LinkedStackClass() { stackTop = null; }//end constructorJava Programming: Program Design Including Data Structures 21 Initialize Stack  Method initializeStack public void initializeStack() { stackTop = null; }//end initializeStackJava Programming: Program Design Including Data Structures 22 Empty Stack and Full Stack  Methods isEmptyStack and isFullStack public boolean isEmptyStack() { return (stackTop == null); }//end isEmptyStack public boolean isFullStack() { return false; }//end isFullStackJava Programming: Program Design Including Data Structures 23 Push  Method push public void push(T newElement) { StackNode<T> newNode; //reference variable to create //the new node newNode = new StackNode<T>(newElement, stackTop); //create //newNode and insert //before stackTop stackTop = newNode; //set stackTop to point to //the top element } //end pushJava Programming: Program Design Including Data Structures 24 Peek  Method peek public T peek() throws StackUnderflowException { if (stackTop == null) throw new StackUnderflowException(); return stackTop.info; }//end topJava Programming: Program Design Including Data Structures 25 Pop  Method pop public void pop() throws StackUnderflowException { if (stackTop == null) throw new StackUnderflowException(); stackTop = stackTop.link; //advance stackTop to the