5.2
Static data structures

Efficiency is discussed later on in this topic, basically, option 1 is an O(0) operation - does not depend on the size of the stack, whereas the second option is an O(n) operation.

The point being, there might not be any space left on the stack!

same static structure

different pointers

much the same process as for the stack

The flags

Set at start

Main loop

modulo operator used to wrap around

if we just added an item, the queue can't be empty

on this page: [ ibio | stacks | queues ]

IBIO

You should be able to compile these examples in any Java editor, such as BlueJ or JCreator. All of the examples assume that the IBIO methods exist in the file.

An example class using these methods is found here . Make sure you can compile and run this source code if you want to implement any of the examples given in these pages.

Any code you want to try out should be placed in the Constructor:

/**
* Constructor for objects of class Adams
*/
public Adams()
{
     // valid Java or JETS statements may be placed here...
     output("The answer is: " + d);
}

You may want to change the Class name, in which case, remember that:

• the file name must be the same as the class name with the extension .java
• the constructor name must be the same as the class name.
• you ought to change the comments to reflect what your program does.

Stack in an array

An array is going to be used to hold a sequence of characters:

Initially, a pointer, size , is set to 0, so stack[size] is the next available element. To push an item onto the stack we can work one of two ways:

• Allocate the item to stack[size] then move size up one in the array
• Allocate the item to stack[0] and increment size by 1

It should be apparent that the second option involves shuffling up elements whereas the first only requires the stack pointer to be moved.

Given:

   private static final int SIZE = 12;      // a constant for the stack size
   private char[] stack = new char[SIZE];  // the array to hold the stack
   private int size = 0;                   // the number of items in the stack

A possible push operation is:

  // method to push an item onto the stack
   public void push(char item)
   {      
     stack[size] = item;
     size = size + 1;
   }

Which works up to a point. Is there any check that needs to be done? Add it.

So far, the code might look like this:

/**
* Class Stack
* Implements a stack of Characters
* Uses an array - is a static data structure
*/
public class Stack
{
   private static final int SIZE = 12;      // a constant for the stack size
   private char[] stack = new char[SIZE];   // the array to hold the stack
   private int size = 0;                    // the number of items in the stack

   // Constructor
   public Stack()
   {
     size = 0;
     char c;
     do
     {
       c = inputChar("Input a character ('/' to end)");
       push(c);
       display();
     } while (c != '/');
   }
   // method to push an item onto the stack
   public void push(char item)
   {
     if (size < SIZE)
     {
       stack[size] = item;
       size = size + 1;
     }
     else
     {
       output("Stack full");
     }
   }
   public void display()
   {
     output("stack");
     output("=====");
     for(int p = (size - 1); p >= 0; p--)
     {
       output(p + ":> " + stack[p]);
     }
     output("=====");
   }
   // Main method for class stack
   public static void main(String[] args)
   {
     new Stack();
   }
   //============================================================
   // Below are the IBIO simple input and output methods
   // to be included in the Class.

Exercises

Write the method pop, to remove an item from the stack - being sure to watch out for underflow (when there are not any items on the stack).

Write the algorithm which reverses a character String in place (a discussion of this is found on the previous page). To take an input String and split it into characters, you might need something like:

  String s = input("Please input a String");
   for (int p = 0; p < s.length(); p++)
   {
     char c = s.getChar(p);
    // process c

To concatenate characters into a String try something like:

  String s;
   char c;
   s = s + c; // string s with char c added at the end (concatenated)

A useful method, top, returns the top element from the stack, if it exists, without popping it. Implement this.

Queue in an array

We have seen a possible way of implementing a queue using a linked list , but this section is concerned with static data structures. So let's see how we might go about using the same array as above, except that we will need two pointers into the array, front and rear.

Recall the items are added at the rear ( enqueued ) and removed from the front ( dequeued ).

It seems reasonable to have both front and rear point to element 0 initially. To enqueue an item, place it at rear then increment rear to point at the next free location.

Check to see if the end of the array has been reached:

**
*Class Queue
*Implements a stack of Characters
*Uses an array - is a static data structure
*/
public class Queue
{
   private static final int SIZE = 12;     // a constant for the queue size
   private char[] queue = new char[SIZE];  // the array to hold the queue
   private int front = 0;                  // the first item in the queue
   private int rear = 0;                   // the last item in the queue

   // Constructor
   public Queue()
   {
     front = 0;
     rear = 0;
     char c;
     do
     {
       c = inputChar("Input a character ('/' to end)");
       enqueue(c);
       display();
     } while (c != '/');
   }
   public void enqueue(char item)
   {
     if (rear < SIZE)
     {
       queue[rear] = item;
       rear = rear + 1;
     }
     else
     {
       output("Queue full - cannot add item");
     }
   }
   public void display()
   {
     output("front");
     output("=====");
     for(int p = front; p < rear; p++)
     {
       output(p + ":> " + queue[p]);
     }
     output("=====");
   }
   // Main method for class queue
   public static void main(String[] args)
   {
     new Queue();
   }
//============================================================
// Below are the IBIO simple input and output methods

Exercise

Implement the dequeue method, be sure to test if there is anything in the queue to remove.

You might want to change the Constructor to allow the dequeue to be called:

     c = inputChar("Input a character ('/' to end, '#' to dequeue)");

You can either return a character from the dequeue method or output it within the method body.

Once you have got that working, there are a few problems here - try adding asnd removing enough items and we get to a point where the rear pointer has run up against the end of the array, yet there is still space at the front of the array:

So, what we need to do is wrap the front pointer around to the start again.

However, we have to be able to detect when the queue is full , when the rear pointer catches up with the front pointer.

There are several ways to deal with this problem, the simplest of which is probably to maintain a special flag qFull which we will set true when the front reaches the rear and unset whenever we dequeue an item.

It is also possible to use a qEmpty flag in a similar way.

/**
*Class Queue
*Implements a stack of Characters
*Uses an array - is a static data structure
*/
public class Queue
{
   private static final int SIZE = 12;    // a constant for the queue size
   private char[] queue = new char[SIZE]; // the array to hold the queue
   private int front = 0;                  // the first item in the queue
   private int rear = 0;                   // the last item in the queue
   private boolean qFull = false;          // flag
   private boolean qEmpty = true;          // nothing in the queue initially
   // Constructor
   public Queue()
   {
     front = 0;
     rear = 0;
     qFull = false;
     qEmpty = true;

     char c;
     do
     {
       c = inputChar("Input a character ('/' to end, '#' to dequeue)");
       if ( (c != '/') && (c !='#'))
       {
         enqueue(c);
       }
       else if (c == '#')
       {
         dequeue();
       }
       display();

     } while (c != '/');
   }
   public void enqueue(char item)
   {
     if (qFull)
     {
       output("Queue full - cannot add item");
     }
     else
     {
       queue[rear] = item;
       rear = (rear + 1) % SIZE;
       qFull = (rear == front);
       qEmpty = false;
     }
   }
   public void dequeue()
   {
     if (qEmpty)
     {
       output("Empty queue");
     }
     else
     {
       char c = queue[front];
       front = (front + 1) % SIZE;
       output("dequeued: " + c);
       qFull = false;
       qEmpty = (front == rear);
     }
   }
   public void display()
   {
     output("front");
     output("=====");
     for(int p = front; p != rear; p = (p + 1) % SIZE)
     {
       output(p + ":> " + queue[p]);
     }
     output("=====");
   }
   // Main method for class queue
   public static void main(String[] args)
   {
     new Queue();
   }
//============================================================
// Below are the IBIO simple input and output methods

Exercises

Write self-contained Queue Class that can enque and dequeue Strings or other Objects of your own choosing.

The Class should implement Exception handling so that EmptyQueue, FullQueue and other custom exceptions can be thrown.

Additional methods mught be getFront, getRear to examine, but not remove these items. A method to return the current size of the queue would also be useful.

Back to top

related: [ ADT home | previous: fundamentals | next: dynamic data structures ]

Remember that you need not know how the IBIO methods work, only that you can use, eg, inputDouble() to input a double value.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.