Stacks and Queues

Simple Queue Implementation [File]

Introduction

Two of the more used data structures in programming are the Stack and the Queue. Each of which has important real-world (programming) applications which you use without knowing every day.

Stacks and queues are both data types used when working with a large number of objects, just like a List or a Set. The behaviour of the set is what sets them apart. Just like a set, you should not randomly access or change the elements of a stack or a queue. Instead you must follow a pre-determined access sequence defined by the data structure.

Stack [Java 1.8 Class]

A stack behaves much in the same way as you would expect when you interact with a stack of paper in the real world:

  • When you grab a piece of paper, you grab one from the top reducing the size of the stack by 1.
  • When you add a piece of paper, you add it to the top, increasing the size of the stack by 1.

In other words, stacks operate under a Last-In, First-Out, or LIFO operation policy. This means that a stack has a fairly standard set of methods that are used:

  • Insert an object to the top of the stack. By tradition, this is called "pushing an object," which is done via the push method.
  • Remove an object from the top of the stack. By tradition, this is called "popping an object," which is done via the pop method.
  • Check if the collection is empty. In Java this is done through the isEmpty() method.
  • Determine the current size of the collection. In Java this is done through the size() method.

Traditionally, these are the only 4 methods needed for a stack data type. It is often, however, useful to check the top item of your stack without removing it. This is done through a peek method.

Note: In Java, a Stack is an already implemented class and inherits from the Vector class. A Vector is just a thread-safe ArrayList. This means a Java Stack<E> does not need to be implemented and the Stack object also has methods like elementAt(int index), insert(E e, int index), and remove(int index). These methods circumvent the purpose of the stack data type and should only be used sparingly.

How Does A Stack Work?

Typically, we would maintain a variable, say n, which tells us how many items have been pushed (that have not been popped). We would also have some other data structure such as a list or array which would store all of the items on our stack.

As a consequence, the most recently added item would be at position n-1, and the least recently added item would be at position 0.

Where Are Stacks Used in Programming?

There are a lot of low-level situations where stacks are very useful. Three good examples are:

  • Expression Evaluation (see your future assignment!)
  • Method/Function calls
  • Undo/Redo in a word processor

In addition, If you think about the back button on your web browser, this is very close to how a stack works, with one major exception. If you go back a few times you can still go forward to the pages you were just on, unless you go to a different page you had not originally visited. In this case all of your "forward" progress is lost and you create a new history.

public interface ISimpleStack<E> {
    /**
     * Places the object, item, on the top of the stack.
     * @param item - the item to be pushed onto this stack.
     */
    public void push(E item);

    /**
     * Removes the item on the top of the stack and returns 
     * it.
     * @return the item from the top of the stack.
     */
    public E pop();

    /**
     * Returns the item at the top of the stack without
     * changing the stack contents.
     * @return the item from the top of the stack.
     */
    public E peek();

    
    /**
     * Tests if this stack is empty.
     * @return true if and only if this stack contains no 
     *    items; false otherwise
     */
    public boolean isEmpty();

    /**
     * Returns the number of items in the stack.
     * @return an integer representing the number of items
     *    currently in the stack.
     */
    public int size();
}

Stack Exercises

1. a) What would be a reasonable response to attempting to pop an empty stack? Why?

b) What would happen if you pushed a null element onto a stack? Does that affect how you think of your response to question (a)?

2. Reverse a String using a stack.

3. Create a stack using an array whose size you control. The array must always be no more than twice the size of the number of items within it, except for a minimum size (say, 5). For example:

  • [1, 2, 3, null, null] - Stack has 3 items, and is of size 5.
    • push (4) => [1, 2, 3, 4, null] - 4 items, size 5.
    • push (5) => [1, 2, 3, 4, 5] - 5 items, size 5.
    • push (6) => [1, 2, 3, 4, 5, 6, null, null, null, null] - 6 items, size 10. We doubled the size of the array to add space.
    • pop() => [1, 2, 3, 4, 5, null, null, null, null, null] - 5 items, size 10. Number of items is greater than or equal to half the size of the array, still good.
    • pop() => [1, 2, 3, 4, null] - 4 items, size 5. Size was less than half of 10, so we cut the array in half.

Queue [Java 1.8 Interface]

A queue behaves much like a line you would enter at an amusement park:

  • A person enters (enqueues) at the back of the line
  • A person exits (dequeues) at the front of the line, but only after every other person who queued before them exits.

In other words, a queue operates under the First-In, First-Out or FIFO operation policy. Which allows us to have a fairly standard interface:

  • Insert an object to the back of the queue. By tradition, this is called "enqueuing" and is performed by the enqueue method.
  • Remove an object from the front of the queue. By tradition, this is called "dequeuing" and is performed by the dequeue method.
  • Check if the collection is empty. In Java this is done through the isEmpty() method.
  • Determine the current size of the collection. In Java this is done through the size() method.

Traditionally, these are the only 4 methods needed for a queue data type. It is often, however, useful to check the front item of your queue without removing it. This is done through a peek method.

How Does A Queue Work?

Though there are better underlying ways of creating a queue, you can create a queue using a primitive array. To do this you need to think of an array as more of a circular structure. So, instead of this:

Think of a Queue like this:

This change in thought allows us to avoid some very expensive reorganisation of elements when we dequeue an object.

In order to accomplish this, we must store two index values:

  • The first points to the front of the list, used to dequeue objects. Call this index front.
  • The second points to one index past the last item in our list. Call this index back. This index helps us to determine size (front-back), and is useful for enqueuing objects.
public interface ISimpleQueue<E> {
    /**
     * Add an item to the queue.
     * @param item - The item being added to the queue
     */
    public void enqueue(E item);

    /**
     * Returns the next item in the queue, removing it from
     * the queue in the process.
     * @return the item being removed from the queue
     */
    public E dequeue();

    /**
     * Returns the item at the front of the queue without
     * changing the queue contents.
     * @return the item at the front of the queue.
     */
    public E peek();

    /**
     * Tests is the queue is empty.
     * @return true if and only if this queue contains no
     *    items; false otherwise.
     */
    public boolean isEmpty();

    /**
     * Returns the number of items in the queue.
     * @return the number of items currently stored in the 
     *    queue
     */
    public int size();
}

Where Are Queues Used in Programming?

Queues are an essential part of internet communication: Requests made to retrieve a website from a server may be queued if there are many requests that happen simultaneously. Another example; tasks to be performed by a CPU/GPU are usually queued and performed by the first available processor. Queues can also used for:

  • Printing
  • Searching other data structures, such as Trees (more on that later).
  • Quick processing of arithmetic operations (See your future assignment)

Queue Exercises

1. What would be a reasonable response for calling dequeue() on an empty queue? Why? Would your answer change if calling enqueue() with a null element was allowed?

2. Simulate a checkout at a grocery store:

    • Your program should start with an empty queue for items placed in the checkout by the customer.
      • The number of items being processed should be determined at runtime.
    • Create an outer loop that does 3 things:
      • Decide, randomly, to add or not add an item to the queue.
        • To start, make the program add items at a 50-50 rate. You may find this does not work well and you need to adjust your rate.
        • The item will have a random amount of processing time (5-50), and a price.
        • When you add an item to the queue, print "New Item being queued" and the current number of items in the queue to the console.
      • If the cashier is busy processing an item, continue to process it until it is finished.
        • Processing an item consists of reducing its current processing time by 1 until it reaches 0.
        • When the item being processed reaches 0, add the price of the item to the subtotal.
      • If there is an item available in the queue and the cashier is not busy processing an item, dequeue an item and begin processing it.
        • When you begin processing the item, print "Processing," the item number and the total processing time to the console.
    • After you are finished processing all items, print the subtotal, tax (13%) and final price of the transaction to the screen.