Question

Describe two approaches to implementing stacks or queues. Some advantages and disadvantages of one over the other? What it the array position of the root of a binary tree? If m is the position of the parent of a complete binary tree what is the position of the left son? State the binary search tree condition. Show how the nodes of a binary search tree Implemented by a linked list look if the following nodes are inserted sequentially: 43, 17, 52, 33, 23, 46, 55, 22 State the heap condition. Explain how a heap is used to implement heap sort. Show how the nodes of a heap implemented by an array look after the following nodes are inserted: 43, 17, 52, 33, 23, 46, 55, 22 Explain how you would implement code to remove a node from a heap. Give an example of when a hashing algorithm may be needed.

Answer 1

sol:

Both stacks and queues are like lists (ordered collections of items), but with more restricted operations. They can both be implemented either using an array or using a linked list to hold the actual items.

Two approaches to implement stack :

Stacks

The conceptual picture of a stack is something like this:

  

V I X/

Think of a stack of newspapers, or trays in a cafeteria. The only item that can be taken out (or even seen) is the most recently added item; a stack is a Last-In-First-Out (LIFO) data structure.

Here are the stack operations:

OPERATION	DESCRIPTION
Stack()	(constructor) create an empty stack
boolean empty()	return true iff the stack is empty
int size()	return the number of items in the stack
void push(Object ob)	add ob to the top of the stack
Object pop()	remove and return the item from the top of the stack (error if the stack is empty)
Object peek()	return the item that is on the top of the stack, but do not remove it (error if the stack is empty)

Implementing Stacks

The stack ADT is very similar to the list ADT; therefore, their implementations are also quite similar.

Array Implementation

Below is the definition of the Stack class, using an array to store the items in the stack; note that we include a static final variable INITSIZE, to be used by the Stack constructor as the initial size of the array (the same thing was done for the List class).

public class Stack {

// *** fields ***

    private static final int INITSIZE = 10; // initial array size

    private Object[] items; // the items in the stack

    private int numItems;   // the number of items in the stack

//*** methods ***

// constructor

    public Stack() { ... }     

// add items

    public void push(Object ob) { ... }

// remove items

    public Object pop() throws EmptyStackException { ... }

// other methods

    public Object peek() throws EmptyStackException { ... }

    public int size() { ... }     

    public boolean empty() { ... }

}

The push method is like the version of the List add method that adds an object to the end of the list (because items are always pushed onto the top of the stack). Note that it is up to us as the designers of the Stack class to decide which end of the array corresponds to the top of the stack. We could choose always to add items at the beginning of the array, or always to add items at the end of the array. However, it is clearly not a good idea to add items at the beginning of the array since that requires moving all existing items; i.e., that choice would make push be O(N) (where N is the number of items in the stack). If we add items at the end of the array, then push is O(1), except when the array is full.

Here are before and after pictures, illustrating the effects of a call to push:

BEFORE CALLING push ilems: numlHems:3 AFTERCALLING pushtyy) ilems numlHems: 4

And here's the code for the push method:

public void push(Object ob) {

    if (items.length == numItems) expandArray();

    items[numItems] = ob;

  numItems++;

}

The pop method needs to remove the top-of-stack item, and return it, as illustrated below.

BEFORE CALLING pop ilems: numlHems: 3 AFTER CALLING pop (lhe vakue bbb is relurmed) ilems

Note that, in the picture, the value "bbb" is still in items[2]; however, that value is no longer in the stack because numItems is 2 (which means that items[1] is the last item in the stack).

Linked-list Implementation

To implement a stack using a linked list, we must first define the Listnode class. The Listnode definition is the same one we used for the linked-list implementation of the List class.

The signatures of the methods of the Stack class are independent of whether the stack is implemented using an array or using a linked list; only the type of the items field needs to change:

private Listnode items; // pointer to the linked list of items in the stack

As discussed above, an important property of stacks is that items are only pushed and popped at one end (the top of the stack). If we implement a stack using a linked list, we can choose which end of the list corresponds to the top of the stack. It is easiest and most efficient to add and remove items at the front of a linked list, therefore, we will choose the front of the list as the top of the stack (i.e., the items field will be a pointer to the node that contains the top-of-stack item). Below is a picture of a stack represented using a linked list; in this case, items have been pushed in alphabetical order, so "cc" is at the top of the stack:

cC 8a ilems num Hems: 3

Notice that, in the picture, the top of stack is to the left (at the front of the list), while for the array implementation, the top of stack was to the right (at the end of the array).

Let's consider how to write the pop method. It will need to perform the following steps:

1.     Check whether the stack is empty; if so, throw an EmptyStackException.

2.     Remove the first node from the list by setting items = items.next.

3.     Decrement numItems.

4.     Return the value that was in the first node in the list.

Note that by the time we get to the last step (returning the top-of-stack value), the first node has already been removed from the list, so we need to save its value in order to return it (we'll call that step 2(a)). Here's the code, and an illustration of what happens when pop is called for a stack containing "cc", "bb", "aa" (with "cc" at the top).

public Object pop() throws EmptyStackException {

    if (empty()) throw new EmptyStackException(); // step 1

    Object tmp = items.getData(); // step 2(a)

    items = items.getNext();       // step 2(b)

    numItems--;                    // step 3

    return tmp;                    // step 4

}

Inilial Slack: (step 1 lest is false) ilems cC num Hems:3 afler slep 2ta):: numHems:3 imp: cc afler slep 4b):ilems: cC 2a num Hems:3 imp: cc afler slep 3 ilems: numllems:2 imp cc

Before push(dd) lems cC 2a numlHerms:3 llerns LdE -L"E.DE.LN 2a Afler push(dd): numlHems: 4

The steps that need to be performed are:

1.     Create a new node whose data field contains the object to be pushed and whose next field contains a pointer to the first node in the list (or null if the list is empty). Note that the value for the next field of the new node is the value in the Stack's items field.

2.     Change items to point to the new node.

3.     Increment numItems.

COMPARISON OF ARRAY AND LINKED-LIST IMPLEMENTATIONS

The advantages and disadvantages of the two implementations are essentially the same as the advantages and disadvantages in the case of the List class:

• In the linked-list implementation, one pointer must be stored for every item in the stack/queue, while the array stores only the items themselves.
• On the other hand, the space used for a linked list is always proportional to the number of items in the list. This is not necessarily true for the array implementation as described: if a lot of items are added to a stack/queue and then removed, the size of the array can be arbitrarily greater than the number of items in the stack/queue. However, we could fix this problem by modifying the pop/dequeue operations to shrink the array when it becomes too empty.
• For the array implementation, the worst-case times for the push and enqueue methods are O(N), for a stack/queue with N items. This is because when the arary is full, a new array must be allocated and the values must be copied. For the linked-list implementation, push and enqueue are always O(1).