# Class 43: Implementing Linear Structures

Held Tuesday, November 14, 2000

Summary

Today we consider techniques for implementing the various linear structures.

Notes

• Are there any questions on hw 4?
• My aunt died last night, so it looks like I'll be gone some days this week and/or next.
• Any comments on the proposed exam times?

Overview

## Basic Implementation Techniques

• For both stacks and queues, we can use similar implementation techniques to those we used for lists:
• Arrays
• Nodes
• For array-based stacks, we add to the end and remove from the end.
• For array-based queues, we add to the end and remove from the front.
• As in the case of "shifty lists", we need to keep track of the position of the front and wrap around.
• For node-based stacks, we add to the front and remove from the front. (And only keep track of the front.)
• For node-based queues, we add to the end and remove from the front. (And keep track of both front and end.)
• We can also use any implementation of lists to implement stacks and queues. For example, here's an approximate implementation of queues:
```public class ListBasedQueue
implements Queue
{
// +--------+--------------------------------------------------
// | Fields |
// +--------+

List implementation;
ListIterator helper;

// +--------------+--------------------------------------------
// | Constructors |
// +--------------+

public ListBasedQueue() {
this.implementation = new WhateverKindOfListYouWant();
this.helper = implementation.getIterator();
} // ListBasedQueue()

// +---------+-------------------------------------------------
// | Methods |
// +---------+

public Object get() {
return this.implementation.deleteFirst();
}

public Object peek() {
this.helper.toFront();
return this.helper.getCurrent();
}

public void put(Object val) {
}

public boolean isEmpty() {
return (this.implementation.length() == 0);
}

public boolean isFull() {
return this.implementation.isFull();
}
} // public class ListBasedQueue
```

## Priority Queues

• Simplest version: use an array or doubly-linked list and search using our normal "largest" technique.
• Here's the array-based version.
```public class ArrayBasedPriorityQueue
implements PriorityQueue
{
// +--------+--------------------------------------------------
// | Fields |
// +--------+

/**
* All the values in the priority queue.  There may be gaps
* in this array, in which case null represents "no element
* here".
*/
Object[] values;

/**
* The number of values in the priority queue.
*/
int size;

/**
* The comparator used to find the highest-priority (largest)
* value in the pqueue.
*/
Comparator order;

// +--------------+--------------------------------------------
// | Constructors |
// +--------------+

/**
* Create a new priority queue that orders values with a
* particular comparator and that holds up to capacity
* values.
*/
public ArrayBasedPriorityQueue(Comparator c; int capacity) {
this.order = c;
this.size = 0;
this.values = new Object[capacity];
// Note that no values are in the queue.
// The following is probably done automatically, but we do
// it ourselves just to be sure.
for (int i = 0; i < capacity; i++) {
this.values[i] = null;
}
} // ArrayBasedPriorityQueue(Comparator, int)

// +---------+-------------------------------------------------
// | Methods |
// +---------+

/** Is it full? */
public boolean isFull() {
return this.size = this.values.length;
}

public void put(Object val) {
for (int i = 0; i < this.values.length; i++) {
// Is the current position available?
if (this.values[i] == null) {
// If so, fill it in.
this.values[i] = val;
// And stop
return;
} // if
} // for
} // put

/** Get something. */
public void get() {
int maxindex = this.findMax();
Object returnMe = this.values[maxindex];
this.values[maxindex] = 0;
return returnMe;
}

// +---------+-------------------------------------------------
// | Helpers |
// +---------+

/**
* Find the index of the maximum value.
*/
public int findMax() {
int guess = -1;
// Step through all the locations
for (int i = 0; i < this.values.length; i++) {
if (this.values[i] != null) {
if (guess == -1) {
guess = i;
}
else if (order.compare(this.values[i], this.values[guess]) > 0) {
guess = i;
} // if values[i] > this.values[guess]
} // if the current value exists
} // for each location
return guess;
} // findMax()
} // ArrayBasedPriorityQueue
```

## Heaps

• A different technique, using divide and conquer for data structrues.

## History

Wednesday, 23 August 2000

• Created as a blank outline.

Thursday, 24 August 2000

• Slight reorganization to page design.

Tuesday, 14 November 2000

• Filled in the details.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.