Kĩ thuật lập trình - Stacks and queues

Stacks and QueuesCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Discuss different implementations of stacks and queuesLearn about applications of stacks and queues2pushpopStackQueueLIFO (Last-In-First-Out) access methodaddremoveFIFO (First-In-First-Out) access methodStacks and queues are used for temporary storage, but in different situations3Stacks are Used forhandling nested structures:processing directories within directoriesevaluating expressions within expressionshandling branching processes: traversing a branching tree structureplanning a move in a chess gametracking the sequence of method calls in a Java program4Stack: Array Implementation public void push (Object x) { myElements [sp] = x; sp++; } public Object pop ( ) { sp--; return myElements [sp]; }5ArrayList Implementation import java.util.ArrayList; public class ArrayStack { private ArrayList items; public ArrayStack ( ) { items = new ArrayList( ); } public boolean isEmpty ( ) { return items.isEmpty ( ); } public void push (Object x) { items.add (x); } public Object pop ( ) { return items.remove (items.size ( ) - 1); } public Object peek ( ) { return items.get (items.size ( ) - 1); } }6LinkedList Implementation import java.util.LinkedList; public class ListStack { private LinkedList items; public ListStack () { items = new LinkedList ( ); } public boolean isEmpty ( ) { return items.isEmpty ( ); } public void push (Object x) { items.addFirst (x); } public Object pop ( ) { return items.removeFirst ( ); } public Object peek ( ) { return items.getFirst ( ); } }7Properties of StacksIn an efficient implementation, push, pop, and peek methods run in O(1) time.A stack of objects holds references to objects.If necessary, a stack can hold multiple references to the same object.If you are not careful, an object can change while stored on the stack (unless that object is immutable).8java.util.Stack classPart of the Java Collections Framework (Chapter 20).A “generic” class (works with objects of specified type).Based on the legacy Vector class, similar to ArrayList.Methods: isEmpty, push, pop, peek.Has other methods  do not use them!9Stack Example: Matching Brackets public boolean bracketsMatch (String str) { Stack stk = new Stack ( ); for (int pos = 0; pos ( ); TreeNode node = root; while (node != null) { System.out.println (node.getValue ( )); if (node.getLeft ( ) != null ) { if (node.getRight ( ) != null ) stk.push (node.getRight ( )); node = node.getLeft ( ); } else if (node.getRight ( ) != null ) node = node.getRight ( ); else if (! stk.isEmpty ( )) node = stk.pop ( ); else node = null; } Save for future processingif no children, take the next node from the stack11Queues are used for:Processing events or messages in order of their arrivalSystem tasksQueueing print jobsEntering keystrokesProcessing mouse clicks12Queue: Ring-Buffer Implementation13Properties of QueuesIn an efficient implementation, add, remove, and peek methods run in O(1) time.A queue of objects holds references to objects.If necessary, a queue can hold multiple references to the same object.If you are not careful, an object can change while stored in the queue (unless that object is immutable).14The java.util.Queue InterfaceA “generic” interface, part of the Java Collections Framework (Chapter 20)Implemented by java.util.LinkedList boolean isEmpty () boolean add (E obj) E remove () E peek ()15Queue Example public Queue findMatches (Scanner input, String target) { Queue q = new LinkedList( ); while (input.hasNextLine ( )) { String line = input.nextLine ( ); if (line.indexOf (target) >= 0 ) q.add (line); } return q; }Returns a queue of all the lines that contain target public void process (Queue q) { while (! q.isEmpty ( )) { String s = q.remove ( ); ... // process s } }Processes the contents of q (leaves the queue empty)16Review:What are the two main operations for a stack?Name a few applications of stacks.Name the four methods of the java.util.Stack class.What are the two main operations for a queue?Name a few applications of queues.17Review (cont’d):Name the four methods of the java.util.Queue interface.Explain why a stack of objects can be equally efficiently implemented using an ArrayList or a LinkedList.Why is an ArrayList not as efficient for implementing a queue (unless you use a ring-buffer implementation)?18