数据结构（三）：栈

佚名 6年前 (2020-03-30) 算法 837人围观抢沙发百度已收录

一、概述

栈（Stack），也叫堆栈。但是不能称为堆，堆是另外一种数据结构
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
FILO栈遵循先进后出的原则（First In Last Out）
基本操作有：入栈（压栈）、出栈（退栈）
入栈和出栈都是针对栈顶的操作

二、结构示意图

依次将a、b、c元素压进一个空栈中：
将上述栈中的元素一个一个出栈
由以上两图我们可以看出来，栈是遵循FILO（先进后出）的原则：a元素是最先进栈的而是最后出栈的，c元素是最后进栈的而是最先出栈的。

三、代码示例

我们这里以java代码为例，使用java官方提供的函数库里面的栈实现

　　@Test
    public void test3(){
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);//往栈中添加一个元素
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack.peek());
        stack.pop();//移除栈中的一个元素
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());
        stack.pop();
        System.out.println(stack.peek());
        stack.pop();
    }

其中peek()方法是获取栈的末尾元素，也就是栈顶的那个元素
代码运行效果如下图：

四、自己用代码实现一个简单的栈

接下来我们使用数组来简单的实现一下栈结构

package com.zhurouwangzi.entity;

public class MyStack {
    public MyStack(){
        element = new int[20];
        size = 0;
    }
    private int[] element;
    private int size;

    public int push(int item){
        element[size] = item;
        size++;
        return item;
    }

    public int pop(){
        int popData = element[size-1];
        int[] newEle = new int[size-1];
        System.arraycopy(element, 0, newEle, 0, size-1);
        element = newEle;
        size--;
        return popData;
    }

    public int peek(){
        return element[size-1];
    }

    public int getSize(){
        return size;
    }
}

测试自定义的栈

@Test
    public void test3(){
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        System.out.println(myStack.peek());
        myStack.pop();//移除栈中的一个元素
        System.out.println(myStack.peek());
        myStack.pop();
        System.out.println(myStack.peek());
        myStack.pop();
        System.out.println(myStack.peek());
        myStack.pop();
        System.out.println(myStack.peek());
        myStack.pop();
    }