Stacks and Queues

Stacks can be implemented using array lists and queues can be implemented using linked lists. A stack can be viewed as a special type of list whose elements are accessed, inserted, and deleted only from the end (top). A queue represents a waiting list. It can be viewed as a special type of list whose elements are inserted into the end (tail) of the queue, and are accessed and deleted from the beginning (head), as shown in Figure below.

Since the insertion and deletion operations on a stack are made only at the end of the stack, it is more efficient to implement a stack with an array list than a linked list. Since deletions are made at the beginning of the list, it is more efficient to implement a queue using a linked list than an array list. This section implements a stack class using an array list and a queue class using a linked list.

There are two ways to design the stack and queue classes:

• Using inheritance: You can define a stack class by extending ArrayList, and a queue class by extending LinkedList, as shown in Figure below (a).
• Using composition: You can define an array list as a data field in the stack class, and a linked list as a data field in the queue class, as shown in Figure below (b).

Both designs are fine, but using composition is better because it enables you to define a completely new stack class and queue class without inheriting the unnecessary and inappropriate methods from the array list and linked list. The implementation of the stack class using the composition approach was given in GenericStack.java. The code below implements the GenericQueue class using the composition approach. Figure below shows the UML of the class.

A linked list is created to store the elements in a queue (lines 4). The enqueue(e) method (lines 6–8) adds element e into the tail of the queue. The dequeue() method (lines 10–12) removes an element from the head of the queue and returns the removed element. The getSize() method (lines 14–16) returns the number of elements in the queue.

The code below gives an example that creates a stack using GenericStack and a queue using GenericQueue. It uses the push (enqueue) method to add strings to the stack (queue) and the pop (dequeue) method to remove strings from the stack (queue).

package demo;

public class TestStackQueue {

    public static void main(String[] args) {
        // Create a stack
        GenericStack<String> stack = new GenericStack<>();

        // Add elements to the stack
        stack.push("Tom"); // Push it to the stack
        System.out.println("(1) " + stack);

        stack.push("Susan"); // Push it to the stack
        System.out.println("(2) " + stack);

        stack.push("Kim"); // Push it to the stack
        stack.push("Michael"); // Push it to the stack
        System.out.println("(3) " + stack);

        // Remove elements from the stack
        System.out.println("(4) " + stack.pop());
        System.out.println("(5) " + stack.pop());
        System.out.println("(6) " + stack);

        // Create a queue
        GenericQueue<String> queue = new GenericQueue<>();

        // Add elements to the queue
        queue.enqueue("Tom"); // Add it to the queue
        System.out.println("(7) " + queue);

        queue.enqueue("Susan"); // Add it to the queue
        System.out.println("(8) " + queue);

        queue.enqueue("Kim"); // Add it to the queue
        queue.enqueue("Michael"); // Add it to the queue
        System.out.println("(9) " + queue);

        // Remove elements from the queue
        System.out.println("(10) " + queue.dequeue());
        System.out.println("(11) " + queue.dequeue());
        System.out.println("(12) " + queue);
    }

}

(1) stack: [Tom]
(2) stack: [Tom, Susan]
(3) stack: [Tom, Susan, Kim, Michael]
(4) Michael
(5) Kim
(6) stack: [Tom, Susan]
(7) Queue: [Tom]
(8) Queue: [Tom, Susan]
(9) Queue: [Tom, Susan, Kim, Michael]
(10) Tom
(11) Susan
(12) Queue: [Kim, Michael]

For a stack, the push(e) method adds an element to the top of the stack, and the pop() method removes the top element from the stack and returns the removed element. It is easy to see that the time complexity for the push and pop methods is O(1).

For a queue, the enqueue(e) method adds an element to the tail of the queue, and the dequeue() method removes the element from the head of the queue. It is easy to see that the time complexity for the enqueue and dequeue methods is O(1).