Java数据结构基础--顺序栈与链式栈

Java数据结构基础–顺序栈与链式栈

栈的定义：
是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
栈的操作：
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的特点：
先进后出，即先入栈的最后操作，后入栈的最先操作。

顺序栈（基于数组）：

完整代码：

public class Stack {
	
	private Object elements[];//存储数组
	private int top;//最后一个元素位置下标
	private int maxsize;//最大存储量
	private int stackIncreament = 50;//栈溢出扩容数量
	
	public Stack(int maxsize) {
		top = -1;
		this.maxsize = maxsize;
		elements = new Object[maxsize];
	}
	
	private void overfolwProcess() {//扩充栈
		Object newArray = new Object[maxsize+stackIncreament];
		System.arraycopy(elements, 0, newArray, 0, top+1);//复制数值元素
		elements = (Object[]) newArray;
		maxsize = maxsize+stackIncreament;
	}
	
	public void Push(Object x) {//入栈
		
		if(IsFull()==true) {//栈满做溢出处理
			overfolwProcess();
		}
		top = top +1;
		elements[top] = x;
	}

	private boolean IsFull() {//判断是否栈满
		
		if(top+1 == maxsize) {
			return true;
		}
		
		return false;
		
	}
	
	public boolean Pop() {//退栈
		
		if(IsEmpty() == true) {
			System.out.println("栈空，无元素");
			return false;
		}
		top--;
		return true;
	}

	private boolean IsEmpty() {//判断栈是否为空
		if(top == -1) {
			return true;
		}
		return false;
	}
	
	public Object getTop() {//获取栈顶元素
		
		if(IsEmpty() == true) {
			System.out.println("栈空，无元素");
			return false;
		}
		return elements[top];
	}
	
	@Override
	public String toString() {//输出函数
		
		String rel = "";
		int index = top;
		if(IsEmpty()==true) {
			return rel;
		}
		while(index > 0) {
			rel = rel + elements[index]+"-->" ;
			index--;
		}
		rel +=  elements[0];
		return rel;
	}
}

部分函数详解：

1. Stack栈类：

public class Stack {
	private Object elements[];//存储数组
	private int top;//最后一个元素位置下标
	private int maxsize;//最大存储量
	private int stackIncreament = 50;//栈溢出扩容数量
	}

（1）基于数组实现，用elements[]存储数据。
（2）用top来指向栈顶，这里则指向栈顶元素的数组下标。(初始值为-1)
（3）maxsize：初始化时定义的最大存储量，既数组长度。
（4）stackIncreament：当存储数据个数超过最大存储量，自动扩容量。

2. overfolwProcess() - -扩充栈

private void overfolwProcess() {//扩充栈
		Object newArray = new Object[maxsize+stackIncreament];
		//定义扩容后对应数组长度的数组，原来最大长度maxsize+自动扩容长度stackIncreament
		System.arraycopy(elements, 0, newArray, 0, top+1);
		//arraycopy函数复制数组元素，
		//System.arraycopy(被复制数组, 开始复制元素下标, 粘贴到此数组, 开始粘贴元素下标, 复制粘贴元素长度);
		elements = (Object[]) newArray; //将扩容后数组赋值给栈中的数组
		maxsize = maxsize+stackIncreament;//更新最大存储长度
	}

3. Push(Object x)- -入栈

public void Push(Object x) {//入栈
		
		if(IsFull()==true) {//栈满做溢出处理
			overfolwProcess();//扩容操作
		}
		top = top +1;
		elements[top] = x;
	}

4. Pop()- -退栈

public boolean Pop() {//退栈
		
		if(IsEmpty() == true) {
			System.out.println("栈空，无元素");
			return false;
		}
		top--;//改变栈顶指向，通过改变top指向的数组下标实现
		return true;
	}

5.测试函数：

public class Main {
	public static void main(String[] args) {
		
		Stack stack = new Stack(4);
		stack.Push(1);//入栈
		stack.Push(2);
		stack.Push(3);
		stack.Push(4);
		stack.Push(5);
		System.out.println(stack);//重载toString函数，改变输入方式
		stack.Pop();//退栈
		stack.Push(6);
		System.out.println(stack);
	}
}

执行结果：

链式栈（基于单链表）：

完整代码：

public class LinkedStack {

	public class Node {
		private Object data;// 存放数据
		private Node next;// 下一个节点（指针）

		public Node(Object data, Node next) {// 双参数构造函数
			this.data = data;
			this.next = next;
		}

		public Node(Object data) {// 单参数构造函数
			this.data = data;
			this.next = null;
		}

		public Node() {// 单参数构造函数
		}
	}

	private Node top ;// 栈顶指针，链头指针

	public void Push(Object x) {// 入栈
		top = new Node(x, top);// top指向新结点，新节点指向原来的栈顶
	}

	public boolean Pop() {// 退栈
		if (IsEmpty() == true) {
			return false;
		}
		top = top.next;// 栈顶移动一个节点
		return true;
	}

	private boolean IsEmpty() {// 是否为空
		if (top == null) {
			return true;
		}
		return false;
	}

	public Object getTop() {// 获取栈顶值
		if (IsEmpty() == true) {
			System.out.println("栈空");
			return null;
		}
		return top.data;
	}

	public int getSize() {// 获取长度
		Node p = top;
		int k = 0;
		while (p != null) {
			p = p.next;
			k++;
		}
		return k;
	}

	@Override
	public String toString() {
		String ans = "top-->";
		Node p = top;
		while (p != null) {
			ans += p.data + "-->";
			p = p.next;
		}
		ans += "null";
		return ans;
	}
}

部分函数详解：

1. Node结点：

	public class Node {
		private Object data;// 存放数据
		private Node next;// 下一个节点（指针）
	}

在链式栈中，将数组换成了一个一个的节点。
顺序栈基于数组实现，链式栈基于单链表实现

原先的top也用Node节点替代：

private Node top ;// 指向栈顶元素

2.Push（）- -入栈：

public void Push(Object x) {// 入栈
		top = new Node(x, top);// top指向新结点，新节点指向原来的栈顶
	}

3. Pop()- -退栈

	public boolean Pop() {// 退栈
		if (IsEmpty() == true) {
			return false;
		}
		top = top.next;// 栈顶移动一个节点
		return true;
	}

4. getSize() - -获取长度

	public int getSize() {// 获取长度
		Node p = top;//定义一个新节点指向top栈顶
		int k = 0;
		while (p != null) {
			p = p.next;//节点后移
			k++;
		}
		return k;
	}

这里利用节点后移计算长度，和单链表计算长度相同。

应该注意的一点是：
重新定义新节点p，利用新节点p指向top后在后移。如果直接用top计算长度，会改变栈顶指向。

5. 测试函数：

public class Mian {
	public static void main(String[] args) {
		LinkedStack stack = new LinkedStack();
		stack.Push(1);//入栈
		stack.Push(2);
		stack.Push(3);
		System.out.println(stack);
		stack.Pop();//退栈
		System.out.println(stack);
		System.out.println(stack.getTop());//取栈顶数据并输出
	}
}

测试结果：

有写的不清楚的地方欢迎留言，谢谢观看。