Stacks and Queues

Stacks and Queues

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.

Stacks

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)

Queues

The conceptual picture of a queue is something like this:

                 ------------------
values in ---->  items in the queue   ----> values out
                 ------------------
                 ^                ^
                 |                |
     this is the rear of          this is the front of
     the queue                    the queue

Think of people standing in line. A queue is a First-In-First-Out (FIFO) data structure. Items can only be added at the rear of the queue, and the only item that can be removed is the one at the front of the queue.

Here are the queue operations:

OPERATION

DESCRIPTION

Queue() (constructor) create an empty queue
boolean empty() return true iff the queue is empty
int size() return the number of items in the queue
void enqueue(Object ob) add ob to the rear of the queue
Object dequeue() remove and return the item from the front of the queue (error if the queue is empty)

 

  • Stacks are data structures which maintain the order of last-in, first-out
  • Queues are data structures which maintain the order of first-in, first-out

Queues might seem fairer, which is why lines at stores are organized as queues instead of stacks, but both have important applications in programs as a data structure.

More Info

Queues and stacks are containers whose main methods for access are push() and pop(). JGL includes three containers with this property.

  • Stack is a first-in, last-out data structure that pops elements in the opposite order than they were pushed. By default, a Stack uses an Array for its internal storage, although this can easily be changed.
  • Queue is a first-in, first-out data structure that pops elements in the same order than they were pushed. By default, a Queue uses an SList for its internal storage, although this can easily be changed.
  • PriorityQueue is a form of queue that keeps its elements in a quasi-sorted state and pops them based on their sorted order rather than in the order that they were pushed. A PriorityQueue uses an Array for its underlying storage.

 

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() { ... }  
}

TEST YOURSELF #1

Write the Stack constructor.

[See below for answers]

————————————————————————————-

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 pushis O(1), except when the array is full.

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

 q1

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.

q2

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).

TEST YOURSELF #2

Complete the pop method, using the following header

public Object pop() throws EmptyStackException {
}

[See below for answers]

———————————————————————————–

The peek method is very similar to the pop method, except that it only returns the top-of-stack value without changing the stack. The size method simply returns the value of numItems, and the empty method returns true if numItems is zero.

TEST YOURSELF #3

Fill in the following table, using Big-O notation to give the worst and average-case times for each of the stack methods for a stack of size N.

OPERATION

WORST-CASE TIME

AVERAGE-CASE TIME

constructor
empty
size
push
pop
peek

————————————————————————————-

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:

 q3

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
}

 q4

q5

Now let’s consider the push method. Here are before and after pictures, illustrating the effect of a call to push when the stack is implemented using a linked list:

q6

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.

TEST YOURSELF #4

Complete the push method, using the following header.

public void push(Object ob) {
}

[See below for answers]

The remaining methods (the constructor, peeksize, and empty) are quite straightforward. You should be able to implement them without any major problems.

————————————————————————————

TEST YOURSELF #5

Fill in the following table, using Big-O notation to give the worst-case times for each of the stack methods for a stack of size N, assuming a linked-list implementation. Look back at the table you filled in for the array implementation. How do the times compare? What are the advantages and disadvantages of using an array vs using a linked list to implement the Stack class?

OPERATION

WORST-CASE TIME

constructor
empty
size
push
pop
peek

[See below for answers]

————————————————————————————-

FIFO Queues

  • Queues are more difficult to implement than stacks, because action happens at both ends.
  • The easiest implementation uses an array, adds elements at one end, and moves all elements when something is taken off the queue.
  • It is very wasteful moving all the elements on each DEQUEUE. Can we do better?
  • More Efficient Queues
    • Suppose that we maintaining pointers to the first (head) and last (tail) elements in the array/queue?
    • Note that there is no reason to explicitly clear previously unused cells.
    • Now both ENQUEUE and DEQUEUE are fast, but they are wasteful of space. We need a array bigger than the total number of ENQUEUEs, instead of the maximum number of items stored at a particular time.

Circular Queues

  • Circular queues let us reuse empty space!
  • Note that the pointer to the front of the list is now behind the back pointer!
  • When the queue is full, the two pointers point to neighboring elements.
  • There are lots of possible ways to adjust the pointers for circular queues. All are tricky!
  • How do you distinguish full from empty queues, since their pointer positions might be identical? The easiest way to distinguish full from empty is with a counter of how many elements are in the queue.

Implementing Queues

The main difference between a stack and a queue is that a stack is only accessed from the top, while a queue is accessed from both ends (from the rear for adding items, and from the front for removing items). This makes both the array and the linked-list implementation of a queue more complicated than the corresponding stack implementations.

Array Implementation

Let’s first consider a Queue implementation that is very similar to our (array-based) List implementation. Here’s the class definition:

public class Queue {
  // *** fields ***
    private static final int INITSIZE = 10;  // initial array size
    private Object[] items; // the items in the queue
    private int numItems;   // the number of items in the queue

  //*** methods ***

  // constructor
    public Queue() { ... }      

  // add items
    public void enqueue(Object ob) { ... }  

  // remove items
    public Object dequeue() throws EmptyQueueException { ... }

  // other methods
    public int size() { ... }      
    public boolean empty() { ... }  
}

We could implement enqueue by adding the new item at the end of the array and implement dequeue by saving the first item in the array, moving all other items one place to the left, and returning the saved value. The problem with this approach is that, although the enqueue operation is efficient, the dequeue operation is not — it requires time proportional to the number of items in the queue.

To make both enqueue and dequeue efficient, we need the following insight: There is no reason to force the front of the queue always to be in items[0], we can let it “move up” as items are dequeued. To do this, we need to keep track of the indexes of the items at the front and rear of the queue (so we need to add two new fields to the queue class, frontIndex and rearIndex, both of type int). To illustrate this idea, here is a picture of a queue after some enqueue and dequeue operations have been performed:

 q7

Now think about what should happen to this queue if we enqueue two more items: “dd” and “ee”. Clearly “dd” should be stored in items[6]. Then what? We could increase the size of the array and put “ee” in items[7], but that would lead to wasted space — we would never reuse items[0], items[1], or items[2]. In general, the items in the queue would keep “sliding” to the right in the array, causing more and more wasted space at the beginning of the array. A better approach is to let the rear index “wrap around” (in this case, from 6 to 0) as long as there is empty space in the front of the array. Similarly, if after enqueuing “dd” and “ee” we dequeue four items (so that only “ee” is left in the queue), the front index will have to wrap around from 6 to 0. Here’s a picture of what happens when we enqueue “dd” and “ee”:

 q8

q9

Conceptually, the array is a circular array. It may be easier to visualize it as a circle. For example, the array for the final queue shown above could be thought of as:

 q10

We still need to think about what should happen if the array is full; we’ll consider that case in a minute. Here’s the code for the enqueue method, with the “full array” case still to be filled in:

public void enqueue(Object ob) {
  // check for full array and expand if necessary
    if (items.length == numItems) {
       // code missing here
    }

  // use auxiliary method to increment rear index with wraparound
    rearIndex = incrementIndex(rearIndex);

  // insert new item at rear of queue
    items[rearIndex] = ob;
    numItems++;
}

private int incrementIndex(int index) {
    if (index == items.length-1) return 0;
    else return index + 1;
}

Note that instead of using incrementIndex we could use the mod operator, and write: rearIndex = (rearIndex + 1) % items.length. However, the mod operator is quite slow, and it is easy to get that expression wrong, so we will use the auxiliary method (with a check for the “wrap-around” case) instead.

To see why we can’t simply use expandArray when the array is full, consider the picture shown below.

 q11

After calling expandArray, the last item in the queue is still right before the first item — there is still no place to put the new item (and there is a big gap in the middle of the queue, from items[7] to items[13]). The problem is that expandArray copies the values in the old array into the same positions in the new array. This does not work for the queue implementation; we need to move the “wrapped-around” values to come after the non-wrapped-around values in the new array.

The steps that need to be carried out when the array is full are:

  1. Allocate a new array of twice the size.
  2. Copy the values in the range items[frontIndex] to items[items.length-1] into the new array (starting at position frontIndex in the new array).
  3. Copy the values in the range items[0] to items[rearIndex] into the new array (starting at position items.length in the new array). Note: if the front of the queue was in items[0], then all of the values were copied by step 2, so this step is not needed.
  4. Set items to point to the new array.
  5. Fix the value of rearIndex.

Here’s an illustration:

q12q13

And here’s the final code for enqueue:

publc void enqueue(Object ob) {
  // check for full array and expand if necessary
    if (items.length == numItems) {
        Object[] tmp = new Object[items.length*2];
        System.arraycopy(items, frontIndex, tmp, frontIndex,
                   items.length-frontIndex);
  if (frontIndex != 0) {
      System.arraycopy(items, 0, tmp, items.length, frontIndex);
  }
        items = tmp;
  rearIndex = frontIndex + numItems - 1;
    }

  // use auxiliary method to increment rear index with wraparound
    rearIndex = incrementIndex(rearIndex);  // insert new item at rear of queue
    items[rearIndex] = ob;
    numItems++;
}

The dequeue method will also use method incrementIndex to add one to frontIndex (with wrap-around) before returning the value that was at the front of the queue.

The other queue methods (empty and size) are the same as those methods for the Stack class — they just use the value of the numItems field.

Linked-list Implementation

The first decision in planning the linked-list implementation of the Queue class is which end of the list will correspond to the front of the queue. Recall that items need to be added to the rear of the queue, and removed from the front of the queue. Therefore, we should make our choice based on whether it is easier to add/remove a node from the front/end of a linked list.

If we keep pointers to both the first and last nodes of the list, we can add a node at either end in constant time. However, while we can remove the first node in the list in constant time, removing the last node requires first locating the previous node, which takes time proportional to the length of the list. Therefore, we should choose to make the end of the list be the rear of the queue, and the front of the list be the front of the queue.

The class definition is the same as for the array implementation, except for the fields:

  // *** fields ***
    private Listnode qFront; // pointer to the front of the queue
                             // (the first node in the list)
    private Listnode qRear;  // pointer to the rear of the queue
                             // (the last node in the list)
    private int numItems;    // the number of items in the queue

Here’s a picture of a Queue with three items, aa, bb, cc, with aa at the front of the queue:

 q14

You should be able to write all of the queue methods, using the code you wrote for the linked-list implementation of the List class as a guide.

TEST YOURSELF #6

Complete method reverseQ, whose header is given below. Method reverseQ should use a Stack to reverse the order of the items in its Queue parameter.

public static void reverseQ(Queue q) {
// precondition: q contains x1 x2 ... xN (with x1 at the front)
// postcondition: q contains xN ... x2 X1 (with xN at the front)
}

[See below for answers]

————————————————————————————

Note about Other Queues

Double-ended queues – These are data structures which support both push and pop and enqueue/dequeue operations.

Priority Queues(heaps) – Supports insertions and “remove minimum” operations which useful in simulations to maintain a queue of time events.

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).

Applications

Stacks are used to manage methods at runtime (when a method is called, its parameters and local variables are pushed onto a stack; when the method returns, the values are popped from the stack). Many parsing algorithms (used by compilers to determine whether a program is syntactically correct) involve the use of stacks. Stacks can be used to evaluate arithmetic expressions (e.g., by a simple calculator program), and they are also useful for some operations on graphs, a data structure we will learn about later in the semester.

Queues are useful for many simulations, and are also used for some operations on graphs and trees.

Appliations of Stack

  • The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
  • Another application is an “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
Backtracking. This is a process when you need to access the most recent data element in a series of elements. Think of a labyrinth or maze – how do you find a way from an entrance to an exit?Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.
  • Language processing:
    • space for parameters and local variables is created internally using a stack.
    • compiler’s syntax check for matching braces is implemented by using stack.
    • support for recursion

 

The simplest two search techniques are known as Depth-First Search(DFS) and Breadth-First Search (BFS). These two searches are described by looking at how the search tree (representing all the possible paths from the start) will be traversed.

Deapth-First Search with a Stack

In depth-first search we go down a path until we get to a dead end; then we backtrack or back up (by popping a stack) to get an alternative path.

  • Create a stack
  • Create a new choice point
  • Push the choice point onto the stack
  • while (not found and stack is not empty)
    • Pop the stack
    • Find all possible choices after the last one tried
    • Push these choices onto the stack
  • Return

Breadth-First Search with a Queue

In breadth-first search we explore all the nearest possibilities by finding all possible successors and enqueue them to a queue.

  • Create a queue
  • Create a new choice point
  • Enqueue the choice point onto the queue
  • while (not found and queue is not empty)
    • Dequeue the queue
    • Find all possible choices after the last one tried
    • Enqueue these choices onto the queue
  • Return

We will see more on search techniques later in the course.

Arithmetic Expression Evaluation with Stack

An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation:

1 + ((2 + 3) * 4 + 5)*6

We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix.

Converting from Infix to Postfix.

Typically, we deal with expressions in infix notation

2 + 5

where the operators (e.g. +, *) are written between the operands (e.q, 2 and 5). Writing the operators after the operands gives a postfix expression 2 and 5 are called operands, and the ‘+’ is operator. The above arithmetic expression is called infix, since the operator is in between operands. The expression

2 5 +

Writing the operators before the operands gives a prefix expression

+2 5

Suppose you want to compute the cost of your shopping trip. To do so, you add a list of numbers and multiply them by the local sales tax (7.25%):

70 + 150 * 1.0725

Depending on the calculator, the answer would be either 235.95 or 230.875. To avoid this confusion we shall use a postfix notation

70  150 + 1.0725 *

Postfix has the nice property that parentheses are unnecessary.

Now, we describe how to convert from infix to postfix.

  1. Read in the tokens one at a time
  2. If a token is an integer, write it into the output
  3. If a token is an operator, push it to the stack, if the stack is empty. If the stack is not empty, you pop entries with higher or equal priority and only then you push that token to the stack.
  4. If a token is a left parentheses ‘(‘, push it to the stack
  5. If a token is a right parentheses ‘)’, you pop entries until you meet ‘(‘.
  6. When you finish reading the string, you pop up all tokens which are left there.
  7. Arithmetic precedence is in increasing order: ‘+’, ‘-‘, ‘*’, ‘/’;

Example. Suppose we have an infix expression:2+(4+3*2+1)/3. We read the string by characters.

'2' - send to the output.
'+' - push on the stack.
'(' - push on the stack.
'4' - send to the output.
'+' - push on the stack.
'3' - send to the output.
'*' - push on the stack.
'2' - send to the output.

Evaluating a Postfix Expression.

We describe how to parse and evaluate a postfix expression.

  1. We read the tokens in one at a time.
  2. If it is an integer, push it on the stack
  3. If it is a binary operator, pop the top two elements from the stack, apply the operator, and push the result back on the stack.

Consider the following postfix expression

5 9 3 + 4 2 * * 7 + *

Here is a chain of operations

Stack Operations              Output
--------------------------------------
push(5);                        5
push(9);                        5 9
push(3);                        5 9 3
push(pop() + pop())             5 12
push(4);                        5 12 4
push(2);                        5 12 4 2
push(pop() * pop())             5 12 8
push(pop() * pop())             5 96
push(7)                         5 96 7
push(pop() + pop())             5 103
push(pop() * pop())             515

Note, that division is not a commutative operation, so 2/3 is not the same as 3/2.

 

Java Implementations

Each of these containers implement the Container interface, as shown by the following diagram:

The rest of this article describes each of these container types in detail.

 

Stack

In addition to implementing the methods defined in the Container interface, a Stack supports the push() the pop() methods as shown by the following example.
Example Stacks1.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import java.util.Enumeration;

import COM.objectspace.jgl.*;

public class Stacks1

{

public static void main( String[] args )

{

Stack stack = new Stack();

stack.push( “bat” );

stack.push( “cat” );

stack.push( “dog” );

System.out.println( “stack = ” + stack );

System.out.println();

System.out.println( “Non-destructively enumerate the Stack.” );

Enumeration e = stack.elements();

while ( e.hasMoreElements() )

System.out.println( e.nextElement() );

System.out.println();

System.out.println( “Pop and print each element.” );

while ( !stack.isEmpty() )

System.out.println( stack.pop() );

}

}

Output

stack = Stack( Array( bat, cat, dog ) )

Non-destructively enumerate the Stack.

bat

cat

dog

Pop and print each element.

dog

cat

bat

By default, a Stack uses an Array for its underlying storage. To change this to a different container, supply the container when the Stack is constructed.
Example Stacks2.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import COM.objectspace.jgl.*;

public class Stacks2

{

public static void main( String[] args )

{

// Use a DList as the underlying data structure.

Stack stack = new Stack( new DList() );

stack.push( “bat” );

stack.push( “cat” );

stack.push( “dog” );

System.out.println( “Print the Stack.” );

System.out.println( stack );

}

}

Output

Print the Stack.

Stack( DList( bat, cat, dog ) )

Queue

In addition to implementing the methods defined in the Container interface, a Queue supports the push() and pop() methods as shown by the following example.
Example Stacks3.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import java.util.Enumeration;

import COM.objectspace.jgl.*;

public class Stacks3

{

public static void main( String[] args )

{

Queue queue = new Queue();

queue.push( “bat” );

queue.push( “cat” );

queue.push( “dog” );

System.out.println( “queue = ” + queue );

System.out.println();

System.out.println( “Non-destructively enumerate the Queue.” );

Enumeration e = queue.elements();

while ( e.hasMoreElements() )

System.out.println( e.nextElement() );

System.out.println();

System.out.println( “Pop and print each element.” );

while ( !queue.isEmpty() )

System.out.println( queue.pop() );

}

}

Output

queue = Queue( SList( bat, cat, dog ) )

Non-destructively enumerate the Queue.

bat

cat

dog

Pop and print each element.

bat

cat

dog

By default, a Queue uses an SList for its underlying storage. To change this to a different container, supply the container when the Queue is constructed.

PriorityQueue

A PriorityQueue uses an internal Array to store pushed elements in a heap structure. By default, elements are compared using their hash values, although you can change this behavior by supplying a function object when the queue is constructed. Note that although a PriorityQueue always pops elements in the order determined by the comparitor, this does not mean that that objects are stored in order within the internal heap structure. The following example uses a PriorityQueue to push and pop Integer objects in descending order.
Example Stacks4.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import java.util.Enumeration;

import COM.objectspace.jgl.*;

public class Stacks4

{

public static void main( String[] args )

{

// Use a HashComparator for comparing elements. Since the hash value of an

// Integer is its int value, this will order Integers in descending order.

PriorityQueue queue = new PriorityQueue();

queue.push( new Integer( 5 ) );

queue.push( new Integer( -2 ) );

queue.push( new Integer( 10 ) );

queue.push( new Integer( 6 ) );

queue.push( new Integer( 20 ) );

queue.push( new Integer( -10 ) );

System.out.println( “queue = ” + queue );

System.out.println();

System.out.println( “Non-destructively enumerate the PriorityQueue.” );

Enumeration e = queue.elements();

while ( e.hasMoreElements() )

System.out.print( e.nextElement() + ” ” );

System.out.println();

System.out.println( “Pop and print each element.” );

while ( !queue.isEmpty() )

System.out.print( queue.pop() + ” ” );

System.out.println();

}

}

Output

queue = PriorityQueue( Array( 20, 10, 5, -2, 6, -10 ) )

Non-destructively enumerate the PriorityQueue.

20 10 5 -2 6 -10

Pop and print each element.

20 10 6 5 -2 -10
Example Stacks5.java

// Copyright(c) 1996,1997 ObjectSpace, Inc.

import COM.objectspace.jgl.*;

public class Stacks5

{

public static void main( String[] args )

{

// Use a GreaterString function object for comparing elements. This will

// order strings in ascending order.

PriorityQueue queue = new PriorityQueue( new GreaterString() );

queue.push( “cat” );

queue.push( “dog” );

queue.push( “ape” );

queue.push( “bat” );

queue.push( “fox” );

queue.push( “emu” );

System.out.println( “Pop and print each element.” );

while ( !queue.isEmpty() )

System.out.print( queue.pop() + ” “);

System.out.println();

}

}

Output

Pop and print each element.

ape bat cat dog emu fox

 

Answers to Above Questions

Test Yourself #1

public Stack() {
  items = new Object[INITSIZE];
  numItems = 0;
}

Test Yourself #2

public Object pop() throws EmptyStackException {
  if (numItems == 0) throw new EmptyStackException();
  else {
    numItems--;
    return items[numItems];
  }
}

Test Yourself #3

OPERATION

WORST-CASE TIME

AVERAGE-CASE TIME

constructor

O(1)

O(1)

empty

O(1)

O(1)

size

O(1)

O(1)

push

O(N)

O(1)

pop

O(1)

O(1)

peek

O(1)

O(1)

Test Yourself #4

public void push(Object ob) {
  items = new Listnode(ob, items);
  numItems++;
}

Test Yourself #5

OPERATION

WORST-CASE TIME

constructor

O(1)

empty

O(1)

size

O(1)

push

O(1)

pop

O(1)

peek

O(1)

Test Yourself #6

public static void reverseQ(Queue q) {
  // precondition: q contains x1 x2 ... xN (with x1 at the front)
  // postcondition: q contains xN ... x2 X1 (with xN at the front)
  Stack s = new Stack();
  while (!q.empty()) s.push(q.dequeue());
  while (!s.empty()) q.enqueue(s.pop());
}

 Images That Might Help you

s1 s2 s3 s4 s5 s6 s7 s8 s9

If you find this site useful, please support us. Like our FaceBook Page. You can also contact us by mail: portaltechinfo@gmail.com

Tagged: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: