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

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

}

}

栈的主要操作

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

}

}

运行结果：

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

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。