![]() * * You should have received a copy of the GNU General Public License * along with algs4.jar. See the * GNU General Public License for more details. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 1-X. * * This implementation uses a singly linked list with a non-static nested class * for linked-list nodes. ****************************************************************************** * Compilation: javac LinkedQueue.java * Execution: java LinkedQueue enqueue and dequeue * operations, along with methods for peeking at the first item, * testing if the queue is empty, and iterating through * the items in FIFO order. * of course).Below is the syntax highlighted version of LinkedQueue.java. * object contains only a single link to its tail node (null for the empty queue ![]() * An implementation of a queue using a ring of singly linked nodes. Here is an implementation using the circular queue:ĬircularLinkedQueue.java import In practice, however, we get a slightly simpler implementation if we store only a link to the tail node and link the tail to the head, like so: When you are learning to program with linked structures, it’s a great exercise. You are encouraged to implement the interface with a structure like this, and it is certainly doable, but there are a lot of special cases. Now we could store direct head and tail links in the object: Since we are adding at the tail and removing from the head, we need direct access to both ends. Let’s start with a linked representation. * Returns whether the queue is empty or not.Īs usual, we have many choices. * Returns the number of items currently in the queue. * Returns the front item from the queue without popping it. * Removes the front item from the queue and returns it. * Adds the given item to the rear of the queue. * it is empty, add and remove items, and peek at the front item. You can query the size of the queue and ask whether You need to know how to code things up when you find yourself in a very restrictive environment that doesn't have a collections library.Job interviews sometimes involve implementing queues on a whiteboard.You need coding practice, especially with linked structures.This is the best way for you to really learn how queues work behind the scenes. ![]() Yes, it’s true: there's already a Queue interface in the Java Core API and a whole bunch of implementing subclasses (AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, PriorityBlockingQueue, PriorityQueue, SynchronousQueue), but we're going to write some queues from scratch because: Queues are seen often in computer science. isEmpty: return whether the queue has no items.size: return the number of items in the queue.peek: return the item at the head (without removing it).Addition takes place only at the tail, and removal takes place only at the head. Chapter 4: Linked Lists and Iterators Often a double-ended singly linked list is used to implement the structure Queue.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |