数据结构——栈

栈（Stack）的含义

栈是一种特殊的线性表，它只允许在表的的一端进行插入和删除操作，栈的两端分别称为栈顶和栈底，栈顶即为数据插入和删除的一端，而 栈底则存放的是第一个被插入的数据，当然这条数据也会是最后一个被取出的数据。当一条数据元素要存入栈中，叫作进栈（push），即将该数据放在栈顶位置成为新的栈顶元素，而从栈顶取出一条数据元素叫作出栈（pop），即将栈顶元素删除。

这是栈在汉语中的解释：

1.储存货物或供旅客住宿的房屋：货～。客～。～房。 2.竹木编成的遮蔽物或其他东西：马～（养马的竹木棚）。～车（古代用竹木编成棚的车子）。 3.用木料或其他材料架设的通道：～道。～桥（一种形似桥梁的建筑物，用于装卸货物、上下旅客等）。 4.通过，越过：～山航海。

在计算机中栈就是用来存储数据的一个仓库，一种先进后出的数据结构，栈的模型如下图所示：

栈的基本操作

定义栈的长度为length，栈顶元素位置为top。

进栈 1、进栈时先判断栈top是否大于等于length，若小于执行2，否则则提示栈满，无法入栈。 2、top++，即top指向新的栈顶位置 3、stack[top] = newData 将新元素赋值到栈顶处

出栈 1、出站时先判断top是否小于等于0，即判断栈中是否还有元素，若有执行2，否则提示栈为空。 2、data = stack[top] 将出栈元素保存下来 3、top–，即top位置减一。

-

javaAPI中对stack方法定义

用java语言实现一个简单的栈结构，重写这些操作：

class myStack { private int size; private int top; private int[] stackArr; public myStack(int size) { this.size=size; this.top=-1; stackArr = new int[this.size]; } /** * 测试堆栈是否为空。 * @return */ public boolean empty() { if(top<=0) return true; else return false; } /** * 查看栈顶元素，但不删除 * @return */ public int peek() { return stackArr[top]; } /** * 移除栈顶元素，并作为函数的返回值 * @return */ public int pop(){ return stackArr[top--]; } public int push(int item){ if(this.top>=this.size) return -1; else { top++; stackArr[top]=item; return item; } } /** * 返回对象在栈中的位置，返回距离堆栈第一出线的位置到栈顶距离，栈最顶部项的距离为1 * @param item * @return */ public int search(int item){ for(int i=top;i>=0;i--){ if(stackArr[i]==item) return top-i+1; } return -1; } }

当然，实际中栈的实现并非这么简单，里面还夹杂着泛型，容器等许多知识点，这里只是做一个简单的例子来了解一下栈的基本结构与操作。