Classwork:

Stack: linked-list implementation

A Queue ADT
A queue is a linear collection whose elements are added on one end and removed from the other. Therefore, we say that queue elements are processed in a first in, first out (FIFO) manner. Elements are removed from a queue in the same order in which they are placed on the queue.

public interface QueueADT
{
// Adds one element to the rear of the queue
public void enqueue (T element);

// Removes and returns the element at the front of the queue
public T dequeue();

// Returns without removing the element at the front of the queue
public T first();

// Returns true if the queue contains no elements
public boolean isEmpty();

// Returns the number of elements in the queue
public int size();

// Returns a string representation of the queue
public String toString();
}

Assignment: Using the QueueADT interface, implement the Queue ADT according to the API below:

■ Queue elements are processed in a FIFO manner—the first element in is the first element out.
■ A queue is a convenient collection for storing a repeating code key.
■ Simulations are often implemented using queues to represent waiting lines.
■ A linked implementation of a queue is facilitated by references to the first and last elements of the linked list.
■ The enqueue and dequeue operations work on opposite ends of the collec- tion.
■ Because queue operations modify both ends of the collection, fixing one end at index 0 requires that elements be shifted.
■ The shifting of elements in a noncircular array implementation creates an O(n) complexity.
■ Treating arrays as circular eliminates the need to shift elements in an array queue implementation.

Assignments:
1. Create a system using a stack and a queue to test whether a given string is a palindrome (i.e., the characters read the same forward or backward).

2. Create a system to simulate vehicles at an intersection. Assume that there is one lane going in each of four directions, with stoplights facing each direction. Vary the arrival average of vehicles in each direction and the frequency of the light changes to view the “behavior” of the intersection.

Answer question about videos 2.3 and 2.4 from Classroom Salon.

Coming reading assignments:

Data Structures: Stacks and Queues

Stacks. A stack is a collection that is based on the last-in-first-out (LIFO) policy. By tradition, we name the stack insert method push() and the stack remove operation pop(). We also include a method to test whether the stack is empty, as indicated in the following API:

Video Lectures :
Stacks and Queues
Clients

Assignment:
Implement the ArrayStackOfIntegers ADT for Integers using arrays.

Other members that you need to implement:

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

public class ArrayStackOfIntegers implements Iterable {
    private Integers[] items;  // holds the items
    private int n;             // number of items in stack
    public ArrayStackOfIntegers(int capacity) {
        items = (Integer[]) new Object[capacity];
    }

    public boolean isEmpty() {
        ----
    }

    public boolean isFull() {
        ----
    }

    public void push(Integer item) {
        ----
    }

    public Integer pop() {
        
    }

    public Iterator iterator() {
        return new ReverseArrayIterator();
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ReverseArrayIterator implements Iterator {

    ----
    public void remove() 
    {}
    }
}

An example of Iterable

The files in this site are cleaned up a bit here.

Use the ArrayStackOfIntegers ADT  to work on these assignments:
ArrayStackOfIntegers ADT – Calculator
Design and implement a client to calculate the following postfix expression: 8 4 -3 * 1 5 + / *

 
ArrayStackOfIntegers ADT – Enhanced Calculator
 
StackCalculatorEnhanced

 

Classwork:
Lesson Videos – questions are posted

Homework
Undirected Graphs – Ex 4.1.1-4.1.3

Classwork:
1. At classroomSalon.com:
Video 11.4 has one question.
Please type “done” in edmodo.com when you answer it.

Homework:
At edmodo.com:
Summary and comparisons.

NOTE: Classroomsalom.com has gone mobil now!!!!