Đang chuẩn bị liên kết để tải về tài liệu:
Lecture note Java methods A & AB: Object-oriented programming and data structures: Chapter 21 - Maria Litvin, Gary Litvin

Chapter 21 - 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. | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Stacks and Queues 21- 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 21- These two data structures are in contract with each other. 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 21- 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 . | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Stacks and Queues 21- 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 21- These two data structures are in contract with each other. 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 21- 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 21- 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]; } 21- 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 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); } } 21- A simple and efficient implementation. LinkedList Implementation import java.util.LinkedList; .