栈
定义：
栈是一种先进后出的数据结构，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈
栈的java代码实现：
基于数组：
import org.junit.jupiter.api.Test;
/**
* 用数组实现栈
* @author wydream
*
*/
public class ArrayStack<T> {
private T data[];
private int maxSize;
private int top;
//初始化栈
public ArrayStack(int maxSize) {
this.maxSize=maxSize;
data=(T[])new Object[maxSize];
this.top=-1;
}
//判断栈是否为空
public boolean isEmpty() {
return (top==-1);
}
//判断栈是否已经满了
public boolean isFull() {
return (top==maxSize-1);
}
//压栈
public boolean push(T value) {
if(isFull()) {
return false;
}
top++;
data[top]=value;
return true;
}
//取出栈顶元素
public T pop() {
if(isEmpty()) {
return null;
}
T tmp=data[top];
data[top]=null;
top--;
return tmp;
}
//============测试代码============
public static void main(String[] args) {
ArrayStack<String> as=new ArrayStack<String>(4);
as.push("anhui");
as.push("shanghai");
as.push("beijing");
as.push("nanj");
//测试栈已经满了的情况
System.out.println(as.push("aa"));
for(int i=0;i<4;i++) {
System.out.println(as.pop());
}
}
}
基于链表：
import org.junit.jupiter.api.Test;
/**
* 基于链表实现的栈
* @author wydream
*
*/
public class NodeStack<T> {
private Node<T> top=null;//栈顶
public NodeStack() {
this.top=null;
}
//判断栈是否为空
public boolean isEmpty() {
if(top!=null) {
return false;
}
return true;
}
//压栈
public boolean push(T value) {
Node<T> node=new Node<T>(value);
node.setNext(top);
top=node;
return true;
}
//出栈
public T pop() {
if(top==null) {
return null;
}
T tmp=top.data;
top=top.getNext();
return tmp;
}
//取出栈顶的值
public T peek() {
if(isEmpty()) {
return null;
}
return top.data;
}
class Node<T>{
private T data;//数据
private Node<T> next;//指向下一个节点的指针
//初始化链表
public Node(T data) {
this.data=data;
}
//获取下一个节点
public Node<T> getNext(){
return this.next;
}
//设置下一个节点
public void setNext(Node<T> n) {
this.next=n;
}
//获取节点数据
public T getData() {
return this.data;
}
//设置节点数据
public void setData(T d) {
this.data=d;
}
}
public static void main(String[] args) {
NodeStack<String> ns=new NodeStack<String>();
//测试是否为空
System.out.println("=======是否为空======");
System.out.println(ns.isEmpty());
System.out.println("=============");
//压栈测试
System.out.println("=======压栈======");
ns.push("北京");
ns.push("上海");
ns.push("深证");
ns.push("广州");
//是否为空
System.out.println("=======是否为空======");
System.out.println(ns.isEmpty());
System.out.println("=============");
System.out.println("=======出栈=======");
//出栈
System.out.println(ns.pop());
System.out.println(ns.pop());
System.out.println(ns.pop());
System.out.println(ns.pop());
System.out.println(ns.pop());
//是否为空
System.out.println("=======是否为空======");
System.out.println(ns.isEmpty());
System.out.println("=============");
}
}
两栈共享空间：
栈有个缺陷，必须事先确定数组的大小，这样如果栈满了的话，想在存储元素就必须通过编程手段来扩充数组的容量，这样就很麻烦。于是我们就设计一个数组，里面存放着两个栈，共享这一个数组空间，这样就可以充分利用空间。数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的0下标，另一个栈的栈为数组的长度n-1处
代码实现：
import javax.crypto.Mac;
/**
* 两栈共享空间
* @author wydream
*
*/
public class DoubleStatk {
private final static int MAXSIZE=20;
private int[] stackElem;
private int top1; //将top1设置为指向栈1栈顶元素的存储位置即数组下标0
private int top2; //将top2设置为指向栈2栈顶元素的存储位置即数组下标n-1
public DoubleStatk() {
top1=-1;
top2=MAXSIZE;
stackElem=new int[MAXSIZE];
}
//是否是空栈
public boolean isEmptyStack() {
if(top1==-1&&top2==MAXSIZE) {
return true;
}
return false;
}
//清空栈
public void clearStack() {
top1=-1;
top2=MAXSIZE;
}
//栈的长度
public int lengthStak() {
return (top1+1)+(MAXSIZE-top2);
}
//获取top1的元素
public int getTop1Elem() {
if(top1==-1) {
return -1;
}
return stackElem[top1];
}
//获取top2的元素
public int getTop2Elem() {
if(top2==MAXSIZE) {
return -1;
}
return stackElem[top2];
}
//压栈
public void stackPush(int stackNumber,int e) {
//如果栈已经满了
if(top1+1==top2) {
System.out.println("栈已满");
return;
}
if(stackNumber==1) {
top1+=1;
stackElem[top1]=e;
return;
}
if(stackNumber==2) {
top2-=1;
stackElem[top2]=e;
return;
}
}
//出栈
public int stackPop(int stackNumber) {
int rs;
if(isEmptyStack()) {
System.out.println("栈为空");
return -1;
}
if(stackNumber==1) {
rs= stackElem[top1];
top1--;
}else if(stackNumber==2) {
rs=stackElem[top2];
top2++;
}else {
System.out.println("输入数据有误");
return -1;
}
return rs;
}
public void stackTraverse() {
System.out.println("此时，栈中的元素为：");
int i=0;
while(i<=top1) {
System.out.println(stackElem[i++]+" ");
}
i=top2;
while(i<MAXSIZE) {
System.out.println(stackElem[i++]+" ");
}
System.out.println();
}
public static void main(String[] args) {
DoubleStatk seqStack=new DoubleStatk();
//1压栈
for(int j=1;j<=5;j++) {
seqStack.stackPush(1,j);
}
//2压栈
for(int i=MAXSIZE;i>=MAXSIZE-2;i--) {
seqStack.stackPush(2, i);
}
//输出
seqStack.stackTraverse();
System.out.println("栈的长度为："+seqStack.lengthStak());
seqStack.stackPop(2);
seqStack.stackTraverse();
System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());
System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());
System.out.println("栈的长度为: " + seqStack.lengthStak());
for (int i = 6; i <= MAXSIZE-2; i++) {
seqStack.stackPush(1,i);
}
seqStack.stackTraverse();
System.out.println("栈1的栈顶元素为: " + seqStack.getTop1Elem());
System.out.println("栈2的栈顶元素为: " + seqStack.getTop2Elem());
System.out.println("栈顶元素为: " + seqStack.getTop2Elem());
System.out.println("栈的长度为: " + seqStack.lengthStak());
System.out.println("栈是否为空: " + seqStack.isEmptyStack());
seqStack.clearStack();
System.out.println("栈是否为空: " + seqStack.isEmptyStack());
}
}