代码实现:
public class Stackimplements Iterable { private Node head; private int N; // 定一个内部类 private static class Node { T item; Node next; public Node(T item,Node next) { this.item=item; this.next=next; } } // 构造方法 public Stack() { this.head=new Node(null,null); this.N=0; } // 判断栈中元素是否为空 public boolean isEmpty() { return N==0; } // 返回栈中元素个数 public int size() { return N; } // 把t元素压入栈中 public void push(T t) { Node oldfirst=head.next; Node newNode=new Node(t,null); head.next=newNode; newNode.next=oldfirst; N++; } // 弹出栈中的元素 public T pop() { Node oldfirst=head.next; if(oldfirst==null) { return null; } head.next=oldfirst.next; N--; return oldfirst.item; } @Override public Iterator iterator() { // TODO 自动生成的方法存根 return new SIterator(); } private class SIterator implements Iterator{ private Node n; public SIterator(){ this.n=head; } @Override public boolean hasNext() { // TODO 自动生成的方法存根 return n.next!=null; } @Override public Object next() { // TODO 自动生成的方法存根 n=n.next; return n.item; } } }
栈的应用：
案例:
1、逆波兰表达式求值问题
题目描述:
中缀表达式： 中缀表达式就是我们平常生活中使用的表达式，例如： 1+3*2,2-(1+3) 等等，中缀表达式的特点是：二元运算符总 是置于两个操作数中间。 中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的 运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做 大量的优先级相关操作。 逆波兰表达式 ( 后缀表达式 ) ： 逆波兰表达式是波兰逻辑学家 J ・卢卡西维兹 (J ・ Lukasewicz) 于 1929 年首先提出的一种表达式的表示方法，后缀表 达式的特点：运算符总是放在跟它相关的操作数之后。 需求： 给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果。 分析： 1. 创建一个栈对象 stack 存储操作数 2. 从左往右遍历逆波兰表达式，得到每一个字符串 3. 判断该字符串是不是运算符，如果不是，把该该操作数压入 stack 栈中 4. 如果是运算符，则从 stack 栈中弹出两个操作数 o1 , o2 5. 使用该运算符计算 o1 和 o2 ，得到结果 result 6. 把该结果压入 stack 栈中 7. 遍历结束后，拿出栈中最终的结果返回代码实现：
public static void main(String[] args) {
// 中缀表达式3*(17-15)+18/6的逆波兰表达式如下
String notation[]= {"3","17","15","-","*","18","6","/","+"};
int result=caculate(notation);
System.out.println("逆波兰表达式的结果为:"+result);
}
private static int caculate(String[] notation) {
// 创建一个栈对象stack存储操作数
Stack stack=new Stack();
// 从左往右遍历逆波兰表达式，得到每一个字符串
for(int i=0;i
2.队列
队列是一种基于先进先出
(FIFO)
的数据结构，是一种只能在一端进行插入
,
在另一端进行删除操作的特殊线性表，它 按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。
代码实现：
public class Queue implements Iterable{
// 首节点
private Node head;
// 尾结点
private Node last;
// 记录队列中元素个数
private int N;
// 定义内部类
private static class Node{
T item;
Node next;
public Node(T item,Node next) {
this.item=item;
this.next=next;
}
}
// 构造方法
public Queue(){
head=new Node(null,null);
last=null;
N=0;
}
// 判断队列元素是否为空
public boolean isEmpty() {
return N==0;
}
// 返回队列中元素个数
public int size() {
return N;
}
//从队列中拿出一个元素
public T dequeue() {
if(isEmpty()) {
return null;
}
Node oldfirst=head.next;
head.next=oldfirst.next;
// 元素个数-1
N--;
//
if(isEmpty()) {
last=null;
}
return oldfirst.item;
}
//向队列中插入元素t
public void enqueue(T t) {
if(last==null) {
last=new Node(t,null);
head.next=last;
}else {
Node oldlast=last;
last=new Node(t,null);
oldlast.next=last;
}
// 元素个数+1
N++;
}
@Override
public Iterator iterator() {
return new QIterator();
}
private class QIterator implements Iterator{
Node n;
public QIterator() {
n= head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n=n.next;
return n.item;
}
}
}
