22.8. Queues and Priority Queues

 
[Page 675 ( continued )]

20.3. Stacks and Queues

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.

Listing 20.6. MyQueue.java
(This item is displayed on pages 675 - 676 in the print version)
 1    public class   MyQueue  { 2    private   MyLinkedList list =   new   MyLinkedList();  3 4    public void   enqueue(Object o)  { 5 list.addLast(o); 6 } 7 

[Page 676]
 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 } 

Figure 20.15. MyQueue uses a linked list to provide a first-in/first-out data structure.


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.

Figure 20.16. The program uses a stack and a queue to store and process strings.


Listing 20.7. TestStackQueue.java
(This item is displayed on pages 676 - 677 in the print version)
 1   public class   TestStackQueue { 2   public static void   main(String[] args) { 3  // Create a stack  4  MyStack stack =   new   MyStack();  5 

[Page 677]
 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.

 


Introduction to Java Programming-Comprehensive Version
Introduction to Java Programming-Comprehensive Version (6th Edition)
ISBN: B000ONFLUM
EAN: N/A
Year: 2004
Pages: 503

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net