后入先出的数据结构

---

在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

 

示例 - 栈

---

1. 入栈：你可以单击下面的 Push 按钮查看如何将新元素 6 添加到栈中。

2. 退栈：你可以单击下面的 Pop 按钮查看当你从栈中弹出一个元素时将移除哪个元素。

    Push                      Pop

 

实现 - 栈

---

栈的实现比队列容易。动态数组足以实现堆栈结构。这里我们提供了一个简单的实现供你参考：

// "static void main" must be defined in a public class.
class MyStack {
    private List<Integer> data;               // store elements
    public MyStack() {
        data = new ArrayList<>();
    }
    /** Insert an element into the stack. */
    public void push(int x) {
        data.add(x);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /** Get the top item from the queue. */
    public int top() {
        return data.get(data.size() - 1);
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean pop() {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
};

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if (!s.isEmpty()) {
                System.out.println(s.top());
            }
            System.out.println(s.pop());
        }
    }
}

 

栈 - 用法

---

大多数流行的语言都提供了内置的栈库，因此你不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，你应该能够从栈中获得顶部元素。下面是一些供你参考的代码示例：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a stack.
        Stack<Integer> s = new Stack<>();
        // 2. Push new element.
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);
        // 3. Check if stack is empty.
        if (s.empty() == true) {
            System.out.println("Stack is empty!");
            return;
        }
        // 4. Pop an element.
        s.pop();
        // 5. Get the top element.
        System.out.println("The top element is: " + s.peek());
        // 6. Get the size of the stack.
        System.out.println("The size is: " + s.size());
    }
}

 

从现在开始，我们可以使用内置的栈库来更方便地解决问题。 让我们从一个有趣的问题（最小栈）开始，帮助你复习有用的操作。 然后我们将看一些经典的栈问题。 当你想首先处理最后一个元素时，栈将是最合适的数据结构。

最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

 

代码如下:

public class MinStack {
    ArrayList<Integer> minstack ;
    int Top=-1;
    public MinStack() {
        minstack= new ArrayList<>();

    }

    public void push(int x) {
        minstack.add(x);
        Top++;

    }

    public void pop() {
        minstack.remove(Top);
        Top--;

    }

    public int top() {
        return  minstack.get(Top);

    }

    public int getMin() {
        int min=minstack.get(0);
        for(int i:minstack){
            if(i<min){
                min=i;
            }
        }
        return min;

    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println( minStack.getMin());
    }
}