栈 Stack

Algorithm Notes

---

Jing | 15 Apr 2021

报告错误

如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：

1. 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
2. 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库

你使用哪种语言？我们会根据你选择的语言显示对应的代码示例

Python

Java

前置条件

在学习这个知识点前，你应该先学习……

• 理论基础：时间复杂度 Time Complexity

栈

栈(stack)是一种用于收集数据的线性数据结构，主要有两个操作

• 放入(push): 将元素放进集合
• 取出(pop) : 将最后放入的元素取出

因为Stack的两个操作，我们也可以将Stack记为LIFO(last in, first out)，也叫后进先出。

在栈(stack)中，还有几种常见的方法：

• peek: 查看当前的栈最后的一个元素
• isEmpty: 判断当前栈是否是空的

代码实现

class Stack:
    def __init__( self ):
        self.stack = []

    def push( self, item ):
        self.stack.append( item )
        return self.stack

    def pop( self ):
        if self.isempty(): return -1
        self.stack.pop()
        return self.stack

    def peek(self):
        return self.stack[ -1 ]

    def isempty(self):
        if len( self.stack ) == 0: return True
        return False


import java.util.ArrayList;

public class Stack {
    ArrayList<Integer> stack = new ArrayList<Integer>();

    public void push( int item ){
        stack.add( item );
    }

    public int pop(){
        if ( ! stack.isEmpty() ) {
            return stack.remove(stack.size() - 1);
        }
        return -1;
    }

    public int peek(){
        return stack.get( -1 );
    }

    public boolean isempty(){
        if ( stack.size() == 0 ) {
            return true;
        }
        return false;
    }
}

时间复杂度 Time Complexity

栈的push 和 pop 方法的时间复杂度都是 $O(1)$，因为每次将一个 object 放入栈中的时候，我们只需要在 ArrayList 末尾添加一个元素即可。每次从栈中取出一个 object，我们只是读取 ArrayList 末尾的元素并删除而已。

评论区