import java.awt.*; import java.awt.event.*; import javax.swing.*; import java.util.ArrayList; /** * This program demonstrates stack and queue operations. The program shows * a grid of squares. When the user clicks on one of the squares, a computation * is begun that visits all the squares of the grid. As the squares * are "encountered", they are colored red. Red squares have been encountered * but not yet processed. A square is processed by adding its horizontal * and vertical neighbors to the set of encountered squares, if they have * not previously been encountered. Once a square has been processed in * this way, it is "finished", and it is colored gray. At the end of the * process, all the squares are gray. * The question is, how does the program decide which red square to * process? There can be many red squares waiting for processing. * The user can specify one of three methods for deciding which square * to process: with a stack, with a queue, or at random. If the random * method is chosen, then a red square is chosen for processing at random * from among all the red squares. If a queue is used, the red squares * are stored on a queue and are processed in FIFO order. If a stack * is used, then the squares are processed in LIFO order. * (Note: If the user clicks on a white square while a computation is * already running, then that square will be "encountered" and added to * the set of red squares.) * This class contains a main() routine that allows it to be run as a * standalone application. */ public class DepthBreadth extends JPanel implements MouseListener, ActionListener { /** * main() routine just opens a window with a DepthBreadth panel * as its content pane. */ public static void main(String[] args) { JFrame window = new JFrame("Stack and Queue Demo"); window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); window.setContentPane( new DepthBreadth(334,380) ); window.pack(); window.setResizable(false); window.setLocation(150,100); window.setVisible(true); } /** * Represents one square in the grid, by specifying the * row number and column number where it is found. */ private static class Location { // int row; int column; Location(int r, int c) { // Constructor, specifying the row and column of a square. row = r; column = c; } } // end nested class Location /** * Represents a node in a linked list of Locations. Both the * Stack and the Queue class use this type of linked list. */ private static class Node { Location loc; // Represents one square in the grid. Node next; // Pointer to next Node in the linked list. } // end nested class Node /** * A stack of Locations, with the standard operations, * plus a getSize() method that returns the number of * Locations on the stack. */ private static class Stack { private Node top = null; // Pointer to the top of the stack. private int size = 0; // Number of items on the stack. void push(Location loc) { // Add the specified location to the top of the stack. Node newTop = new Node(); newTop.loc = loc; newTop.next = top; top = newTop; size++; } Location pop() { // Remove and return the top Location on the stack. // (Note that this can throw a NullPointerException if // it is called when the stack is empty.) Location topItem = top.loc; top = top.next; size--; return topItem; } boolean isEmpty() { // Return true if the stack is empty. return top == null; } int getSize() { // Return the number of Locations on the stack. return size; } } // end nested class Stack /** * A queue of Locations, with the standard operations, * plus a getSize() method that returns the number of * Locations on the queue. */ private static class Queue { private Node head = null; // Points to first Node in the queue. private Node tail = null; // Points to last Node in the queue. private int size; // Number of items on the queue. void enqueue(Location loc) { // Add the specified Location to the end of the queue. Node newTail = new Node(); newTail.loc = loc; if (head == null) { head = newTail; tail = newTail; } else { tail.next = newTail; tail = newTail; } size++; } Location dequeue() { // Remove and return the first item in the queue. // (Note that this will throw a NullPointerException // if the queue is empty.) Location firstItem = head.loc; head = head.next; if (head == null) tail = null; size--; return firstItem; } boolean isEmpty() { // Return true if the queue is empty. return head == null; } int getSize() { // Return the number of items on the queue. return size; } } // end nested class Queue private final static int SQUARE_SIZE = 12; // Size of one square in the grid. private int rows; // Number of rows in the grid. This depends on the size of the panel. private int columns; // Number of columns in the grid. This depends on the size of the panel. private boolean[][] encountered; // encountered[r][c] is set to true when a square is // first encountered. (See comment at top of file.) // A square that has been encountered but not // finished is red. private boolean[][] finished; // finished[r][c] is set to true when a square is // finished (i.e. processed). Finished squares are gray. private JButton abortButton; // User can click this to terminate the computation. private JLabel message; // For displaying information to the user. private JComboBox methodChoice; // For selecting the method of // selecting which red square to process. private final static int STACK = 0, // Possible values for the method. QUEUE = 1, RANDOM = 2; private int method; // Used to hold the selected method while a // computation is running. private Timer timer; // A timer that drives the computation. // When no computation is in progress, timer is null. private Queue queue; // Exactly one of these is used to store the private Stack stack; // red squares while the computation is running. private ArrayList randomList; // Which one is used depends on the method. /** * Construct the panel. * @param width the width of the panel * @param height the height of the panel. The height and width must be passed * as parameters because they are needed to determine how many rows and columns * are drawn. The height and width also become the preferred size of the panel. */ public DepthBreadth(int width, int height) { setLayout(null); setBackground(new Color(220,220,255)); setPreferredSize(new Dimension(width,height)); setBorder(BorderFactory.createMatteBorder(2,2,2,2,Color.BLUE)); addMouseListener(this); /* Determine the number of rows and columns and create the encountered and finished arrays. */ rows = (height - 100) / SQUARE_SIZE; columns = (width - 20) / SQUARE_SIZE; encountered = new boolean[rows][columns]; finished = new boolean[rows][columns]; /* Create the components. */ Font labelFont = new Font("SansSerif",Font.PLAIN,14); message = new JLabel("Click any square to begin.",JLabel.CENTER); message.setForeground(Color.blue); message.setFont(labelFont); methodChoice = new JComboBox(); methodChoice.addItem("Stack"); methodChoice.addItem("Queue"); methodChoice.addItem("Random"); methodChoice.setBackground(Color.WHITE); abortButton = new JButton("Abort"); abortButton.setEnabled(false); abortButton.addActionListener(this); abortButton.setBackground(Color.LIGHT_GRAY); JLabel lb = new JLabel("Use:", JLabel.RIGHT); // An unchanging informational label. lb.setForeground(Color.BLUE); lb.setFont(labelFont); /* Add the components to the panel and set their sizes and positions. */ add(message); add(lb); add(methodChoice); add(abortButton); message.setBounds(15, height-80, width-30, 18); lb.setBounds(15, height-54, 50, 18); methodChoice.setBounds(75, height-56, width-150, 22); abortButton.setBounds(75, height-29, width-150, 22); } // end init(); /** * The user has clicked the mouse on the panel. If the user has clicked on * a position in the grid, start a computation to start processing from that * square, or if a computation is already running, "encounter" the square. */ public void mousePressed(MouseEvent evt) { int row = (evt.getY() - 10) / SQUARE_SIZE; int col = (evt.getX() - 10) / SQUARE_SIZE; if (row < 0 || row >= rows || col < 0 || col >= columns) return; if (timer == null) { // Start a new computation at the point where the user clicked. startComputation(row,col); } else { // A computation is already in progress. // Mark the square where the user clicked as encountered. encounter(row,col); repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE); } } // end mousePressed() /** * When the user clicks the button, call doAbort(). Otherwise, this * is a Timer event, so do the next step in the computation. */ public void actionPerformed(ActionEvent evt) { if (evt.getSource() == abortButton) doAbort(); else continueComputation(); } /** * Begin a new computation. Set all the squares back to unencountered * and start a timer that will process the squares beginning with * the square at (startRow,startCol). */ void startComputation(int startRow, int startCol) { for (int r = 0; r < rows; r++) for (int c = 0; c < columns; c++) { encountered[r][c] = false; finished[r][c] = false; } method = methodChoice.getSelectedIndex(); switch (method) { case STACK: stack = new Stack(); message.setText("Using a stack."); break; case QUEUE: queue = new Queue(); message.setText("Using a queue."); break; case RANDOM: randomList = new ArrayList(); message.setText("Using a randomized list."); break; } abortButton.setEnabled(true); methodChoice.setEnabled(false); encounter(startRow,startCol); repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE); timer = new Timer(75,this); timer.start(); } /** * Do one step in a computation, by processing * one location from the stack, queue, or arraylist. * If no more items are available, finish the computation. */ public void continueComputation() { Location loc = removeItem(); if (loc != null) { finish(loc.row, loc.column); } else { // All squares have already been "finished". The // computation is complete. timer.stop(); timer = null; methodChoice.setEnabled(true); abortButton.setEnabled(false); message.setText("Click any square to begin."); queue = null; stack = null; randomList = null; } repaint(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE); } /** * Stop the computation, if one is running. This is called * when the user clicks the Abort button. */ void doAbort() { if (timer != null) { timer.stop(); timer = null; methodChoice.setEnabled(true); abortButton.setEnabled(false); message.setText("Click any square to begin."); queue = null; stack = null; randomList = null; } } /** * Get the next item to be processed from the appropriate data structure. * The data structure that is being used depends on the method. If the data * structure is empty, return null. Also, display the size of the data * structure to the user. */ Location removeItem() { Location loc = null; switch (method) { case STACK: if ( ! stack.isEmpty() ) loc = stack.pop(); message.setText("Stack size is " + stack.getSize()); break; case QUEUE: if ( ! queue.isEmpty() ) loc = queue.dequeue(); message.setText("Queue size is " + queue.getSize()); break; case RANDOM: if ( randomList.size() > 0 ) { int index = (int)(randomList.size()*Math.random()); loc = randomList.get(index); randomList.remove(index); } message.setText("List size is " + randomList.size()); break; } return loc; } /** * If there is a square at (r,c) that has not already been encountered, * encounter it and add it to the data structure. The data structure * that is used depends on the method. Also, display the size of the * data structure. */ void encounter(int r, int c) { if (r < 0 || r >= rows || c < 0 || c >= columns || encountered[r][c] == true) return; Location loc = new Location(r,c); switch (method) { case STACK: stack.push(loc); message.setText("Stack size is " + stack.getSize()); break; case QUEUE: queue.enqueue(loc); message.setText("Queue size is " + queue.getSize()); break; case RANDOM: randomList.add(loc); message.setText("List size is " + randomList.size()); break; } encountered[r][c] = true; } /** * Process the red square at (r,c) by encountering its horizontal and * vertical neighbors. */ void finish(int r, int c) { encounter(r-1,c); encounter(r+1,c); encounter(r,c-1); encounter(r,c+1); finished[r][c] = true; } public void mouseReleased(MouseEvent e) { } // Methods required by MouseListener interface public void mouseClicked(MouseEvent e) { } public void mouseEntered(MouseEvent e) { } public void mouseExited(MouseEvent e) { } /** * Paint the grid of squares. (Other components contained in the panel paint themselves.) */ public void paintComponent(Graphics g) { super.paintComponent(g); //Fill with background color /* Fill the area occupied by the grid with white, then draw black lines around this area and between the squares of the grid. */ g.setColor(Color.white); g.fillRect(10, 10, columns*SQUARE_SIZE, rows*SQUARE_SIZE); g.setColor(Color.black); for (int i = 0; i <= rows; i++) g.drawLine(10, 10 + i*SQUARE_SIZE, columns*SQUARE_SIZE + 10, 10 + i*SQUARE_SIZE); for (int i = 0; i <= columns; i++) g.drawLine(10 + i*SQUARE_SIZE, 10, 10 + i*SQUARE_SIZE, rows*SQUARE_SIZE + 10); /* Fill "encountered" squares with red and "finished" squares with gray. Other squares remain white. */ for (int r = 0; r < rows; r++) for (int c = 0; c < columns; c++) { if (finished[r][c]) { g.setColor(Color.gray); g.fillRect(11 + c*SQUARE_SIZE, 11 + r*SQUARE_SIZE, SQUARE_SIZE - 1, SQUARE_SIZE - 1); } else if (encountered[r][c]) { g.setColor(Color.red); g.fillRect(11 + c*SQUARE_SIZE, 11 + r*SQUARE_SIZE, SQUARE_SIZE - 1, SQUARE_SIZE - 1); } } } // end paintComponent(); } // end class DepthBreadth