一．介绍
堆栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
堆栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为先进后出表（Last In First Out , 简称LIFO）。
比如：堆栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来。
二．知识点介绍
1、堆栈原理
2、Stack使用
三．上课对应视频的说明文档
1、堆栈原理
(1) 一图：当栈里面没有任何元素的时候，为空栈，栈顶和栈底在同一个位置
(2) 二图：当A元素进入我们的栈里面后，他所进入的过程叫入栈，栈底不变，栈顶为A元素的上部
(3) 三图：在栈中加入B，C,D三个元素后，栈底不变，栈顶为D元素上部
(4) 四图：D元素被移出，这个过程叫出栈，栈底不变，栈顶发生变化，栈顶为C元素的上部
2、Stack使用
public push(item) 把项压入栈顶。其作用与 addElement (item ) 相同。
参数 item 压入栈顶的项 。 返回： item 参数
public pop () 移除栈顶对象，并作为函数的值 返回该对象。
返回：栈顶对象（Vector 对象的中的最后一项）。
抛出异常 ： EmptyStackException 如果堆栈式空的 。。。
public peek() 查看栈顶对象而不移除它。。
返回：栈顶对象（Vector 对象的中的最后一项）。
抛出异常 ： EmptyStackException 如果堆栈式空的 。。。
public boolean empty （测试堆栈是否为空。） 当且仅当堆栈中不含任何项时 返回 true，否则 返回 false.
public int search (object o) 返回对象在堆栈中位置， 以 1 为基数， 如果对象 ｏ是栈中的一项，该方法返回距离 栈顶最近的出现位置到栈顶的距离； 栈中最上端项的距离为 １ 。 使用equals 方法比较 o 与 堆栈中的项。。。
案例：
import java.util.*;
public class StackTest{
public static void main(String args[]){
Stack s=new Stack();//产生一个空栈
s.push("A");
s.push("B");//入栈
s.push("C");
System.out.println(s.peek());//显示栈顶的元素
//System.out.println(s.pop());//显示栈顶的元素，并移出。
System.out.println(s);
System.out.println(s.search("A"));
Iterator i=s.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
/*
while(!s.empty()){
System.out.println(s.peek());
}
System.out.println(s);
*/
}
}
案例：数组实现堆栈
public class ArrayOfStack {
private Object[] stack = null;
private int size;
private int top;
//默认初始化一个栈堆,大小为100
public ArrayOfStack(){
this.size = 100;
this.top = -1;
this.stack = new Object[size];
}
//初始化一个自定义大小的栈堆
public ArrayOfStack(int size){
this.size = size;
this.top = -1;
this.stack = new Object[size];
}
//判断堆栈是否为空
public boolean isEmpty(){
if(top == -1){
return true;
}else
return false;
}
//判断栈堆是否已满
public boolean isFull(){
if(top == (size-1)){
return true;
}else
return true;
}
//入栈操作
public void push(String data){
if(isFull()){
System.out.println("堆栈已满");
return;
}
//入栈开始，top相当于数组下标
top++;
stack[top] = data;
}
//出栈
public Object pop(){
//定义一个临时对象
Object val = null;
//堆栈为空时报错
if(isEmpty()){
System.out.println("堆栈为空");
return val;
}
//获取堆栈值
val = stack[top];
top--;
return val;
}
//获取栈顶元素
public Object peek(){
Object topVal = null;
if(isEmpty()){
System.out.println("栈堆为空!");
return topVal;
}
//取出栈顶元素
topVal = stack[top];
return topVal;
}
//获取堆栈元素
public int size(){
return top+1;
}
//获取栈堆容量
public int capcity(){
return size;
}
}
案例：链表实现堆栈
public class Node {
//链表数据域
Object data;
//链域
Node next;
//构造头结点
public Node(){
this.data = null;
this.next = null;
}
//构造节点
public Node(Object data){
this.data = data;
this.next = null;
}
}
案例：堆栈类
public class LinkOfStack {
//定义一个头结点
private Node head;
//构造头结点
public LinkOfStack(){
head = new Node();
}
//判断是否为空
public boolean empty(){
if(head.next == null)
return true;
else
return false;
}
//堆栈入栈
public void push(Object data){
Node item = new Node(data);
item.next = head.next;
head.next = item;
}
//出栈
public Object pop(){
Object item = null;
if(empty()){
System.out.println("堆栈为空");
}
item = head.next.data;
head.next = head.next.next;
return item;
}
//堆栈大小
public int size(){
int len = 0;
Node p = head;
while(p.next != null){
len++;
p = p.next;
}
return len;
}
//获取栈顶元素
public Object peek(){
if(empty()){
System.out.println("堆栈为空");
}
return head.next.data;
}
public static void main(String[] args){
LinkOfStack stack = new LinkOfStack();
stack.push("测试链表堆栈节点一");
System.out.println(stack.size());
System.out.println(stack.peek());
while(!stack.empty()){
System.out.print(stack.pop()+"-->");
}
}
}
网友评论