Week 6

• Collect linked list project

Stacks and Queues

Stacks

• Examples
  • Dish stacker
  • Compiler parser
  • Calculator
• LIFO
  • Oil inventories
  • Accounting
• Diagram
• Operations
  • Push
  • Pop
• Do algorithms
  • Define a new object Stack that has a top pointing to a type Node
  • Then do push and pop on top

public void push(Object item)

{

top = new Node(item, top);

}

public Object pop()

{

Object answer;

if (top == null) throw new EmptyStackException();       // from java.util

answer = top.getData();            // remember returns an object

top = top.next;

return answer;

}

Queues

·        Examples

o       Traffic

o       Grocery store

o       Operating system

·        FIFO

·        Draw it

·        Operations: enqueue, dequeue

·        Define a Queue object with Nodes front and rear , could also keep a counter

public void enqueue(Object item)

{

if(front == null)

{

front = new Node(item, null);

rear = front;

}

else

{

rear.next = new Node(item, null);

rear = rear.next;

}

} // end enqueue

public Object dequeue()

{

Object answer;

if(front == null) throw new NoSuchElementException(“queue underflow”);

answer = rear;

front = front.next;

return answer;

} // end dequeue

In Class:

·        Assignment: in class,

1.      convert the linked list to a doubly linked list

2.      change all algorithms to work with a doubly linked list, esp. remove

3.      write a paragraph evaluating the software they got and a paragraph on lessons they learned.  Hand copy to me and to person who gave them software.  COUNTS AS A QUIZ GRADE