数据结构入门教程-栈

上节我们了解了双向链表的基本用法，本节我们来了解下数据结构的另外一种栈结构，首先我们来了解下什么是栈吧！

栈的介绍

• 首先我们的栈是一个先入后出的有序列表。
• 其次栈限制了线性表的元素的插入和删除只能在同一端进行的特殊有序线性表，其中允许插入和删除的一端为栈顶（TOP），另外一端为固定的一端，称为栈底
• 从上述的描述中，我们得知最先入栈的元素肯定在栈底，最后放入的元素在栈顶，删除元素时恰恰相反。最后入栈的元素最先被删除，最先放入的元素最后被删除
• 放入元素的过程我们称为入栈(Push),删除元素的过程我们称为出栈（pop）

上述就是对栈这种数据结构简单的介绍,既然我们提到了入栈和出栈的操作，我们通过如下图来亲切的感受一把Push和Pop的过程，如图所示：

元素入栈.png 出栈.png

上面你的图分别很形象的描述了入栈和出栈的操作，接下来通过下图来分别对入栈和出栈的过程进行思路分析：

入栈思路分析

利用数组模拟入栈出栈操作.png

正如图中一样我们利用数组的特性来实现入栈操作，简单的对图中涉及到的参数简单的介绍下：

• 首先MaxTop：表示的是当前数组的存放数据的最大容量
• Top:表示我们的栈顶，当栈为空时，默认值为-1
• Stack：表示我们当前的数组，真正用来保存数据的

当有数据入栈时：

• 我们只需要做如下的操作，先让top++,其次是stack[top] = data (data就是入栈的数据)

这就是入栈的操作，接着我们来看看出栈的过程

• 首先定义一个临时的变量value来保存我们的栈顶元素，即value= stack[top].
• 接着让栈顶top往下移动即top--
• 最后返回value即可

知道了入栈和出栈的思路，接着我们用代码来实现：

代码实现

• 先定义一个数组（模拟栈）

//定义栈结构类
class ArrayStack{
private int maxSize; //表示栈的最大容量
private int[] stack; //stack实际用来保存数据的
private int top = -1; //top表示栈顶，初始值为-1，表示此时栈中是没有数据的

public ArrayStack(int maxSize){
    this.maxSize = maxSize;
    stack = new int[this.maxSize];
}

• 栈的限制条件代码

//栈满的条件
public boolean isFull(){
    return top == maxSize -1;
}
//栈空的条件
public boolean isEmpty(){
    return top == -1;
}

• 入栈代码

 //入栈操作
public void push(int element){
    if (isFull()){
        throw new ArrayIndexOutOfBoundsException("栈已经满了~");
    }
    top ++;
    stack[top] = element;
}

• 出栈代码

 //出栈操作
public int pop(){
    if (isEmpty()){
        throw new RuntimeException("栈空~");
    }
    int element = stack[top];
    top --;
    return element;
}

• 打印栈的代码

//打印操作
public void print(){
    if (isEmpty()){
        System.out.println("栈空~");
        return;
    }
    for (int i = top; i >= 0 ; i--) {

        System.out.printf("stack[%d]=%d\n",i,stack[i]);
    }
}

上述就是栈数据结构的基本操作的代码演示，接着我们来看测试代码：

/**
 * 数据结构-栈（利用数组特性来实现）
 */
public class ArrayStackCase {
public static void main(String[] args) {

    //测试
    ArrayStack arrayStack = new ArrayStack(5);
    arrayStack.push(10);
    arrayStack.push(20);
    arrayStack.push(30);
    arrayStack.push(40);
    arrayStack.push(50);
    arrayStack.print();
    System.out.println("出栈测试=============");
    int element = arrayStack.pop();
    System.out.println("出栈的元素为："+element);
    arrayStack.print();
    int element1 = arrayStack.pop();
    System.out.println("出栈的元素为："+element1);
    arrayStack.print();
    int element2 = arrayStack.pop();
    System.out.println("出栈的元素为："+element2);
    arrayStack.print();
}}

测试结果如图所示：

栈的测试.png

从我们的测试结果中来看，我们完成了栈的入栈和出栈操作，其实栈的用途还是很多的比如：回溯历史数据操作，就可以利用栈的特性来帮助我们实现等，那么关于栈的学习就到这里呢......