java判断栈中元素数目_Java数据结构与算法-栈和队列

(摘录加总结)------

栈和队列不属于基础的数据结构，它们都属于线性表。

一、栈

对于栈存储操作元素只能在栈结构的一端进行元素的插入和删除，是一种性质上的线性表结构。按照“先进后出”的原则进行存储数据。先进的元素在栈底，后进的元素在栈顶。需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。比较常规的说明是：栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH)，删除则称为退栈(POP)。

栈的实现结构包括顺序结构实现和链式结构实现。前者依据的是数组，后者是链表。

(1)利用数组实现栈

下面这个是一个基本的实现：①在Stack底层设置了一个int数组，当然可以使用泛型来指代不同的数据类型。最大容量和栈顶位置。特别需要注意的是在初始化时也看出来，一般在初始化的时候top位置设置为-1，这是利于后面在压入数据的时候数组的第一位是array[0]，并且maxSize最大容量和数组的length是一致的。②top表示这个数组的当前的没有被设置元素的第一个位置的标志位是多少，首先要判断是否小于maxSize-1，因为是从-1开始的，并且每次判断都是++top，是先自增的处理，示意如下，假如初始化了一个容量为3的数组：

③当压栈完成的时候自然top的索引值已经变成了数组最高项的值的大小，在进行pop弹栈操作的时候自然已经是完成了压栈操作的，此时的top的值是最大位置处，所以return array[top--]就完成了弹出最大的那个元素，并且将索引top值在弹栈之后再减一。④判断是否空栈是通过top == -1来判断的，即初始化的情况。

public class MyStack {

private int[] array;

private int maxSize;

private int top;

public MyStack(int size){

this.maxSize = size;

array = new int[size];

top = -1;

}

//压入数据

public void push(int value){

if(top < maxSize-1){

array[++top] = value;

}

}

//弹出栈顶数据

public int pop(){

return array[top--];

}

//访问栈顶数据

public int peek(){

return array[top];

}

//判断栈是否为空

public boolean isEmpty(){

return (top == -1);

}

//判断栈是否满了

public boolean isFull(){

return (top == maxSize-1);

}

}

(2)利用栈的后进先出的特性可以很容易的实现逆序的操作，比如下面这个利用栈实现字符串的输入的逆序：这里使用一个用Object类型数组来接收数据，并且加入了判断是否扩容的ArrayStack类来进行测试，实现字符串的逆序输出：

package stack.test;

import java.util.Arrays;

import java.util.EmptyStackExcep