栈的描述
栈是基于后进先出(LIFO)的特殊的线性表,是应用非常广泛且极为重要的线性结构。其插入和删除操作都只允许在表尾进行。允许插入删除操作的一端称为栈顶(top),另一端成为栈底(bottom)。
顺序栈
基于数组实现的顺序栈。需要用一个变量top指示栈顶元素的位置。在这里我采用的是将top设置为指向栈顶元素存储位置的下一个存储单元的位置,即空栈的时候top==0。
package StackDemo;
public class SqStack {
private Object[] stackElem;
private int top; //指向栈顶元素下一个位置
//构造函数 构造一个存储容量为maxSize的空栈
public SqStack(int maxSize) {
top = 0;
stackElem = new Object[maxSize];
}
//栈置空
public void clean() {
top = 0;
}
//判断栈是否为空
public boolean isEmpty() {
return top == 0;
}
//求栈中数据元素的个数
public int length() {
return top;
}
//取栈顶的数据元素
public Object peek() {
//由于top指向栈顶元素下一个单元位置因此栈顶元素位置为top-1
if(!isEmpty())
return stackElem[top-1];
else
return null;
}
//入栈
public void push(Object x) throws Exception{
if(top==stackElem.length)
throw new Exception("栈已满");
else {
/* * 由于top指向栈顶元素下一个单元位置,因而直接将新元素压入top的位置(变为新的栈顶) * top再+1(指向新栈顶的下一个位置) */
stackElem[top++] = x;
}
}
//出栈
public Object pop() {
if(isEmpty())
return null;
else
return stackElem[--top]; //栈顶指向上一个元素
}
}
链栈
链栈的存储结构可以用不带头结点的单链表实现,只需要将栈顶元素放在链表首部并用top指向即可。
链表中的结点类描述
package LinkedDemo;
public class Node<T> {
/** * 用来存放结点的值 */
public T data;
/** * 用来存放后续的结点的引用 */
public Node<T> next;
public Node() {
// 调用有两个参数的构造方法Node(Object data,Node next)
this(null,null);
}
public Node(T data) {
// 同理
this(data,null);
}
public Node(T data,Node<T> next) {
this.data = data;
this.next = next;
}
}
几种常用方法
public class LinkStack<T>
void clean(); //栈清空
boolean isEmpty(); //判断栈是否为空
T peek(); //取栈顶元素并返回其值
int size(); //判断栈内元素个数
void push(T x); //入栈
T pop(); //出栈
具体实现:
入栈
//入栈
public void push(T x) {
Node<T> temp = new Node<T>(x); //构造新节点
temp.next = top;
top = temp; //新节点变为栈顶
}
出栈
//出栈
public T pop() {
if(isEmpty())
return null;
else {
Node<T> temp = top; //指向被删除的结点(原栈顶结点)
top = top.next; //修改链指针,使栈顶结点从链栈中移去
return temp.data; //返回栈顶结点的数据域的值
}
}
其他方法
package StackDemo;
import LinkedDemo.Node;
public class LinkStack<T> {
private Node<T> top;
//栈清空
public void clean() {
top = null;
}
//判断栈是否为空
public boolean isEmpty() {
return top == null;
}
//取栈顶元素并返回其值
public T peek() {
if(!isEmpty())
return top.data;
else
return null;
}
//判断栈内元素个数
public int size() {
Node<T> temp = top;
int size = 0;
while(temp!=null) {
temp = temp.next;
++size;
}
return size;
}
}