亲宝软件园·资讯

展开

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

熊三@ 人气: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());
 }
}

栈的主要操作

  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

加载全部内容

相关教程
猜你喜欢
用户评论