tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (2nd AP edition): Chapter 22 - Maria Litvin, Gary Litvin

Chapter 22 - Stacks and queues. After you have mastered the material in this chapter, you will be able to: Discuss different implementations of stacks and queues, learn about applications of stacks and queues. | Stacks and Queues Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 22- This chapter also contains a case study on asynchronous computing architectures (Actors). Objectives: Discuss different implementations of stacks and queues Learn about applications of stacks and queues 22- It is useful to compare these two data structures. push pop Stack Queue LIFO (Last-In-First-Out) access method add remove FIFO (First-In-First-Out) access method Stacks and queues are used for temporary storage, but in different situations 22- The queue operations are sometimes called enqueue and dequeue, but Java uses add and remove. Stacks are Used for handling nested structures: processing directories within directories evaluating expressions within expressions handling branching processes: traversing a branching tree structure planning | Stacks and Queues Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 22- This chapter also contains a case study on asynchronous computing architectures (Actors). Objectives: Discuss different implementations of stacks and queues Learn about applications of stacks and queues 22- It is useful to compare these two data structures. push pop Stack Queue LIFO (Last-In-First-Out) access method add remove FIFO (First-In-First-Out) access method Stacks and queues are used for temporary storage, but in different situations 22- The queue operations are sometimes called enqueue and dequeue, but Java uses add and remove. Stacks are Used for handling nested structures: processing directories within directories evaluating expressions within expressions handling branching processes: traversing a branching tree structure planning a move in a chess game tracking the sequence of method calls in a Java program 22- Often recursion is a more straightforward way of handling such tasks. Recursive method calls use the system stack behind the scenes. Stack: Array Implementation public void push (Object x) { myElements [sp] = x; sp++; } public Object pop ( ) { sp--; return myElements [sp]; } 22- In this implementation, the stack pointer points to the next available slot. In another implementation it might point to the top value. ArrayList Implementation import ; public class ArrayStack { private ArrayList items; public ArrayStack ( ) { items = new ArrayList( ); } public boolean isEmpty ( ) { return ( ); } public void push (Object x) { (x); } public Object pop ( ) { return ( ( ) - 1); } public Object peek ( ) { return ( ( ) - 1); } } 22- A simple and efficient implementation. LinkedList Implementation import