Abstract Data Types

Generic structures

Implementation separate from structure


Push takes an element as a parameter:


Pop returns an element

E pop()

LIFO – Last In First Out


  1. A letter means push and an asterisk means pop in the sequence

    E A S * Y * Q U E * * * S T * * * I O * N * * *.`

    Give the sequence of values returned by the pop operations.

  2. Give a way to insert asterisks in the sequence E A S Y so that the sequence of values returned by the pop operations is

    a. E A S Y b. Y S A E c. A S Y E d. A Y E S

    or, in each instance, prove that no such sequence exists.

  3. Given two sequences, give an algorithm for determining whether or not asterisks can be added to make the first produce the second.


interface intStack { 
	intStack(int)  //param optional: size of stack
	boolean isEmpty()
	void push(int)
	int pop() 
	int peek() //sometimes


Functions: Extensions


Put takes an element as a parameter


get returns an element


FIFO – First In First Out


  1. A letter means put and an asterisk means get in the sequence

    S I L* *L Y * R ** A B * * * B I T * * * .

    Give the sequence of values returned by the get operations when this sequence of operations is performed on an initially empty FIFO queue.

How would that problem work on a queue that did not allow duplicate letters?


interface intQueue 
	intQueue(int maxN) 
  	boolean empty() 
	void put(int item) 
	int get()


  • an array:

class intQueue 
	private int[] q; 
	private int N, head, tail; 
	intQueue(int maxN) { 
		q = new int[maxN + 1]; 
		N = maxN + 1; 
		head = N; 
		tail = 0; } 
	boolean empty() { 
		return (head % N == tail); } 
	void put(int item) { 
		q[tail++] = item; 
		tail = tail % N; } 
	int get() { 
		head = head % N; 
		return q[head++]; } 
  • Nodes? (next week :muscle:)
  • Stacks?
    • Power question: How many stacks do you need to implement a queue? What is the net efficiency of such an implementation?
  • Java Queue Reference

Functions: Queue Flavors (pick one)

  • priority queue
  • deque
  • circular queue
  • sorted queue


A list is like a dynamically sized array

we usually define add(E), E get(index), set(index, E) and remove(index)


interface List {
    E get(int index);
    E set(int index, E element);
    boolean add(E element); 
    void add(int index, E element);
    E remove(int index);


Functions: Polymorphic


a set is a group of items with no order


interface Set {
	boolean contains(E)


Functions: Selection and Statistics

Collections Assignment

Complete a function for each datastructure: stack, queue, list, set.

H period I period C period


5 pts for each correct function (individual) 1 pt for each completed datastructure (group) 1 pt to be determined 70 pts for free

due 10/28 extended to 10/30, resubmissions due 11/13.