3 knapsack, queue and stack - algorithm 4

There are three data types: bag, queue and stack They differ in the order in which objects are deleted and accessed

target

  • It shows that the way we represent objects in the collection will directly affect the efficiency of various operations
  • Introducing generics and iterations
  • Explain the importance of chained data structures

API

Each API contains a parameterless constructor, a method to add a single element to the collection, a method to test whether the collection is empty, and a method to return the size of the collection Both Stack and Queue contain a method that can delete specific elements in a collection

generic paradigm

A key feature of an abstract data type of a collection class is that we should be able to use them to store any type of data A special Java mechanism can do this. It is called generics, or parameterized types

Automatic packing

Type parameters must be instantiated as reference types Because Java has a special mechanism to enable generic code to handle primitive data types We remember that the encapsulation types of Java are the reference types corresponding to the original data types:
Boolean, byte, character, double, float, integer, long and short correspond to Boolean, byte, char, double, float, int, long and short respectively
When processing assignment statements, method parameters and arithmetic or logical expressions, Java will automatically convert between the reference type and the corresponding original type Here, this transformation helps us to use both generic and raw data types

Stack<Integer> stack = new Stack<>();
stack.push(17); //Auto Boxing (int ->integer)
int i = stack.pop();//Automatic unpacking (integer->int)
  • Auto boxing: automatically convert an original data type to an encapsulated data type as auto boxing
  • Automatic unpacking: automatically converting a package type to an original data type is called automatic unpacking

Iteratable collection elements

For many application scenarios, the requirement of use cases is only to process each element in the collection in some way, or to iterate through all elements in the collection
Suppose a transaction set is maintained in the Queue, as follows:

Queue<Transaction> collection = new Queue<>();

If the set is iteratable, the list of sets can be printed in one sentence

for(Transaction t : collection){
	System.out.println(t);
}

This statement is called a foreach statement

knapsack

Knapsack is a collection data type that does not support deleting elements from it - its purpose is to help use cases collect elements and iteratively traverse the number of all collected elements (use cases can also check whether the knapsack is empty or obtain the number of elements in the knapsack)

package basis.Knapsack queue stack;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;


/**
 * Defining a generic knapsack class
 */
public class Bag<Item> implements Iterable<Item> {
    //Generic element list
    private Node<Item> first;
    //Number of elements
    private int n;
    //The element pointed to by the current linked list
    private Node<Item> curr;

    /**
     * Create a control Backpack
     */
    public Bag() {
        curr=first;
    }

    /**
     * Add an element
     * @param item
     */
    public void add(Item item){
        Node<Item> oldFirst = first;
        Node<Item> first = new Node<>();
        first.var=item;
        first.next=oldFirst;
        this.first=first;
        n++;
    }

    /**
     * Whether the backpack is empty
     * @return
     */
    public boolean isEmpty(){

        return first==null;
    }
//    public Iterator iterator(){
//        return (Iterator) new ListIterator<Item>(first);
//    }

    /**
     * Number of elements in the backpack
     * @return
     */
    public int size(){
        return n;
    }

    /**
     * Implement an iterator
     * @return
     */
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator<>(first);

    }

    /**
     * Concrete iterator implementation
     * @param <Item>
     */
    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> current;

        /**
         * Use the linked list sub elements of the backpack
         * @param first
         */
        public ListIterator(Node<Item> first) {
            this.current = first;
        }

        /**
         * Whether the linked list is empty
         * @return
         */
        public boolean hasNext() {
            return current != null;
        }
        public void remove(){
            throw new UnsupportedOperationException();
        }

        /**
         * The next element of the current linked list
         * @return
         */
        public Item next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            Item item = current.var;
            current=current.next;
            return item;
        }
    }

    /**
     * A simple linked list
     * @param <Item>
     */
    class Node<Item>{
        private Item var;
        private Node next;

        public Node(Item var) {
            this.var = var;
        }

        public Node() {
        }
    }

}

package basis.Knapsack queue stack;

import java.util.Scanner;

/**
 * Average and standard deviation
 */
public class Stats {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Bag<Double> numbers = new Bag<>();
        //Termination pattern is 0; Type is ctrl+z
        while (!in.hasNext("0")){
            numbers.add(in.nextDouble());

        }
        int N = numbers.size();
        double sum = 0.0;
        for (double x : numbers){
            sum+=x;
        }
        double mean = sum/N;
        sum = 0.0;
        for (double x : numbers){
            sum+=(x-mean)*(x-mean);

        }
        //N-1 is because the calculation accuracy is higher
        double std = Math.sqrt(sum/(N-1));
        System.out.println("Mean: "+String.format("%.2f",mean));
        System.out.println("Std dev: "+String.format("%.2f",std));
    }
}

First in first out queue

First in first out queue (queue for short) is a collection type based on first in first out (FIFO) policy
API implementation

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * First in first out queue
 * @param <Item>
 */
public class Queue<Item> implements Iterable<Item> {
    //Double linked list queue
    private Node<Item> first;
    private Node<Item> last;
    private int n;

    /**
     * Add an element
     * @param item
     */
    public void enqueue(Item item){
        Node<Item> oldLast = last;
        last.var=item;
        last.next=null;
        if (isEmpty()){
            first = last;
        }else{
            oldLast.next=last;
        }
        n++;
    }

    public int size(){
        return n;
    }
    /**
     * Delete header element
     */
    public Item dequeue(){
        if (isEmpty()){

            throw new NoSuchElementException();
        }
        Item item = first.var;
        if (first.next != null){
            first=first.next;
        }else{
            first=last=null;
        }
        n--;
        return item;
    }

    /**
     * Empty Constructor 
     */
    public Queue() {

    }

    /**
     * Is it empty
     * @return
     */
    public boolean isEmpty(){
        return first == null;
    }

    /**
     * iterator 
     * @return
     */
    @Override
    public Iterator<Item> iterator() {
        return new QueueStack(first);
    }
    private class QueueStack implements Iterator<Item>{
        private Node<Item> current;

        public QueueStack(Node<Item> first) {
            this.current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            Item item = current.var;
            current=current.next;
            return item;
        }
    }
}

    /**
     * First in first out
     * @param name
     * @return
     * @throws InterruptedException
     */
    public static int[] readInts(String name) throws InterruptedException {
        Scanner in = new Scanner(System.in);
        Queue<Integer> q = new Queue<>();
        int N = 0;
        while (!in.hasNext("EOF")){
            q.enqueue(in.nextInt());
            N++;
        }
        int [] a = new int[N];
        for (int i = 0; i < N; i ++){
            a[i] = q.dequeue();
        }
        return a;

    }

Push down stack

Push down stack (or stack for short) is a collection type based on last in first out (LIFO) policy

  • Implementation of data type of downstack
package basis.Knapsack queue stack;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Push down stack
 * @param <Item>
 */
public class Stack<Item> implements Iterable<Item> {
    //Press down the top of the stack
    private Node<Item> first;
    //Number of elements
    private int n;

    /**
     * Empty Constructor 
     */
    public Stack() {
    }

    /**
     * Add an element
     * @param item
     */
    public void push(Item item){
        Node<Item> oldFirst = first;
        first = new Node<>();
        first.var=item;
        first.next=oldFirst;
        n++;
    }

    /**
     * Delete recently added elements
     * @return
     */
    public Item pop(){
        if (first == null){
            throw new NoSuchElementException();
        }
        Item item = first.var;
        if (first.next == null){
            first= null;
        }else{
            first=first.next;
        }
        n--;
        return item;
    }

    /**
     * Whether the stack is empty
     * @return
     */
    public boolean isEmpty(){
        return first==null;
    }

    /**
     * Number of elements in the stack
     * @return
     */
    public int size(){
        return n;
    }


    @Override
    public Iterator<Item> iterator() {
        return new StackIterator(first);
    }
    private class  StackIterator implements Iterator<Item>{
        private Node<Item> current;

        public StackIterator(Node<Item> first) {
            this.current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            Item item = current.var;
            current = current.next;
            return item;
        }
    }
}

import java.util.Scanner;

public class Reverse {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Stack<Integer> stack;
        stack = new Stack<>();
        while (!in.hasNext("EOF")){
            stack.push(in.nextInt());
        }
        while (!stack.empty()){
            System.out.println(stack.pop());
        }

    }
}

Evaluation of arithmetic expressions

Another stack use case we will learn is also a classic example to show generic applications Is to calculate the value of an arithmetic expression, for example (1+ ((2+3) (45))
If you multiply 4 by 5, add 3 to 2, take their product and add 1, you get 101
An expression consists of parentheses, operators, and operands (numbers) We send these entities to the stack one by one from left to right according to the following four situations:

  • Push operand into operand stack
  • Push operator onto operator stack
  • Ignore left parenthesis
  • When the closing bracket is encountered, an operator pops up, pops up the required number of operands, and pushes the operation results of the operator and operand into the operand stack
    After processing the last bracket, there will only be one value on the operand stack, which is the value of the expression
package basis.Knapsack queue stack;

import java.util.Scanner;
import java.util.Stack;

/**
 * Dijkstra Double stack arithmetic expression evaluation algorithm based on
 */
public class Evaluate {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        while (!in.hasNext("EOF")){
            //Read characters and push them onto the stack if they are operators
            String s = in.next();
            if (s.equals("("));
            else if(s.equals("+")) ops.push(s);
            else if(s.equals("-")) ops.push(s);
            else if(s.equals("*")) ops.push(s);
            else if(s.equals("/")) ops.push(s);
            else if(s.equals("sqrt")) ops.push(s);
            else if(s.equals(")")){
                //If it is a right parenthesis, pop up the operator and operand, evaluate the result and push it onto the stack
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop()+v;
                else if (op.equals("-")) v = vals.pop()-v;
                else if (op.equals("*")) v = vals.pop()*v;
                else if (op.equals("/")) v = vals.pop()/v;
                else if (op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            }
            //If the character is neither an operator nor a bracket, push it onto the stack as a dpuble value
            else {
                vals.push(Double.valueOf(s));
            }
        }
        //Final answer
        System.out.println(vals.pop());
    }
}

iteration

One of the basic operations of a collection class data type is to iterate through each element in the collection using Java foreach statements The code of this method is clear and concise, and does not depend on the specific implementation of the collection data type Before discussing the implementation of iteration, let's take a look at the use case code that can print all the elements in a string set:

Stack<String> collection = new Stack<>();
for(String s : collection){
System.out.println(s);

The foreach statement here is a shorthand for the while statement (just like the for statement) It is essentially equivalent to the while statement:

Iterator<String> i = collection.iterator();
while(iterator.hasNext()){
	String s = iterator.next();
	System.out.println(s);	
	}

This code shows us something we need to implement in any iteratable collection data type
**-The collection data type must implement an iterator() method and return an Iterator object

  • The Iterator class must contain two methods: hasnext () (returns a Boolean value) and next () (returns a generic element in the collection)**

In Java, we use the interface mechanism to specify the methods that a class must implement For the iteratable collection data type, Java has defined the required interface for us To make a class of iteratable,

  • The first step is to add implements Iterable to his declaration. The corresponding interface (i.e. java.lang.Iterable) is:
    public interface Iterable{
    Iterator iterator();
    }
  • Then add a method iterator() to the class and return an Iterator Iterators are generic, so we can use the parameter Item to help traverse any type of object they specify For the array representation we have been using, we need to iterate through the array in reverse order, so we name the Iterator ReverseArrayIterator and add the following methods
public Iterator<Item>  iterator(){
		return new ReverseArrayIterator();
	}

What is an iterator? It is an object of a class that implements the hasNext() and Next() methods. It is defined by the following interface, namely java Lang.iterator

public interface Iterator<Item>{
		boolean hasNext();
		Item next();
		void remove();
	}

Although a remove method is defined in the interface, the remove() method in this book is always empty. Therefore, we hope to avoid inserting operations that can modify the data structure in the iteration For the ReverseArrayIterator, these methods require only one line of code and are implemented in a nested class in the stack class:

private class ReverseArrayIterator implements Iterator<Item>{
		private int =N;
		public bolean hasNext(){ return i > 0;}
		public Item next() {return }
	}

Note that a nested class can access the instance variables of its class, which are a[] and n (this is the main reason why we use nested classes to implement iterators)
From a technical point of view, in order to be consistent with the structure of the Iterator, we should run exceptions in two cases; If the use case calls remove(), an UnsupportedOperationException will be thrown. If i is 0 when the use case calls next(), a NoSuchElementException will be thrown Because we only use iterators in foreach syntax, these situations will not occur, so we omit this part of the code There is another very important detail. We need to add this statement at the beginning:

import java.util.Iterator;

Now, using foreach to handle the use case of this class can get the same behavior as using an ordinary for loop array, but he does not need to know that the data representation method is an array (that is, implementation details) This is very important for the implementation of all basic data types similar to collections learned in this book and included in the Java library For example, we can switch between different representations without changing any code More importantly, from the perspective of use cases, use cases can implement iterations without knowing the implementation details of classes

The following algorithm is very important because it almost (but not yet) achieves the best performance of the implementation of any collection class data type:

  • The duration of each operation is independent of the collection size
    -Space requirements always do not exceed the set size multiplied by a constant
package basis.Knapsack queue stack;

import org.springframework.core.io.ClassPathResource;

import java.util.Iterator;
import java.util.Objects;

/**
 * Stack down (LIFO) (implementation that can dynamically adjust the size of the array)
 */
public class ResizingArrayStack<Item> implements Iterable<Item>{

    private Item[] a = (Item[]) new Object[1];//Stack element
    private int N = 0;//Number of elements

    public boolean isEmpty(){
        return N==0;
    }

    /**
     * Modify stack array size
     * @param max
     */
    public void resize(int max){
        //Move the stack to a new array of size max
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i ++){
            temp[i]=a[i];
        }
        a=temp;
    }
    public int size(){
        return N;
    }

    /**
     * Add new element
     * @param item
     */
    public void push(Item item){
        //Add element to top of stack
        if (N == a.length) resize(2*a.length);
        a[N++]=item;
    }

    /**
     * Delete element
     * @return
     */
    public Item pop(){
        Item item = a[--N];
        a[N]=null;//Avoid object drift
        if (N > 0 && N == a.length/4){
            resize(a.length/2);
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }
    private class ReverseArrayIterator implements Iterator<Item>{
        //Support last in first out iteration
        private int i = N;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public Item next() {
            return a[--i];
        }
    }

}

This generic iterative Stack Api implementation is a template for the implementation of all collection class abstract data types It saves all elements in the array and dynamically resizes the array to keep the ratio of array size to stack size less than a constant

Linked list

Linked list is a suitable choice to represent data in the abstract data type implementation of collection class This is our first example of constructing a data structure that is not supported by Java Our implementation will serve as a template for the construction code of other more complex data structures in this book

  • Linked list definition: a linked list is a recursive data structure. It is either null or a reference to a node. The node contains a generic element and a reference to another linked list

Node record

In object - oriented programming, it is not difficult to implement linked lists We first use a nested class to define the abstract data type of a node
private class Node{
Item item;
Node node;
}
We will define the Node class in the class that needs to use it and mark it as private, because it is not prepared for use cases Like any data structure, we use new Node() to trigger the (parameterless) constructor to create an object of Node type
The call result points to a reference to a Node object, and its instance variables are initialized to null
Item is a placeholder for any data type that we want to handle with the linked list (we will use Java generics to make it represent any reference type)

Construct linked list

Now, according to the definition of recursion, we only need a variable of Node type to represent a linked list, as long as its value is null or points to another Node object and the next field of the object points to another linked list To construct a linked list containing elements to,be and or

  • First create a node for each element
Node first = new Node();
Node second = new Node();
Node thirst = new Node();
  • Set the Item field of each node to the required value (Item is String)
first.item = "to";
second.item = "be";
third.item = "or"'
  • Then set the next field to construct the linked list
first.next=second;
second.next=third;

Note, third Next is still null, that is, the initial value created

When building linked list or other linked structure codes, we will use visual representation methods:

  • Representing objects with rectangles
  • Write the value of an instance variable in a rectangle
  • Use the arrow pointing to the referenced object to indicate the reference relationship

Insert element in header

If you want to insert the string not at the beginning of a given linked list whose first node is first, we now save first in oldFirst, then assign a new node to first, set its item to not, and set the next field to oldFirst The time required is independent of the length of the linked list

Delete element from header

Just point first to first Next

Insert node at end of table

We need a link to the last node of the linked list, because the link of this node must be modified and point to a new node containing a new element When the linked list has only one node, it is both the first node and the last node

Insert and delete from other locations

  • Insert node in header
  • Delete node at the end of the table
  • Insert node at end of table
    Other operations
  • Delete the specified node
  • Insert a new node before the specified node
  • How to delete the tail node of a linked list? Use a two-way linked list, where each linked list has two links pointing in different directions

ergodic

There is also a corresponding way to access the elements in the linked list: initialize the cyclic index variable x as the first node of the linked list, then access the elements associated with X through x.item, and set X to x.next to access the next node of the linked list. Repeat this process until x is null (this indicates that we have reached the end of the linked list) This process is called the traversal of the linked list. You can use the following code introduction expression to cycle through each node of the linked list, where first points to the first node of the linked list

for(Node x = first: x != null; x = x.next()){
		//Process x.item
	}

Implementation of stack

  • Save the stack as a linked list, the top of the stack is the header, and the instance variable first points to the top of the stack
  • When push() pushes in an element, we will add the element to the header
  • When pop() deletes an element, we will delete the element from the header
  • Implement the size() method, save the number of elements with the instance variable N, press the element N+1, and pop the element N-1
  • To implement the isEmpty() method, just check whether first is null or N is 0
  • This implementation uses a generic Item
  • Ignore iteration code for now

The use of linked list has achieved our optimal design goal:

  • He can handle any type of data
  • The space required is always proportional to the size of the collection
  • The time required for an operation is always independent of the size of the collection

Implementation of stack table API (linked list implementation)

package basis.Knapsack queue stack;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Push down stack
 * @param <Item>
 */
public class Stack<Item> implements Iterable<Item> {
    //Press the top of the stack (recently added element)
    private Node first;
    //Number of elements
    private int N;

    /**
     * Empty Constructor 
     */
    public Stack() {
    }

    /**
     * Add an element
     * @param item
     */
    public void push(Item item){
        //
        Node oldFirst = first;
        first = new Node();
        first.item=item;
        first.next=oldFirst;
        N++;
    }

    /**
     * Delete recently added elements
     * @return
     */
    public Item pop(){
//        if (first == null){
//            throw new NoSuchElementException();
//        }
        Item item = first.item;
        first=first.next;
        N--;
        return item;
    }

    /**
     * Whether the stack is empty
     * @return
     */
    public boolean isEmpty(){
        return first==null;
    }//Or: N==0

    /**
     * Number of elements in the stack
     * @return
     */
    public int size(){
        return N;
    }


    @Override
    public Iterator<Item> iterator() {
        return new StackIterator(first);
    }
    private class  StackIterator implements Iterator<Item>{
        private Node current;

        public StackIterator(Node first) {
            this.current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
    private class Node{
        //Nested classes that define nodes
        Item item;
        Node next;
    }

}

Implementation of queue

  • A queue is represented as a linked list from the earliest inserted element to the most recently inserted element. The instance variable first points to the beginning of the queue and the instance variable last points to the end of the queue
  • The element is listed (qnqueue()) and we add it to the end of the table (when the linked list is empty, both first and last point to the new node)
  • Element dequeue (), we need to delete the node in the header (like Stack, when the linked list is empty, we need to update the last value)
  • Implement the size() method, save the number of elements with the instance variable N, press the element N+1, and pop the element N-1
  • To implement the isEmpty() method, just check whether first is null or N is 0
  • This implementation uses a generic Item
  • Ignore iteration code for now

The use of linked list has achieved our optimal design goal:

  • He can handle any type of data
  • The space required is always proportional to the size of the collection
  • The time required for an operation is always independent of the size of the collection

Implementation of first in first out queue API

package basis.Knapsack queue stack;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * First in first out queue
 * @param <Item>
 */
public class Queue<Item> implements Iterable<Item> {
    //Link of the earliest added node
    private Node first;
    //Links to recently added nodes
    private Node last;
    //Number of elements in the queue
    private int N;

    /**
     * Add an element
     * @param item
     */
    public void enqueue(Item item){
        //Add an element to the tail
        Node oldLast = last;
        last.item=item;
        last.next=null;
        if (isEmpty()){
            first = last;
        }else{
            oldLast.next=last;
        }
        N++;
    }

    public int size(){
        return N;
    }
    /**
     * Delete header element
     */
    public Item dequeue(){
//        if (isEmpty()){
//
//            throw new NoSuchElementException();
//        }
        //Delete element from header
        Item item = first.item;
        first=first.next;
        if (isEmpty()){
            last=null;
        }
        N--;
        return item;
    }

    /**
     * Empty Constructor 
     */
    public Queue() {

    }

    /**
     * Is it empty
     * @return
     */
    public boolean isEmpty(){
        return first == null;
    }//Or N==0

    /**
     * iterator 
     * @return
     */
    @Override
    public Iterator<Item> iterator() {
        return new QueueStack(first);
    }
    private class QueueStack implements Iterator<Item>{
        private Node current;

        public QueueStack(Node first) {
            this.current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            if (!hasNext()){
                throw new NoSuchElementException();
            }
            Item item = current.item;
            current=current.next;
            return item;
        }
    }
    private class Node{
        //Nested classes that define nodes
        Item item;
        Node next;
    }
}

Linked list is an important alternative to array when storing data sets structurally

Implementation of knapsack - Implementation of iteration in collection type

  • Save the stack as a linked list, the top of the stack is the header, and the instance variable first points to the top of the stack
  • When add() pushes in an element, we will add the element to the header
  • Implement the size() method, save the number of elements with the instance variable N, press the element N+1, and pop the element N-1
  • To implement the isEmpty() method, just check whether first is null or N is 0
  • This implementation uses a generic Item
  • Ignore iteration code for now

The use of linked list has achieved our optimal design goal:

  • He can handle any type of data
  • The space required is always proportional to the size of the collection
  • The time required for an operation is always independent of the size of the collection

Implementing iterations in collection types

  • Step 1 add the following code
import java.util.Iterator
  • The second step is to add some code to the class declaration, which guarantees that the class will provide an iterator() method
implements Iterable<Item>

The iterator() method itself simply returns an object from the class that implements the Iterator interface:

public Iterator<Item> iterator(){
	return new ListIterator();
}

This code ensures that the class must implement the methods hasNext(),next() and remove() for the foreach statement of the example
To implement these methods, the nested class ListIterator() maintains an instance variable current to record the current node of the linked list The hasNext() method will detect whether current is null. The next () method will save the reference of the current element, point the current variable to the next node of the linked list, and return the saved reference

package basis.Knapsack queue stack;

import java.util.Iterator;

import java.util.NoSuchElementException;

/**
 * Defining a generic knapsack class
 */
public class Bag<Item> implements Iterable<Item> {
    //Generic element list
    private Node first;
    //Number of elements
    private int N;
    //The element pointed to by the current linked list


    /**
     * Create a control Backpack
     */
    public Bag() {

    }

    /**
     * Add an element
     * @param item
     */
    public void add(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item=item;
        first.next=oldFirst;
        N++;
    }

    /**
     * Whether the backpack is empty
     * @return
     */
    public boolean isEmpty(){

        return first==null;
    }
//    public Iterator iterator(){
//        return (Iterator) new ListIterator<Item>(first);
//    }

    /**
     * Number of elements in the backpack
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * Implement an iterator
     * @return
     */
    @Override
    public Iterator<Item> iterator() {
        return new ListIterator(first);

    }

    /**
     * Concrete iterator implementation
     *
     */
    private class ListIterator implements Iterator<Item> {
        private Node current = first;

        /**
         * Use the linked list sub elements of the backpack
         * @param first
         */
        public ListIterator(Node first) {
            this.current = first;
        }

        /**
         * Whether the linked list is empty
         * @return
         */
        public boolean hasNext() {
            return current != null;
        }
        public void remove(){
            throw new UnsupportedOperationException();
        }

        /**
         * The next element of the current linked list
         * @return
         */
        public Item next() {
//            if (!hasNext()){
//                throw new NoSuchElementException();
//            }
            Item item = current.item;
            current=current.next;
            return item;
        }
    }

    private class Node{
        //Nested classes that define nodes
        Item item;
        Node next;
    }

}

summarize

Tags: Java Algorithm data structure linked list queue

Posted by Jim on Tue, 31 May 2022 05:15:21 +0530