Stacks and Queues

Stacks and QueuesWelcome to my tutorial on Java Stacks and Queues. The data structures most are used to such as Arrays, linked lists, trees, etc. are best for data that represents real objects. Stacks and Queues are instead used to complete a task and are soon after discarded.

A major difference is that stacks and queues allow only a single item to be added or removed at a time. Stacks then provide access to the last item in, while queues provide access to the first item in. The video and code below will cover everything.

If you like videos like this, it helps to tell Google+

Code From the Video

TheStack.java

// Arrays, linked lists, trees, etc. are best for
// data that represents real objects.

// Stacks & Queues are instead used to complete a 
// task and are soon after discarded.

// Stacks & Queues
// 1. Allow only a single item to be added or removed at a time
// 2. Stacks allow access to the last item inserted (LIFO)
// 3. Queues allow access to the first item inserted (FIFO)

import java.util.Arrays;

public class TheStack {
	
	private String[] stackArray;
	private int stackSize;
	
	// Sets stack as empty
	
	private int topOfStack = -1;
	
	TheStack(int size){
		
		stackSize = size;
		
		stackArray = new String[size];
		
		// Assigns the value of -1 to every value in the array
		// so I control what gets printed to screen
		
		Arrays.fill(stackArray, "-1");
		
	}

	public void push(String input){
		
		if(topOfStack+1 < stackSize){
			
			topOfStack++;
			
			stackArray[topOfStack] = input;
			
		} else System.out.println("Sorry But the Stack is Full");
		
		displayTheStack();
		
		System.out.println("PUSH " + input + " Was Added to the Stack\n");
		
	}
	
	public String pop(){
		
		if(topOfStack >= 0){
			
			displayTheStack();
			
			System.out.println("POP " + stackArray[topOfStack] + " Was Removed From the Stack\n");
			
			// Just like in memory an item isn't deleted, but instead is just not available
			
			stackArray[topOfStack] = "-1"; // Assigns -1 so the value won't appear
			
			return stackArray[topOfStack--];
	
			
		} else {
			
			displayTheStack();
			
			System.out.println("Sorry But the Stack is Empty");
			
			return "-1";
		}
		
		
	}
	
	public String peek(){
		
		displayTheStack();
		
		System.out.println("PEEK " + stackArray[topOfStack] + " Is at the Top of the Stack\n");
		
		return stackArray[topOfStack];
		
	}
	
	public void pushMany(String multipleValues){
		
		String[] tempString = multipleValues.split(" ");
		
		for(int i = 0; i < tempString.length; i++){
			
			push(tempString[i]);
			
		}
		
	}
	
	public void popAll(){
		
		for(int i = topOfStack; i >= 0; i--){
			
			pop();
			
		}
		
	}
	
	public void popDisplayAll(){
		
		String theReverse = "";
		
		for(int i = topOfStack; i >= 0; i--){
			
			theReverse += stackArray[i];
			
		}
		
		System.out.println("The Reverse: " + theReverse);
		
		popAll();
		
	}
	
	public void displayTheStack(){
		
			for(int n = 0; n < 61; n++)System.out.print("-");
			
			System.out.println();
			
			for(int n = 0; n < stackSize; n++){
				
				System.out.format("| %2s "+ " ", n);
				
			}
			
			System.out.println("|");
			
			for(int n = 0; n < 61; n++)System.out.print("-");
			
			System.out.println();
			
			for(int n = 0; n < stackSize; n++){
				
				
				
				if(stackArray[n].equals("-1")) System.out.print("|     ");
				
				else System.out.print(String.format("| %2s "+ " ", stackArray[n]));
				
			}
			
			System.out.println("|");
			
			for(int n = 0; n < 61; n++)System.out.print("-");
			
			System.out.println();
		
	}
	
	public static void main(String[] args){
		
		TheStack theStack = new TheStack(10);
		
		theStack.push("10");
		theStack.push("17");
		theStack.push("13");
		
		// Look at the top value on the stack
		
		theStack.peek();
		
		// Remove values from the stack (LIFO)
		
		theStack.pop();
		theStack.pop();
		theStack.pop();
		
		// Add many to the stack
		
		theStack.pushMany("R E D R U M");
		
		// Remove all from the stack
		
		// theStack.popAll();
		
		// Remove all from the stack and print them
		
		theStack.popDisplayAll();
		
		theStack.displayTheStack();
		
		
	}
	
}

TheQueue.java

import java.util.Arrays;


public class TheQueue {
	
	private String[] queueArray;
	private int queueSize;
	
	// Sets stack as empty
	
	private int front, numberOfItems, rear = 0;
	
	TheQueue(int size){
		
		queueSize = size;
		
		queueArray = new String[size];
		
		// Assigns the value of -1 to every value in the array
		// so I control what gets printed to screen
				
		Arrays.fill(queueArray, "-1");
		
	}
	
	public void insert(String input){
		
		if(numberOfItems + 1 <= queueSize){
		
			queueArray[rear] = input;
			
			rear++;
		
			numberOfItems++;
			
			System.out.println("INSERT " + input + " Was Added to the Stack\n");
		
		} else {
			
			System.out.println("Sorry But the Queue is Full");
			
		}
		
	}
	
	// This priority insert will add items in order from high to low
	
	public void priorityInsert(String input){
		
		int i;
		
		if(numberOfItems == 0){
			
			insert(input);
			
		} else {
			
			for(i = numberOfItems-1; i >= 0; i--){
				
				if(Integer.parseInt(input) > Integer.parseInt(queueArray[i])){
					
					queueArray[i+1] = queueArray[i];
					
				} else break; // Done shifting items in queue
				
			}
			
			queueArray[i+1] = input;
			
			rear++;
			
			numberOfItems++;
			
		}
		
	}
	
	public void remove(){
		
		if(numberOfItems > 0){
			
			System.out.println("REMOVE " + queueArray[front] + " Was Removed From the Queue\n");
			
			// Just like in memory an item isn't deleted, but instead is just not available
			
			queueArray[front] = "-1";
			
			front++;
		
			numberOfItems--;
		
		} else {
			
			System.out.println("Sorry But the Queue is Empty");
			
			
		}
		
	}
	
	public void peek(){
		
		System.out.println("The First Element is " + queueArray[front]);
		
	}
	
	public void displayTheQueue(){
		
		for(int n = 0; n < 61; n++)System.out.print("-");
		
		System.out.println();
		
		for(int n = 0; n < queueSize; n++){
			
			System.out.format("| %2s "+ " ", n);
			
		}
		
		System.out.println("|");
		
		for(int n = 0; n < 61; n++)System.out.print("-");
		
		System.out.println();
		
		for(int n = 0; n < queueSize; n++){
			
			
			if(queueArray[n].equals("-1")) System.out.print("|     ");
			
			else System.out.print(String.format("| %2s "+ " ", queueArray[n]));
			
		}
		
		System.out.println("|");
		
		for(int n = 0; n < 61; n++)System.out.print("-");
		
		System.out.println();
		
		// Number of spaces to put before the F
		
		int spacesBeforeFront = 3*(2*(front+1)-1);
		
		for(int k = 1; k < spacesBeforeFront; k++)System.out.print(" ");
		
		System.out.print("F");
		
		// Number of spaces to put before the R
		
		int spacesBeforeRear = (2*(3*rear)-1) - (spacesBeforeFront);
		
		for(int l = 0; l < spacesBeforeRear; l++)System.out.print(" ");
		
		System.out.print("R");
		
		System.out.println("\n");
	
}
	
	public static void main(String[] args){
		
		TheQueue theQueue = new TheQueue(10);
		
		theQueue.priorityInsert("16");
		
		theQueue.priorityInsert("25");
		
		theQueue.priorityInsert("10");
		
		/*
		theQueue.insert("10");
		
		theQueue.displayTheQueue();
		
		theQueue.insert("15");
		
		theQueue.displayTheQueue();
		
		theQueue.insert("25");
		
		theQueue.displayTheQueue();
		
		theQueue.insert("25");
		
		theQueue.displayTheQueue();
		
		theQueue.insert("25");
		*/
		
		theQueue.displayTheQueue();
		
		theQueue.remove();
		
		theQueue.displayTheQueue();
		
		theQueue.remove();
		
		theQueue.displayTheQueue();
		
		theQueue.peek();
		
	}

}

21 Responses to “Stacks and Queues”

  1. Ramini Bronze says:

    Been watching your tutorial starting from linked list to stacks and queues since July 28, 2013. And still having a hard time understanding them a bit.

    • Derek Banas says:

      What is confusing you? I’ll gladly try to help

      • CaptainStupid says:

        For the stack code, I think you should move line 48 to line 43, then add “\n” in front of “Sorry” for line 44.

        if you fill the stack, then pushing another item wont add anything to the stack, yet your code will say it was added.

  2. samneo says:

    Hi Derek, Thank you very much for you videos. I like your way of teaching, it’s a good pace and straight to the point. My question is where exactly I can use stack concept in javascript? Because I can achieve same results using JS builtin arrays also.

  3. Alejandro Chavez says:

    I believe there may be an error with your insert. Your if simply based on numberOfItems with no regard for what the front index of the array is. There if you fill up the queue, remove some, and then add more I don’t think it will work. Your numberOfItems will be < queueSize and your rear will then go out of bounds.

    • tarun says:

      my version of insert
      public void insert (String value){
      System.out.println(“Display of queue before entering “+value);
      displayTheQueue();
      if (numberOfItems+1<queueSize){
      if (rear==queueSize)rear=0;
      queueArray[rear]=value;
      rear++;
      numberOfItems++;
      }
      else{System.out.println("Sorry queue is full");}
      System.out.println("Status of queue after entering "+value);
      displayTheQueue();
      }

  4. Ivan Kavuma says:

    I love your toturials.
    But In public void priorityInsert(String input)
    there is no check to see that the queue is full.
    Am I not seeing it?

  5. Sowjhanya says:

    Hello Derek,

    Great video tutorials! Easy to understand.

    I just came across this while implementing Stack. Withing the Stack class’s peek(), lets say I call this method even before pushing elements onto the Stack. Wouldn’t peek throw an ArrayIndexOutOfBoundException? Hence we need to check for topOfArray >=0 within the peek method.

    Please correct me if otherwise.

    Thanks,
    Sowjhanya

    • Derek Banas says:

      Hello Sowjhanya,

      Yes you are correct that I should always check for a values existence before calling. I wrote this largely out of my head and it wasn’t optimized. I hope that makes sense.

  6. tarun says:

    Hi, Awesomely explained but there is a problem in the pop() of stack. It will always return -1. Instead you should first store the value in a different string and then return it. Please see the modified code below.

    Please confirm if my understanding is correct.

    public String pop (){
    System.out.println(“Display stack before removal”);
    displayTheStack();
    String str;
    if (topOfStack >0){
    System.out.println(“Value to be deleted = “+stackArray[topOfStack]);
    str=stackArray[topOfStack];
    stackArray[topOfStack] = “-1″;
    topOfStack–;
    }
    else{
    System.out.println(” Stack is empty”);
    str=”-1″;
    }
    System.out.println(“Stack after removal “);
    displayTheStack();
    System.out.println(“topOfStack = “+topOfStack);
    System.out.println(“str = “+str);
    return str;
    }

  7. Iwan B says:

    Great video. I thought I should mention though that after ten items are inserted into this array, and deleted then we simply cannot insert anything anymore.

    A quick way to get around this is to do queueArray[rear % queueSize] or queueArray[front%queueSize]. Now rear and front will always be within the queue range because of the modulus operation.

    A problem with this approach is if you ever inserted/deleted 2^32 (Int max size) of items then front will suddenly become -2^32.

    So to get around this problem we modify rear and front directly.

    rear = (++rear % queueSize);

    front = (++front % queueSize);

    Now we can add as many items as we want, and only worry about the max size of the array.

  8. Pavitra Kansara says:

    Great piece of work Derek !
    Kudos…

  9. Greg says:

    Do you have any implementation of deques data structures on your website? 🙂

Leave a Reply

Your email address will not be published.

Google+