A stack can be viewed as a special type of list whose elements are accessed, inserted, and deleted only from the end (top) of the stack. A queue represents a waiting list. A queue 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) of the queue.
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 with 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 using a linked list.
There are two ways to design the stack and queue classes:
Using inheritance : You can declare a stack class by extending the array list class, and a queue class by extending the linked list class.
Using composition : You can declare an array list as a data field in the stack class, and a linked list as a data field in the queue class.
Both designs are fine, but using composition is better because it enables you to declare 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 Listing 9.8, MyStack.java. Listing 20.6 implements the queue class using the composition approach. Figure 20.15 shows the UML of the class.
1 public class MyQueue { 2 private MyLinkedList list = new MyLinkedList(); 3 4 public void enqueue(Object o) { 5 list.addLast(o); 6 } 7 8 public Object dequeue() { 9 return list.removeFirst(); 10 } 11 12 public int getSize() { 13 return list. size (); 14 } 15 16 public String toString() { 17 return "Queue: " + list.toString(); 18 } 19 } |
A linked list is created to store the elements in a queue (line 2). The enqueue(Object o) method (lines 4 “6) adds element o into the tail of the queue. The dequeue() method (lines 8 “10) removes an element from the head of the queue and returns the removed element. The getSize() method (lines 12 “14) returns the number of elements in the queue.
Listing 20.7 gives an example that creates a stack using MyStack and a queue using MyQueue . 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). A sample run of the program is shown in Figure 20.16.
1 public class TestStackQueue { 2 public static void main(String[] args) { 3 // Create a stack 4 MyStack stack = new MyStack(); 5 6 // Add elements to the stack 7 stack.push( "Tom" ); // Push it to the stack 8 System.out.println( "(1) " + stack); 9 10 stack.push( "John" ); // Push it to the stack 11 System.out.println( "(2) " + stack); 12 13 stack.push( "George" ); // Push it to the stack 14 stack.push( "Michael" ); // Push it to the stack 15 System.out.println( "(3) " + stack); 16 17 // Remove elements from the stack 18 System.out.println( "(4) " + stack.pop() ); 19 System.out.println( "(5) " + stack.pop()); 20 System.out.println( "(6) " + stack); 21 22 // Create a queue 23 MyQueue queue = new MyQueue(); 24 25 // Add elements to the queue 26 queue.enqueue( "Tom" ); // Add it to the queue 27 System.out.println( "(7) " + queue); 28 29 queue.enqueue( "John" ); // Add it to the queue 30 System.out.println( "(8) " + queue); 31 32 queue.enqueue( "George" ); // Add it to the queue 33 queue.enqueue( "Michael" ); // Add it to the queue 34 System.out.println( "(9) " + queue); 35 36 // Remove elements from the queue 37 System.out.println( "(10) " + queue.dequeue() ); 38 System.out.println( "(11) " + queue.dequeue()); 39 System.out.println( "(12) " + queue); 40 } 41 } |
For a stack, the push(o) 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.
For a queue, the enqueue(o) method adds an element to the tail of the queue, and the dequeue() method removes the element from the head of the queue.