Modeling Stacks and Queues Using Arrays

Stacks and queues don't necessarily need to be dynamic. You may want a more concise implementation if you know your data requirements are of a fixed size. Using an array approach to model stacks and queues guarantees that your data structure will only grow up to a certain size. The other advantage of using an array is that the array approach is more memory efficient if you can live with having a static data structure. The catch with static data structures is that the queue or stack can only grow to a maximum fixed size of your initially allocated array.

Implementing a stack using an array involves first initializing an empty array with a fixed size. Then, it's a matter of keeping an index pointer to the top of the stack, initially pointing to zero. As we push items on the stack, we place the item at this index and increment the pointer by one. When we need to pop an element, we reduce this pointer by one and read the value. This process is shown in the following code:

public StackArray(int capacity) {
array = (V[]) new Object[capacity];
}
public void push(V item) {
array[headPtr++] = item;
}
public Optional<V> pop() {
if (headPtr > 0) return Optional.of(array[--headPtr]);
else return Optional.empty();
}
Snippet 2.24: Stack using an array instead of linked list. Source class name: Stackarray

Go to https://goo.gl/T61L33 to access the code

Implementing a queue using an array requires a little more thinking. The difficulty with a queue is that the structure is modified from both ends since it grows from the tail and shrinks from the head.

As we enqueue and dequeue the contents of the queue, it seems to be moving towards the right of the array. We need to deal with what happens when the contents reaches the end of our array. To make the queue work in an array, we just need to let our data wrap around the edges (think Pacman, Figure 2.10):

Figure 2.10: Array wrap around analogy

When we reach the end of our array, we can just start again from the beginning index. This wrap around mechanism is called a circular buffer. It can be implemented using the modulus operator to access any element in the underlying array. The following code snippet shows how this works. Notice that when we enqueue an item, we place it at the tail position and increment the tail pointer using the mod operator. When the pointer is larger or equal to the size of the array, it wraps around and starts again from zero. The same happens on the dequeue method, where we access and increment the head pointer in a similar fashion. The following code demonstrates it:

The implementation in Snippet 2.25 does not check if the circular buffer is full before enqueuing another item. Implementing this check is given as an exercise in the next section.
public void enqueue(V item) {
array[tailPtr] = item;
tailPtr = (tailPtr + 1) % array.length;
}
public Optional<V> dequeue() {
if (headPtr != tailPtr) {
Optional<V> item = Optional.of(array[headPtr]);
headPtr = (headPtr + 1) % array.length;
return item;
} else return Optional.empty();
}
Snippet 2.25: Enqueue and dequeue using an array. Source class name: QueueArray

Go to https://goo.gl/LJuYz9 to access this code.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.147.58.194