Java程序辅导
C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解
C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解
Lab 8 Linked Lists, Stacks & Queues This lab is all about linked lists, stacks and queues. Below you will find a very short introduction to these data structures, and will practice one exercise on each one of them. 1. Linked Lists Linked lists are data structures made of components called nodes. In its simplest form a node holds one value and a reference to the next node. The figure below shows a linked list of 3 nodes, where the first node holds 42, the second -‐9 and the third 5. Note that the last node (with 5) has a reference to an odd symbol that means null, signaling the end of the linked list. The class Node below shows a generic node class. To create a node holding an integer you would write “Noden = new Node ();” Use <> just as with array lists to denote the type of value held in the node. public class Node { public T value; public Node next; } When handling linked lists you will be given the first node in the list (usually called head or root) to work your way down all nodes. For example the method below finds the tally of nodes in a list of integers. public static int size(Node head) { int count = 0; Node now = head; while (now != null) { count++; now = now.next; } return count; } Exercise 1 Write a class “ListExample” that has the method “getUppercaseList” below. public static Node getUppercaseList(Node head) This method receives a linked list of characters, and returns a linked list with all nodes from the input list holding an uppercase letter. The new list should preserve the original order of nodes in the input list. For example, given the list { 'B' , 'r' , 'o' , 'C' , 'c', 'o' , 'L' , 'i' } the method returns { 'B' , 'C' , 'L' }. Returned nodes must be the same nodes given as input, i.e, your method must not create new nodes but reuse the ones given. The value in each node is immutable but the reference to the next node is not (i.e., the field “next” can be changed). Nodes are implemented in the class “Node”, which is provided. Your class must not use static variables, arrays or Java collections (e.g., array list). Download the JUnit file ListExampleTest.java from the class website and import it into the project. Exercise 1 -‐ Get Instructor’s Signature 2. Stacks Stacks are data structures that resemble the way a tennis ball container work: if you want a tennis ball you can only take out the one on top; if you want to add a ball you can only add one through the top. In programming terms, adding an element to a stack is called “push”, and removing an element from the stack is called “pop”. In addition, there is a method “isEmpty” that tells whether the stack is empty. The figures below show a stack after adding and removing elements. On the first row, we add the numbers 42, -‐9 and 5. On the second row, we remove all elements from the stack. push( 42 ) push( -‐9 ) push( 5 ) after pushing 42, -‐9 & 5 pop() pop() pop() after popping 3 times Be aware that removing an element from the stack when it is empty throws an exception. As such you should use “isEmpty” to find out whether a stack is not empty before calling “pop”. The generic class “Stack” (snippet below) shows the common methods found in stacks. When creating a stack of integers you should write “Stack s = new Stack ();” Use <> just as with array lists to denote the type of values held in the stack. public class Stack { public void push(T value) { … }; public T pop() { … }; public boolean isEmpty() { … }; } The method below shows how to count the elements in a stack of integers. Be aware that this method removes all elements from the stack and does not put them back (you would need a temporary stack to store every removed element and a loop to add them back to the original stack after counting them). public static int size(Stack stack) { int count = 0; while (!stack.isEmpty()) { stack.pop(); count++; } return count; } Exercise 2 Write a class “StackExample” that has the method “getEvenNumbers” below. public static Stack getEvenNumbers(Stack stack) The method receives a stack of integers (implemented in the provided Stack class) and returns a new stack with all even numbers from the initial stack (preserving their original order). For example, given the stack { 4, 5, 3, 2, 6, 9, 2 } (where 4 is at the top of the stack), the method returns { 4, 2, 6, 2 }. The initial stack should retain its original values when the method ends. The class Stack has methods: push (to add an integer to the stack), pop (to remove an integer from the stack) and isEmpty (to know whether the stack is empty or not). Your class must not use static variables, arrays or Java collections (e.g., array list). Download the JUnit file StackExampleTest.java from the class website and import it into the project. Exercise 2 -‐ Get Instructor’s Signature 3. Queues Queues are data structures that can be imagined as a line of customers: customers enter on one end (usually referred to as the “back”) and they leave from the other end (referred to as the “front”). Differently than in real life, elements in a queue can only leave from the front, never in between or back. In programming terms, adding an element to a queue is known as “enqueue” and removing an element is known as “dequeue”. Also, the method “isEmpty” says whether the queue is empty. The figures below show a queue of integers after adding and removing elements. The first 2 rows show the stack when adding 42, -‐9 and 5. The last 2 rows show the stack when removing all its elements. enqueue( 42 ) enqueue( -‐9 ) enqueue( 5 ) after enqueuing 42, -‐9 & 5 dequeue() dequeue() dequeue() after dequeuing 3 times. The generic class “Queue” (snippet below) shows the common methods found in queues. When creating a queue of integers you should write “Queue q = new Queue ();” Use <> just as with array lists to denote the type of the values held in the queue. public class Queue { public void enqueue(T value) { … }; public T dequeue() { … }; public boolean isEmpty() { … }; } Be aware that removing an element from the queue when it is empty throws an exception. As such you should use “isEmpty” to find out whether a queue is not empty before calling “dequeue”. The method below shows how to count the elements in a queue of integers. This method removes all elements from the queue and does not put them back (you would need a temporary queue to store every removed element and a loop to add them back to the original queue after counting them). public static int size(Queue queue) { int count = 0; while (!queue.isEmpty()) { queue.dequeue(); count++; } return count; } Exercise 3 Pipi Longstockings has a PEZ dispenser from where she gets candy one at a time. Being slightly unconventional Pipi eats her candy differently each day of the week. On Mondays she eats them one by one in the order they come out from the dispenser. On Tuesdays she eats one candy and adds the next candy back to the bottom of the dispenser. On Wednesdays, she eats one candy and adds the next two back to the bottom of the dispenser (in the same order they were taken off). On Thursday she eats one candy and puts back at the bottom of the dispenser the next 3 candies, and so on, until Sunday, when she eats one candy and puts back the next 6 candies. Write a class “QueueExample” method with the method “getCandy” (below) that simulates Pipi’s candy-‐ eating routine. public static Queue getCandy(Queue dispenser, int day) This method receives a queue candy dispenser (implemented in the class Queue) and a day of the week (where Monday is 0, Tuesday 1, and so on until 6 for Sunday), and returns a new queue with the candy Pipi ate, in the order she ate it, until the time the dispenser is empty. For simplicity, we can identify candy by its flavor, which can be Blue Raspberry, Chocolate, Cola, Grape, Green Apple, Lemon, Orange, Peppermint, Raspberry, and Watermelon. For example, given a dispenser with 4 candy { Chocolate, Cola, Peppermint, BlueRaspberry } (where Chocolate is at the head of the queue) and day 1 (Tuesday) the method returns { Chocolate, Peppermint, Cola, BlueRaspberry }. In this example, Pipi eats one candy (Chocolate) and puts back the next candy (Cola) leaving the queue { Peppermint, BlueRaspberry, Cola }. She then eats another candy (Peppermint) and puts back the next candy (BlueRaspberry) leaving the queue { Cola, BlueRaspberry }. Next Pipi eats another candy (Cola) and puts back the next candy (BlueRaspberry) leaving the queue { BlueRaspberry }. Pipi then eats the last candy (BlueRaspberry) leaving the queue empty. The class Queue has methods: enqueue (to add a candy to the queue), dequeue (to remove a candy from the queue) and isEmpty (to know whether the queue is empty or not). Be aware that the dispenser can be empty. Your class must not use static variables, arrays or Java collections (e.g., array list). Download the JUnit file QueueExampleTest.java from the class website and import it into the project. Exercise 3 -‐ Get Instructor’s Signature Lab 8 Instructor’s Signature Page Student’s Name: ___________________________________________ Student ID _________________ Exercise 1: ___________________________ JUnit tests passed: ____________ Exercise 2: ___________________________ JUnit tests passed: ____________ Exercise 3: ___________________________ JUnit tests passed: ____________