Stacks: can be implemented using arrays, LinkedLists, ArrayLists

• Abstract data type
• Hold ordered (not sorted), linear sequences of items
• Linear structure
• Last In First Out
  • You can get an item in your stack, or take an item out of the stack
  • Always take from the top of the stack
  • The last ones that were put in are the first items that are being put out
• You should know if the stack is empty or not, and how many items are in it (the size)
  • where is the top item?
    • should have a method that returns the location of the top item
  • how many items are in the stack vs how many items can the stack hold
  • makeEmpty = makes the entire stack empty
    • can be done by clearing every item in the array one by one
    • the location of the top keeps moving every time
    • can also be done by moving the top item
    • size (number of items) = top + 1
    • makeEmpty = top = -1
  • every time we push (add an item), the top increases by 1

public class Stack{
	private int[] data;
	private int top;

	public Stack(int maxSize){
		data = new int[maxSize];
		top = -1;
	}
	
	public void push(int n){
		//can you add? is there space?
		if(top < data.length-1){
			top++;
			data[top] = n;
		}	
	}

	public int getTop(){
		//returns the item at the top 
		return data[top];
	}

	public int pop(){
		top--;
		return data[top + 1];
	}
	
	public boolean isEmpty(){
		//checks if the array is empty
		if(top == -1){
			return true;
		}
		return false;
	}

	public int getSize(){
		//how many items are in the array 
		return top + 1;
	}

	public void makeEmpty(){
		top = -1;
	}

}

//main
Stack plates = new Stack(20); //making an object called Stack, 20 is the size of the array, not the item number
plates.push(12);
plates.push(231);
plates.push(184);

System.out.println("top: " + plates.getTop());

Queues:

• Implementing a line (e.g a line up at the store)
• The first person who goes in a store in a line is the first person who comes out of the store
• You are not just keeping track of the top, you also need to keep track of what is leaving

Elements leave from the front, and are inserted from the rear

public class Queue{
	public Queue (int maxSize){
		data = new int[maxSize];
		front = -1;
		rear = -1;
	}

	public int getFront(){
		return data[front];
	}
	
	public int dequeue(int n){
		//taking them out of the lineup
		//move the front + 1
		//display the front (dequeued queue)
		//use mod to rotate through 
	}

	public int enqueue(int n){
		rear+=1;
		int location = rear%data.length;
		// adding an item into the queue
		//actually adding something to the queue
		//when we inqueue something, the rear increases by 1
		//increase the rear by 1
		//use mod to rotate through 
		//
	}
	
	public int size(){

	}

	public void makeEmpty(){

	}

}

//main

location = rear % data.length

the size is how many people are in the queue

linked lists

ADS to-do