CS3343/3341
 Analysis of Algorithms 
Spring 2012
  Linked List   
Used as
Stack and Queue
(Java Version)

Linked List, with Inherited Stack and Queue (Java Version)

[Please see the C Version of this part of the recitation for C code, but you should use the directions and picture below.]

The purpose of this part of the recitation is to practice pointer manipulations involving linked lists. For this purpose I'm using a program that implements a linked list is such a way that the list can be used either as a stack or a queue.

This is primarily an exercise and an example of algorithms involving pointers. It is not an example of how stacks and queues should be implemented. In the Java implementation below, one would probably want to make the data structures generic. In addition, with only the functionality below, there is not benefit to the added complexity of linked lists.

Here is a picture of the basic structure of the lists worked on below:

In the program below, we're calling the left end "first", but it could also be called "front" or "top". One can add, or remove, or dequeue, or pop, or push at this end.

The right end we're calling "last", but it could be called "rear". One can add, or enqueue at this end.

The red text below has five numbered parts. You are to supply code for these parts so that the program will work as shown. It is permissible to make further changes to this code (beyond the additions asked for), but you're not supposed to rewrite everything.

As an optional part of this exercise, you can write a "delete" function with an integer as parameter. Your function should look up the integer value and if found delete that whole link (along with the value) returning a 0. If the item is not found, return a -1.

Linked List, with Inherited Stack and Queue (Java Version)
Linked List ItselfInherited Stack and Queue along with Test Code
// ListNode.java: node for a linked list
public class ListNode {
   public int data;
   public ListNode next;

   public ListNode(int newdata) {
      // would be this way by default
      data = newdata;
      next = null;
   }
   // Can put in another constructor
   // public ListNode() { ... }
   // if you want to or need to.
}

// LinkdedList.java: basic linked list
public class LinkedList {

   private ListNode first; // front, top
   private ListNode last;  // rear

   public LinkedList() {
      last = null;
      first = null;
   }

   public void addLast(int dataItem) {
      // or add to rear, i.e. enqueue
      // 1. Supply code for this function.
      // Add a new link at "last" end
      //   holding "dataItem".
      // May need to treat empty list
      //   as a separate case.
   }

   public void addFirst(int dataItem) {
      // or add to front, i.e. dequeue, or push
      // 2. Supply code for this function.
      // Add a new link at "first" end
      //   holding "dataItem".
   }

   public int removeFirst() {
      // or pop
      // 3. Supply code for this function.
      // Must remove link at "first" end,
      //   and return data value stored there.
   }

   public boolean empty() {
      return first == null;
   }

   public void printList() {
      // first to last, or front to rear
      // 4. Supply code to print the list
      //   from first to last.
   }

   public void printReverse() {
      printReverse0(first);
      System.out.println();
   }
   public void printReverse0(ListNode temp) {
      // last to first, or rear to front
      // 5. Supply code for a RECURSIVE function
      //   that prints from last to first.
   }
}

// Stack.java: inherited from linked list
public class Stack extends LinkedList{

   public void push(int dataItem) {
      addFirst(dataItem);
   }

   public int pop() {
      return removeFirst();
   }
   // Could add main function here
   //   for testing.  (Not required.)
}

// Queue.java: inherited from linked list
public class Queue extends LinkedList{

   public void enqueue(int dataItem) {
      addLast(dataItem);
   }

   public int dequeue() {
      return removeFirst();
   }
   // Could add main function here
   //   for testing.  (Not required.)
}

// ListTest.java: test stack and queue
public class ListTest{

   public static void main(String[] args) {
      int[] a = {2, 3, 5, 7, 11, 13};

      Queue q = new Queue();
      for (int i = 0; i < a.length; i++)
         q.enqueue(a[i]);
      System.out.println("Queue:");
      q.printList();
      q.printReverse();
      int t = q.dequeue();
      System.out.print(t + " ");
      t = q.dequeue();
      System.out.print(t + "\n");

      Stack s = new Stack();
      for (int i = 0; i < a.length; i++)
         s.push(a[i]);
      System.out.println("Stack:");
      s.printList();
      s.printReverse();
      t = s.pop();
      System.out.print(t + " ");
      t = s.pop();
      System.out.print(t + "\n");
   }
}
Common Output
Queue:
2 3 5 7 11 13 
13 11 7 5 3 2  
2 3
Stack:
13 11 7 5 3 2 
2 3 5 7 11 13 
13 11

Revision date: 2011-12-17. (Please use ISO 8601, the International Standard Date and Time Notation.)