If a student Stacks up

A stack is a collection of objects that are inserted and removed according to the last-in, First-out (LIFO) principle. Java has a java.util.Stack class, but the Java documentation recommends not using this class in favor of using a Deque (because a Deque can Queue and Stack?). .

Stack Interface

public interface Stack<E> {
	int size(a);    // return the number of elements in the stack 
	boolean isEmpty(a); 

	void push(E e); 
	E top(a);      // Returns, but does not remove, the element at the top of the stack
	E pop(a);      // Removes and returns the top element from the stack
}
Copy the code

Array-based Stack Implementation

public class ArrayStack<E> implements Stack<E> {
	public static final int CAPACITY = 1000; 
	private E[] data; 
	private int t = -1;        // index of the top element in stack
	public ArrayStack(a) { this(CAPACITY); } 
	public ArrayStack(int capacity) { 
		data = (E[]) new Object[capacity]; 
	}
	public int size(a) { return (t + 1); } 
	public boolean isEmpty(a) { return (t == -1); } 
	public void push(E e) throws IllegalStateException {
		if(size() == data.length) throw new IllegalStateException("Stack is full"); 
		data[++t] = e;      // increment t before storing new item
	}
	public E top(a) {
		if(isEmpty()) return null; 
		return data[t]; 
	}
	public E pop(a) {
		if(isEmpty()) return null; 
		E answer = data[t]; 
		data[t] = null;       // deference to help garbage collection
		t--; 
		returnanswer; }}Copy the code

Implementing a Stack with a Singly Linked List

In the implementation, the top of the stack is at the front of the list.

public class LinkedStack<E> implements Stack<E> {
	private SinglyLinkedList<E> list = new SinglyLinkedList<>(); 
	public LinkedStack(a) {}      // new stack relies on the initially empty list
	public int size(a) { return list.size(); } 
	public boolean isEmpty(a) { return list.isEmpty(); } 
	public void push(E element) { list.addFirst(element); } 
	public E top(a) { return list.first(); } 
	public E top(a) { returnlist.removeFirst(); }}Copy the code

Reversing an Array Using a Stack

public class ReverseArray(a) {
	// A generic method for reversing an array 
	public static <E> void reverse(E[] a) {
		Stack<E> buffer = new ArrayStack<>(a.length); 
		for(int i = 0; i < a.length; i++) buffer.push(a[i]); 
		for(int j = 0; j < a.length; j++) a[i] = buffer.pop(); 
	}

	public static void main(String[] args) {
		Integer[] a = {4.8.15.16.23.42};       // Autoboxing
		String[] s = {"Jack"."Kate"."Hurley"."Jin"."Michael"}; 
		System.out.println("a = " + Arrays.toString(a)); 
		System.out.println("s = " + Arrays.toString(s)); 
		System.out.println("Reversing..."); 
		reverse(a); 
		reverse(s); 
		System.out.println("a = " + Arrays.toString(a)); 
		System.out.println("s = "+ Arrays.toString(s)); }}Copy the code