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

时间:2020-12-04 熊三@ 人气:0

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());
 }
}

栈的主要操作

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

栈的辅助操作

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

实现

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

基于简单数组的实现方法
基于动态数组的实现方法
基于链表的实现方法

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);
  }
}

运行结果：

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();
  }
}

运行结果：

加载全部内容