Question

In Java or C++, implement a stack and a queue using a linkedlist data structure.  You may not use any standard Java or C++ libraries.

Assume your data structure only allows Strings. Implement the following operations for the data structure:

Queue: enqueue, dequeue, create, isEmpty (10 points)

Stack: push, pop, create, isEmpty (10 points)

Here is a link to get started on transferring from Java to C++ http://www.horstmann.com/ccj2/ccjapp3.html (Links to an external site.)

Upload a zip file with one implementation for your Stack and one for your Queue, along with any classes required to implement your linkedlist (i.e. nodes for linkedlist). In each file include a test method which shows how you've tested each operation.

Answer 1

Here is the completed code for this problem in Java. Two files are attached – LinkedQueue.java that represents linked list representation of a Queue and LinkedStack.java that represents linked list representation of a Stack, with main methods in both files for testing. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// LinkedQueue.java

public class LinkedQueue {

      //references to front and rear node

      private Node front, rear;

      // private inner class representing a Node in linked list representation of

      // the queue

      private class Node {

            private String item;

            private Node next;

            // constructor initializing item and next node

            public Node(String item, Node next) {

                  this.item = item;

                  this.next = next;

            }

      }

      // constructor, creates an empty queue

      public LinkedQueue() {

            create();

      }

      // method to create/reset an empty queue

      public void create() {

            front = null;

            rear = null;

      }

      // returns true if queue is empty

      public boolean isEmpty() {

            return (front == null);

      }

      // adds an element to the rear

      public void enqueue(String item) {

            // creating a new node

            Node newNode = new Node(item, null);

            // if queue is currently empty, adding as both front and rear

            if (isEmpty()) {

                  front = newNode;

                  rear = newNode;

            } else {

                  // appending to rear and updating rear

                  rear.next = newNode;

                  rear = newNode;

            }

      }

      // removes and returns the front value, will return null if queue is empty

      public String dequeue() {

            if (front != null) {

                  // getting item on front

                  String item = front.item;

                  // updating front

                  front = front.next;

                  // if front became null, setting rear to null

                  if (front == null) {

                        rear = null;

                  }

                  // returning removed value

                  return item;

            }

            return null;// empty

      }

     

      //main method for testing linked queue

      public static void main(String[] args) {

            // creating a queue, adding some strings

            LinkedQueue que = new LinkedQueue();

            que.enqueue("hello");

            que.enqueue("world");

            que.enqueue("how");

            que.enqueue("are");

            que.enqueue("you");

            // looping until que is empty

            while (!que.isEmpty()) {

                  // dequeing and displaying front element

                  System.out.println(que.dequeue());

            }

      }

}

// LinkedStack.java

public class LinkedStack {

      private Node top;

      // private inner class representing a Node in linked list representation of

      // the stack

      private class Node {

            private String item;

            private Node next;

            // constructor initializing item and next node

            public Node(String item, Node next) {

                  this.item = item;

                  this.next = next;

            }

      }

      // constructor, creates an empty stack

      public LinkedStack() {

            create();

      }

      // method to create/reset an empty stack

      public void create() {

            top = null;

      }

      // returns true if stack is empty

      public boolean isEmpty() {

            return (top == null);

      }

      // pushes an element to the top

      public void push(String item) {

            // adding a new node before top and updating top

            top = new Node(item, top);

      }

      // removes and returns the top value, will return null if stack is empty

      public String pop() {

            if (top != null) {

                  // getting item on top

                  String item = top.item;

                  // updating top

                  top = top.next;

                  // returning removed value

                  return item;

            }

            return null;// empty

      }

     

      //main method for testing linked stack

      public static void main(String[] args) {

            // creating a stack, pushing some strings

            LinkedStack stack = new LinkedStack();

            stack.push("hello");

            stack.push("world");

            stack.push("how");

            stack.push("are");

            stack.push("you");

            // looping until stack is empty

            while (!stack.isEmpty()) {

                  // popping and displaying top element

                  System.out.println(stack.pop());

            }

      }

}

/*OUTPUT of LinkedQueue program*/

hello

world

how

are

you

/*OUTPUT of LinkedStack program*/

you

are

how

world

hello