Made by Mike_Zhang

数据结构与算法主题：

1 Introduction to Stack

Stack (栈) is the simplest and very important data structure.

A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.

The fundamental operations of a stack are push and pop.

[Example]
Like the coin collector in real life:
You are always able to take out the top coin which is the one most recently inserted, and the first coin you put in will be the last one you take out.

coin collector

2 Stack Abstract Data Type

First thing first, what is the Abstract Data Type?

Abstract Data Type (ADT) is an concept based on abstraction of OOP, where abstraction describes a system in a very general way, including naming and explaining their functionality.
Therefore, ADT is a model of a data structure specifying the type of data stored, the operations performed on them, and the types of parameters of the operations.
ADT is treated as an interface in Java, just including method declarations and their parameters, but leaving the method bodies empty, which mean the ADT only know what each operation does, but does not know how it does.
To realize an ADT, we need some concrete date structure to specify how operations work. In Java, this process is realized by a class to implement an interface.

Stack Abstract Data Type specifies the following operations (with examples in coin collector):

push(e): Add (push) an element e to the top of the stack (store a new coin);
pop(): Remove (pop) and return the top element from the stack, or null if the stack is empty (take out a coin);
top(): Return but NOT remove the top element from the stack, or null if the stack is empty (check the coin on top);
size(): Return the number of elements in the stack (check how many coins are there);
isEmpty(): Return a boolean value indicating whether the stack is empty (check whether the collector is empty);

In order to use the Stack ADT in Java, we first need to define the Stack interface.

public interface Stack<E> {
    int size();
    boolean isEmpty();
    void push(E e);
    E pop();
    E top();
}

Then we need to define the concrete Stack class to implement the Stack interface to give each method a body.

Two ways:

Using Array to implement the Stack;
Using LinkedList to implement the Stack.

Before our implementation, we first look at the Stack class offered by Java, which is the java.util.Stack class.

3 java.util.Stack Class

Stack - Java SE 17

Some differences of method between the Stack ADT and the java.util.Stack class:

Stack ADT	`java.util.Stack` Class
`size()`	`size()`
`isEmpty()`	`empty()`
`push(e)`	`push(e)`
`pop()`	`pop()`
`top()`	`peek()`

4 Stack ADT Implementations

4.1 Implement Stack Using Array

Using an array to store the elements in the stack, with fixed size of the array, $N$.
We use a variable $t$ to indicate the top of the stack, and $t = -1$ indicates the stack is empty, as the first inserted element is at index $0$.

Java implementation:

public class ArrayStack<E> implements Stack<E> {
    private static final int SIZE = 100; // Default array size
    private E[] elements; // Using array to store elements in the Stack
    private int t = -1; // Start index of the top
    // Default constructor
    public ArrayStack() { 
        this(SIZE);
    }
    // Constructor with size
    public ArrayStack(int inSize) { 
        elements = (E[]) new Object[inSize];
    }
    // Return the size of the Stack
    public int size() { 
        return t+1;
    }
    // Return true if the Stack is empty
    public boolean isEmpty() { 
        return t == -1;
    }
    // Push an element into the Stack
    public void push(E inElement) { 
        if (size() == elements.length) { // Check whether the Stack is full
            throw new RuntimeException("Stack is full");
        }
        t = t + 1; // Increase the index of the top
        elements[t] = inElement; // Put the element into the Stack
    }
    // Pop an element from the Stack
    public E pop() { 
        if (isEmpty()) {
            return null;
        }
        E outElement = elements[t]; // Get the element from the top
        elements[t] = null; // Set the element to null for garbage collection
        t = t - 1; // Decrease the index of the top
        return outElement;
    }
    // Return the element from the top
    public E top() {
        if (isEmpty()) {
            return null;
        }
        return elements[t]; // Get the element from the top
    }

    public String toString() {
        String outString = "bottom -> ";
        for (int i = 0; i <= t; i++) {
            outString = outString + elements[i] + " ";
        }
        outString = outString + "<- top";
        return outString;
    }
}

Test:

public static void main(String[] args) {
        Stack<Integer> stack = new ArrayStack<Integer>();
        System.out.println(stack.isEmpty()); // true
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.size()); // 3
        System.out.println(stack.toString()); // bottom -> 1 2 3 <- top
        System.out.println(stack.pop()); // 3
        System.out.println(stack.toString()); // bottom -> 1 2 <- top
        System.out.println(stack.top()); // 2
    }

Result:

true
3
bottom -> 1 2 3 <- top
3
bottom -> 1 2 <- top
2

Advantages of using an array to implement the Stack:

Simple and efficient;
- Each method just includes some primitive operations, which is easy to understand and implement.
- Running time of each method:

Method	Running time
`size()`	$O(1)$
`isEmpty()`	$O(1)$
`push(e)`	$O(1)$
`pop()`	$O(1)$
`top()`	$O(1)$

Therefore, using Array to implement the Stack is efficient, for each method runs in constant time, $O(1)$ time.

Drawbacks of using an array to implement the Stack:

It is based on a fixed size of the array, $N$, which means the size of the Stack is fixed, limited and unchangeable, while the the actual size of the Stack is dynamic.
- If we needs much less space than the reserved size, memory is wasted.
- If we try to push an element into the Stack when the array storage is full, the program will throw an exception, and we cannot push any more elements into the Stack.

To solve the above problem, we can use a LinkedList to implement the Stack.

4.2 Implement Stack Using Linked List

Using a singly linked list to store the elements in the stack;
The memory usage is always associated with the actual number of elements in the Stack, without a capacity limitation;
According to the stack ADT, we can adapt our SinglyLinkedList class to define a new LinkedStack class:

Methods in Stack	Method in `SingleLinkedList`
`size()`	`getSize()`
`isEmpty()`	`isEmpty()`
`push(e)`	`addAtHead(e)`
`pop()`	`deleteAtHead()`
`top()`	`getHead()`

Java implementation:

(Import the SingleLinkedList class from the post-Linked List Introduction - 链表简介)

public class LinkedStack<E> implements Stack<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<E>();
    public LinkedStack() {}
    public int size() {
        return list.getSize();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void push(E element) {
        list.addAtHead(element);
    }
    public E pop() {
        return list.deleteAtHead();
    }
    public E top() {
        return list.getHead();
    }
    public String toString() {
        return "top ->"+list.toString()+"<- bottom";
    } 
}

Test:

public static void main(String[] args) {
        Stack<Integer> stack = new LinkedStack<Integer>();
        System.out.println(stack.isEmpty()); // true
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.size()); // 3
        System.out.println(stack.toString()); // top ->3 2 1 <- bottom
        System.out.println(stack.pop()); // 3
        System.out.println(stack.toString()); // top ->2 1 <- bottom
        System.out.println(stack.top()); // 2
    }

Result:

true
3
top ->3 2 1 <- bottom
3
top ->2 1 <- bottom
2

5 Stack Applications

List two simple applications of Stack.

5.1 Reverse a Array

Based on the FILO (First In Last Out) principle, we can reverse an array using Stack.

First we push all the elements into the Stack in the default order in the array;
Then we pop them out one by one to get the reversed array.

Java implementation:

public static <E> void reverse(E[] inArr) {
    Stack<E> stack = new ArrayStack<E>();
    for (int i = 0; i < inArr.length; i++) {
        stack.push(inArr[i]);
    }
    for (int i = 0; i < inArr.length; i++) {
        inArr[i] = stack.pop();
    }
}

Test:

public static void main(String[] args) {
    Integer[] arr = {1, 2, 3, 4, 5};
    System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]
    reverse(arr);
    System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]
}

Result:

1 2	`[1, 2, 3, 4, 5] [5, 4, 3, 2, 1]`

5.2 Matching Parentheses

Giving an arithmetic expressions, we need to check whether their delimiting symbols match up correctly. We can use a stack to check the matching by pushing and popping the delimiting symbols.

Pairs:

Parentheses: “(” and “)”
Braces: “{” and “}”
Brackets: “[” and “]”

Examples:

valid: ()
valid: [([]){()}]
invalid: [([{()}]
invalid: {[(}

Simple algorithm:

1. Traverse the expression from left to right;
1. If we meet a left delimiter(e.g. ([{), we push it into the stack;
1. Else if we meet a right delimiter(e.g. )]}), we pop an element from the stack,
1. then check whether the popped element and the met delimiter match up(e.g. (),[],{});
The expression is invalid, if:
- a. When we meet a right delimiter, the stack is empty,;
- b. These two delimiters do NOT match up;
- c. After we traversing the whole expression, the stack is NOT empty.
The expression is valid, if:
- d. After we traversing the whole expression, the stack is empty.

Java implementation:

public static boolean isMatched(String expression) {
        Stack<Character> stack = new LinkedStack<Character>();
        String opening = "([{";
        String closing = ")]}";
        for (int i = 0; i < expression.length(); i++) { // step 1
            char c = expression.charAt(i);
            if (opening.indexOf(c) != -1) {
                stack.push(c); // step 2
            }
            else if (closing.indexOf(c) != -1) {
                if (stack.isEmpty()) { // case a
                    return false;
                }
                // step 3 & 4
                else if (closing.indexOf(c) != opening.indexOf(stack.pop())) { 
                    return false; // case b
                }
            }
        }
        return stack.isEmpty(); // case c & d
}

Test:

public static void main(String[] args) {
    System.out.println(isMatched("()")); // true
    System.out.println(isMatched("[([]){()}]")); // true
    System.out.println(isMatched("[([{()}]")); // false
    System.out.println(isMatched("{[(}")); // false
}

Result:

true
true
false
false

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

写在最后

Stack 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持

Data Structure and Algorithm > Data Structure > Stack

#Java #数据结构 #Stack

Stack Introduction - 栈简介

https://ultrafish.io/post/stack-introduction/

Author

Mike_Zhang

Posted on

May 18, 2022

Licensed under

Sorting Algorithm Introduction - 排序算法简介 Previous

Algorithm Analysis Introduction - 算法分析简介 Next