Stacks, Queues and Linked Stacks, computer science homework help

1 Stacks and Queues Based on D.S. Malik, Java Programming: Program Design Including Data Structures 2 Stacks  Lists of homogeneous elements  Addition and deletion of elements occur only at one end, called the top of the stack  The middle elements of the stack are inaccessible  Computers use stacks to implement method calls  Real life examples? 3 Stacks Figure 17 -1 Various types of stacks 4 Stacks  Stacks are also called Last In First Out (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 5 Stacks Figure 17 -3 Stack operations 6 Stacks Figure 17 -4 UML diagram of the interface StackADT 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 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 9 Implementation of Stacks as Arrays Figure 17 -5 UML class diagram of the class StackClass 10 Implementation of Stacks as Arrays Figure 17 -6 Example of a stack 11 Stacks (Methods)  Default constructor public StackClass() { maxStackSize = 100; stackTop = - 1; //set stackTop to - 1 //create the array list = (T[]) new Object[maxStackSize]; }  Method initializeStack public void initializeStack(){ for (int i = 0; i < maxStackSize; i++) list[i] = null; stackTop = - 1; } 12 Stacks (Methods)  Method isEmptyStack public boolean isEmptyStack(){ return (stackTop == - 1); }  Method isFullStack public boolean isFullStack() { return (stackTop == maxStackSize - 1); } 13 Stacks (Methods)  Method push public void push(T newItem) throws StackOverflowException { if (isFullStack()) throw new StackOverflowException(); list[++stackTop] = newItem; //add newItem //stackTop++; //increment stackTop }  Method pop public void pop() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException(); stackTop -- ; //decrement stackTop //list[stackTop -- ] = null; } 14 Stacks (Methods)  Method peek public T peek() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException(); return (T) list[stackTop - 1]; } 15 Linked List 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 16 Linked Implementation of Stacks (continued) Figure 17 -13 Nonempty linked stack 17 Stacks (Methods)  Default constructor public LinkedStackClass() { stackTop = null; }  Method initializeStack public void initializeStack() { stackTop = null; } 18 Stacks (Methods)  Method isEmptyStack public boolean isEmptyStack() { return (stackTop == null); }  Method isFullStack public boolean isFullStack() { return false; } 19 Stacks (Methods)  Method push public void push(T newElement) { StackNode newNode; //reference variable newNode = new StackNode(newElement, stackTop); //insert before stackTop stackTop = newNode; }  Method pop public void pop() throws StackUnderflowException { if (stackTop == null) throw new StackUnderflowException(); stackTop = stackTop.link; //advance stackTop } 20 Stacks (Methods)  Method peek public T peek() throws StackUnderflowException { if (stackTop == null) throw new StackUnderflowException(); return stackTop.info; } 21 Queues  Data structure in which the elements are added at one end, called the rear , and deleted from the other end, called the front.  As in a stack, the middle elements of the queue are inaccessible.  A queue is a First In First Out (FIFO) data structure. 22 Queue Operations  Queue operations  initializeQueue  isEmptyQueue  isFullQueue  front  back  addQueue (OR: enqueue)  deleteQueue (OR: dequeue) 23 QueueException Class  Adding an element to a full queue and removing an element from an empty queue would generate errors or exceptions  Queue overflow exception  Queue underflow exception  Classes that handle these exceptions  QueueException extends RunTimeException  QueueOverflowException extends QueueException  QueueUnderflowException extends QueueException 24 Implementation of Queues as Arrays  Instance variables  An array to store the queue elements  queueFront: keeps track of the first element  queueRear: keeps track of the last element  maxQueueSize : specifies the maximum size of the queues 25 Implementation of Queues as Arrays Figure 17 -42 Queue after three addQueue operations 26 Implementation of Queues as Arrays Figure 17 -43 Queue after the deleteQueue operation CORRECTION: queueFront = 1 27 Implementation of Queues as Arrays  Problems with this implementation  Arrays have fixed sizes  After various insertion and deletion operations, queueRear will point to the last array position  Giving the impression that the queue is full  Solutions  Slide all of the queue elements toward the first array position  Use a circular array 28 Implementation of Queues as Arrays Figure 17 -45 Circular queue 29 Implementation of Queues as Arrays Figure 17 -46 Queue with two elements at positions 98 and 99 30 Implementation of Queues as Arrays Figure 17 -47 Queue after one more addQueue operation 31 Queues (Methods)  Default constructor public QueueClass(){ maxQueueSize = 100; queueFront = 0; queueRear = maxQueueSize - 1; count = 0; list = (T[]) new Object[maxQueueSize]; }  Method initilializeQueue public void initializeQueue(){ for (int i = queueFront; i < queueRear; i = (i + 1) % maxQueueSize) list[i] = null; queueFront = 0; queueRear = maxQueueSize - 1; count = 0; } 32 Queues (Methods)  Method isEmptyQueue public boolean isEmptyQueue() { return (count == 0); }  Method isFullQueue public boolean isFullQueue() { return (count == maxQueueSize); } 33 Queues (Methods)  Method front public T front() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); return (T) list[queueFront]; }  Method back public T back() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); return (T) list[queueRear]; } 34 Enqueue /addQueue  Method addQueue public void addQueue(T queueElement)throws QueueOverflowException { if (isFullQueue()) throw new QueueOverflowException(); //circular array  use % op. to advance queueRear queueRear = (queueRear + 1) % maxQueueSize; count++; list[queueRear] = queueElement; } 35 Dequeue /deleteQueue  Method deleteQueue public void deleteQueue() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); count -- ; list[queueFront] = null; //circular array  use % op. to advance queueFront queueFront = (queueFront + 1) % maxQueueSize; } 36 Linked Implementation of Queues  Simplifies many of the special cases of the array implementation  Because the memory to store a queue element is allocated dynamically, the queue is never full  Class LinkedQueueClass implements a queue as a linked data structure  It uses nodes of type QueueNode 37 Queues (Methods)  Method initializeQueue public void initializeQueue(){ queueFront = null; queueRear = null; }  Method isEmptyQueue public boolean isEmptyQueue(){ return (queueFront == null); }  Method isFullQueue public boolean isFullQueue(){ return false; } 38 Enqueue / addQueue  Method addQueue public void addQueue(T newElement) { QueueNode newNode; newNode = new QueueNode(newElement, null); if (queueFront == null) {//empty list? queueFront = newNode; queueRear = newNode; } else { //not empty  add newNode at the end queueRear.link = newNode; queueRear = queueRear.link; } } 39 Queues (Methods)  Method front public T front() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); return queueFront.info; }  Method back public T back() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); return queueRear.info; } 40 Dequeue / deleteQueue  Method deleteQueue public void deleteQueue() throws QueueUnderflowException { if (isEmptyQueue()) throw new QueueUnderflowException(); //advance queueFront queueFront = queueFront.link; //if after deletion the queue is empty if (queueFront == null) queueRear = null; }