首页 > 编程语言 > Java栈的三种实现方式(完整版)
2020
12-05

Java栈的三种实现方式(完整版)

java什么是栈

系统中的堆、栈和数据结构堆、栈不是一个概念。可以说系统中的堆、栈是真实的内存物理区，数据结构中的堆、栈是抽象的数据存储结构。

栈：实际上就是满足后进先出的性质，是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。

栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

栈的优势是，存取速度比堆要快，仅次于直接位于CPU中的寄存器。但缺点是，存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。

代码：

Stack的基本使用
初始化
Stack stack=new Stack
判断是否为空
stack.empty()
取栈顶值（不出栈）
stack.peek()
进栈
stack.push(Object);
出栈
stack.pop();
实例：
public class Test01 {
 public static void main(String[] args) {
 Stack stack=new Stack();
 //1.empty()栈是否为空
 System.out.println(stack.empty());
 //2.peek()栈顶值  3.进栈push()
 stack.push(new Integer(1));
 stack.push("b");
 System.out.println(stack.peek());
 //4.pop()出栈
 stack.pop();
 System.out.println(stack.peek());
 }
}

栈的主要操作

  1. void push(int data)：将data（数据）插入栈
  2. int pop()：删除并返回最后一个插入栈的

栈的辅助操作

  1. int top()：返回最后一个插入栈的元素，但不删除
  2. int size()：返回存储在栈中的元素的个数
  3. int isEmpty()：判断栈中是否有元素
  4. int isStackFull()：判断栈中是否满元素

实现

栈抽象数据类型有多种实现方式。下面是常用的方法：

  1. 基于简单数组的实现方法
  2. 基于动态数组的实现方法
  3. 基于链表的实现方法

1）基于简单数组实现： 

public class Stack{
  private int size;//栈的大小
  private int top;//栈顶元素的下标
  private char[] stackArray;//栈的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化栈的时候由于栈内没有元素，栈顶下标设为-1  
  	this.size = size;
  }
  //入栈,栈顶的下标+1
  public void push(char item){
  	stackArray[++top] = item;
  }
  //出栈，删除栈顶元素，栈顶元素的下标-1
  public int pop(){
  	return stackArray[top--];
  }
  //查看栈顶元素，不删除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判满
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	char ch = stack.find();
  	System.out.println(ch);
  }
}

运行结果：

d

2）基于动态数组实现：

扩容——给我的感觉就像是在搬家，搬完了东西，还得把钥匙给主人

public class Stack {
	public int size;//栈的大小
  public int top;//栈顶元素的下标
  public static char[] stackArray;//栈的容器
  public Stack(int size){
  	stackArray = new char[size];
  	top = -1;     //初始化栈的时候由于栈内没有元素，栈顶下标设为-1     
  	this.size = size;
  }
  //入栈,栈顶的下标+1
  public void push(char item){
  		if(isFull()){
  			doubleStack();
  		}
  		stackArray[++top] = item;
  }
  //模拟数组的扩容
  public void doubleStack(){
  	char[] newStackArray = new char[size*2];
  	for(int i = 0;i<size;i++){
  		newStackArray[i] = stackArray[i];
  	}
  	size = size*2;
  	stackArray = newStackArray;
  }
  //出栈，删除栈顶元素，栈顶元素的下标-1
  public int pop(){
  	if(isEmpty()){
  		System.out.println("Stack is Empty");
  		return 0;
  	}else{ 		
  		return stackArray[top--];
  	}
  }
  //查看栈顶元素，不删除
  public char find(){
  	return stackArray[top];
  }
  //判空
  public boolean isEmpty(){
  	return (top == -1);
  }
  //判满
  public boolean isFull(){
  	return (top == size - 1);
  }
  public static void main(String[] args){
  	Stack stack = new Stack(5);
  	stack.push('a');
  	stack.push('b');
  	stack.push('c');
  	stack.push('d');
  	stack.push('e');
  	stack.push('f');
  	stack.push('g');
  	stack.push('h');//一共8个元素
  	char ch = stack.find();
  	System.out.println(ch);
  	System.out.println(stackArray.length);
  }
}

运行结果：

h
10

3）基于链表实现

使用链表实现栈，通过在链表的表头插入元素的方式实现push操作，删除链表的表头结点实现pop操作。表头结点即栈顶结点

import java.util.EmptyStackException;
class Link{
	public char data;
	public Link next;
	public void show(){
		System.out.println(data + " ");
	}
	public Link(char data){
		this.data = data;
	}
}
public class Stack2 {
	Link head;
  public int size;//栈的大小
  public int top;//栈顶元素的下标
  public static char[] stackArray;//栈的容器
  public void push(char data){
  	if(head == null){
  		head = new Link(data);
  	}else{
  		Link node = new Link(data);
  		node.next = head;
  		head = node;
  	}
  }
  public void pop(){
  	if(head == null){
  		throw new EmptyStackException();
  	}else{
  		char dat = head.data;
  		head.show();
  		head = head.next;
  	}
  }
  public int top(){
  	if(head == null){
  		return 0;
  	}else{
  		return head.data;
  	}
  }
  public boolean isEmpty(){
  	if(head == null) return true;
  	return false;
  }
  public static void main(String[] args){
  	Stack2 stack = new Stack2();
  	stack.push('A');
  	stack.push('B');
  	stack.push('C');
  	stack.push('D');
  	stack.push('E');
  	stack.push('F');
  	stack.pop();
  }
}

运行结果：

F

到此这篇关于Java栈的三种实现方式(完整版)的文章就介绍到这了,更多相关Java栈内容请搜索自学编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持自学编程网！

编程技巧