The stack

An overview of the

Stack is a relatively simple data structure, often described in one sentence, last in first out. The stack itself is a linear table, but there is only one slot in the table that allows data in and out.

Common operations on the stack include PUSH and POP, pushing and pushing data in and out. Access to the top of the stack, determine whether the stack is empty, determine the size of the stack, and so on. Due to the last-in-first-out feature of the stack, it can often be used as a temporary container for data, and the order of data can be adjusted and adjusted. Combining with other data structures, it can obtain a lot of flexible processing.

Stack

Stack is the stack, its characteristics are: advanced after out. In the Java toolkit, stack is inherited from vector, and since vector is implemented in arrays, that means stack is implemented in arrays, not lists. Of course, we can also use the LinkedList as a stack. Stack inheritance relationship

package java.util;

public class Stack<E> extends Vector<E> {
    // 版本ID。这个用于版本升级控制，这里不须理会！
    private static final long serialVersionUID = 1224463164541339165L;
// 构造函数
public Stack() {
}

// push函数：将元素存入栈顶
public E push(E item) {
    // 将元素存入栈顶。
    // addElement()的实现在Vector.java中
    addElement(item);
    return item;
}

// pop函数：返回栈顶元素，并将其从栈中删除
public synchronized E pop() {
    E   obj;
    int  len = size();
    obj = peek();
    // 删除栈顶元素，removeElementAt()的实现在Vector.java中
    removeElementAt(len - 1);
    return obj;
}

// peek函数：返回栈顶元素，不执行删除操作
public synchronized E peek() {
    int  len = size();
    if (len == 0)
        throw new EmptyStackException();
    // 返回栈顶元素，elementAt()具体实现在Vector.java中
    return elementAt(len - 1);
}

// 栈是否为空
public boolean empty() {
    return size() == 0;
}

// 查找“元素o”在栈中的位置：由栈底向栈顶方向数
public synchronized int search(Object o) {
    // 获取元素索引，elementAt()具体实现在Vector.java中
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}
}
Copy the code

The queue

Queue is the brother structure of stack, and corresponding to the last in, first out of stack, queue is a kind of first in, first out data structure, meaning that the data storage of queue is just like queuing, the data stored first is pushed out first, often with the stack together, can exert the maximum strength.