Stack

Stack

• A stack is an abstract data type that serves as a collection of elements.
• Last in First out(LIFO).
• Push, which adds an element to the collection.
• Pop, which removes the most recently added element that was not yet removed.

(Source: Stack (abstract data type) - Wikipedia)

Implements a Stack:

class StackX {
    private int maxSize; // size of stack array 
    private long[] stackArray; 
    private int top; // top of stack
	
	// constructor
	public StackX(int s) {
		maxSize = s; // set array size 
		stackArray = new long[maxSize]; // create array 
		top = -1; // no items yet
	}
	
	// put item on top of stack
	public void push(long j) {
		stackArray[++top] = j; // increment top, insert item
	}
	
	// take item from top of stack
	public long pop() {
		return stackArray[top--]; // access item, decrement top
	}
	
	// peek at top of stack
	public long peek() {
		return stackArray[top];
	}
	
	// true if stack is empty
	public boolean isEmpty() {
		return (top == -1);
	}
	
	// true if stack is full
	public boolean isFull() {
		return (top == maxSize-1);
	}
}

---

Stack Example 1: Reversing a Word:

class Reverser {
    private String input; // input string 
    private String output; // output string
    
	 // constructor
	public Reverser(String in) { 
		input = in; 
	}
	
	// reverse the string
	public String doRev() {
		int stackSize = input.length(); // get max stack size 
		StackX theStack = new StackX(stackSize); // make stack

		for(int j=0; j < input.length(); j++) {
			char ch = input.charAt(j); // get a char from input
			theStack.push(ch); // push it
		}
		
		output = “”;

		while(!theStack.isEmpty()) {
			char ch = theStack.pop(); // pop a char
			output = output + ch; // append to output
		}
		return output;
	}
}

Stack Example 2: Valid Parentheses (LeetCode - 20):

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

class Solution {
    public boolean isValid(String s) {

        Map<Character,Character> map = new HashMap<>();
        Stack<Character> stack = new Stack<>();

        map.put('(',')');
        map.put('{','}');
        map.put('[',']');

        if(s.length() == 1) {
            return false;
        }

        for(int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))) {
                stack.push(map.get(s.charAt(i)));
            } else {
                if(stack.isEmpty() || stack.pop() != s.charAt(i)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}