栈:(先进后出)
一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:
栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:
栈的删除操作叫做出栈。出数据在栈顶。
单链表尾插法每次得找到末尾才能插入,不占优势。下面介绍的都由数组实现。
实现方式 | 入栈出栈时间复杂度 |
---|---|
数组 | O(1) |
单链表 | 头插法 :O(1)尾插法:O(N) |
向栈中存放元素:stack.push();
获取栈顶元素:stack.peek();
删除栈顶元素(返回值为删除的元素):stack.pop();
public static void main2(String[] args) { Stack<Integer> stack = new Stack<>();//创建一个栈 //向栈中存放1,2,3个元素 stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.peek());//获取栈顶元素 但是不删除 结果为3 System.out.println(stack.pop());//弹出栈顶元素 删除 结果为3 System.out.println(stack.peek());//获取栈顶元素 但是不删除 结果为2 System.out.println(stack.empty());//将栈中元素置为空 System.out.println(stack.isEmpty());//判断是否为空 }
1.开辟一个栈的空间
2.push往栈中存放元素要判断栈满没满,满了进行扩容,没满则存放到数组最后的位置。
3.pop删除栈顶元素要判断栈是否为空
public class MyStack { public int[] elem;//开辟一个栈的空间 public int usedSize;//栈实际用的长度 public MyStack() { this.elem = new int[10];//设置栈的空间为10个元素的空间 } //push往栈中存放元素要判断栈满没满 public boolean isFull() { //数据个数==长度了 if (this.usedSize == this.elem.length) { return true; } return false; } public void push(int item) { if (isFull()) { //满了进行扩容 this.elem = Arrays.copyOf(this.elem, 2 * elem.length); } //没满,存放到数组最后的位置 this.elem[this.usedSize] = item; this.usedSize++; } //pop删除栈顶元素要判断栈是否为空 public boolean empty(){ //数据个数为空的时候 return this.usedSize==0; } public int pop() throws RuntimeException { if (empty()) { throw new RuntimeException("栈空了"); } int val=this.elem[this.usedSize-1]; this.usedSize--; return val; } //获取栈顶元素 public int peek(){ if(empty()){ throw new RuntimeException("栈空了"); } return this.elem[this.usedSize-1]; } public static void main(String[] args) { MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.push(3); System.out.println(myStack.peek());//获取栈顶元素 但是不删除 结果为3 System.out.println(myStack.pop());//弹出栈顶元素 删除 结果为3 System.out.println(myStack.peek());//获取栈顶元素 但是不删除 结果为2 System.out.println(myStack.empty());//结果为false System.out.println(myStack.pop());//2 System.out.println(myStack.pop());//1 System.out.println(myStack.pop());//证明为空报异常 } }