Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Complete the implementation of the Stack kernel represented as a singly-linked list of…

  1. User

    Complete the implementation of the Stack kernel represented as a singly-linked list of Nodes in the skeleton provided, Stack2. You need to write bodies for the private method createNewRep and for the kernel methods push, pop, and length.

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

    import components.stack.Stack; import components.stack.StackSecondary;

    /**

    • {@code Stack} represented as a singly linked list, done "bare-handed", with

    • implementations of primary methods.

    • Execution-time performance of all methods implemented in this class is O(1).

    • @param

    •        type of Stack entries
      
    • @convention

    • $this.length >= 0 and

    • if $this.length == 0 then

    • [$this.top is null]

    • else

    • [$this.top is not null] and

    • [$this.top points to the first node of a singly linked list

    • containing $this.length nodes] and

    • [next in the last node of that list is null]

    • @correspondence this = [data in this.lengthnodesstartingatthis.length nodes starting at this.top] */ public class Stack2 extends StackSecondary {

      /*

      • Private members -------------------------------------------------------- */

      /**

      • Node class for singly linked list nodes. */ private final class Node {

        /**

        • Data in node. */ private T data;

        /**

        • Next node in singly linked list, or null. */ private Node next;

      }

      /**

      • Top node of singly linked list. */ private Node top;

      /**

      • Number of nodes in singly linked list, i.e., length = |this|. */ private int length;

      /**

      • Creator of initial representation. */ private void createNewRep() {

        // TODO - fill in body

      }

      /*

      • Constructors ----------------------------------------------------------- */

      /**

      • No-argument constructor. */ public Stack2() { this.createNewRep(); }

      /*

      • Standard methods removed to reduce clutter... */

      /*

      • Kernel methods --------------------------------------------------------- */

      @Override public final void push(T x) { assert x != null : "Violation of: x is not null";

       // TODO - fill in body
      

      }

      @Override public final T pop() { assert this.length() > 0 : "Violation of: this /= <>";

       // TODO - fill in body
      

      }

      @Override public final int length() {

       // TODO - fill in body
      

      }

      /*

      • Iterator code removed to reduce clutter... */

    }

  2. Assistant

    To complete the implementation of the Stack2 class, you need to write bodies for the private method createNewRep and for the kernel methods push, pop, and length. Here's the complete implementation:

    public class Stack2<T> extends StackSecondary<T> {
    
        /*
         * Private members --------------------------------------------------------
         */
    
        /**
         * Node class for singly linked list nodes.
         */
        private final class Node {
    
            /**
             * Data in node.
             */
            private T data;
    
            /**
             * Next node in singly linked list, or null.
             */
            private Node next;
    
        }
    
        /**
         * Top node of singly linked list.
         */
        private Node top;
    
        /**
         * Number of nodes in singly linked list, i.e., length = |this|.
         */
        private int length;
    
        /**
         * Creator of initial representation.
         */
        private void createNewRep() {
            this.top = null;
            this.length = 0;
        }
    
        /*
         * Constructors -----------------------------------------------------------
         */
    
        /**
         * No-argument constructor.
         */
        public Stack2() {
            this.createNewRep();
        }
    
        /*
         * Standard methods removed to reduce clutter...
         */
    
        /*
         * Kernel methods ---------------------------------------------------------
         */
    
        @Override
        public final void push(T x) {
            assert x != null : "Violation of: x is not null";
            Node newNode = new Node();
            newNode.data = x;
            newNode.next = this.top;
            this.top = newNode;
            this.length++;
        }
    
        @Override
        public final T pop() {
            assert this.length() > 0 : "Violation of: this /= <>";
            T poppedData = this.top.data;
            this.top = this.top.next;
            this.length--;
            return poppedData;
        }
    
        @Override
        public final int length() {
            return this.length;
        }
    
        /*
         * Iterator code removed to reduce clutter...
         */
    
    }
    

    In the createNewRep method, we simply set the top reference to null and the length to 0 to create an empty stack representation.

    In the push method, we create a new node, set its data to the given element x, make it point to the current top node, and update the top reference to the new node. We also increment the length by 1.

    In the pop method, we first check if the stack is not empty by ensuring the length is greater than 0. We then get the data from the top node, move the top reference to the next node, and decrement the length by 1. Finally, we return the popped data.

    In the length method, we simply return the current length value.