教你怎么用Java数组和链表实现栈

教你怎么用Java数组和链表实现栈

一、何为栈？

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

栈可以类比成现实生活中的弹夹或者羽毛球桶

二、用数组实现栈

用数组模拟栈的思路分析如图：

1.定义一个top变量（指针）表示栈顶初始化为-1.

2.定义一个变量来记录栈的大小。

3.入栈操作有数据加入到栈中：top++; arr[top]=value;

4.出栈操作： int value=arr[top]; top–; return value;

下面看完整代码示例：

class Stack{

public int maxsize;//栈的大小

public int top=-1;//栈顶

public int[] arr;

public Stack(int maxsize) {

this.maxsize = maxsize;

arr=new int[maxsize];

}

//判断栈是否为空

public boolean isEmpty(){

return top==-1;

}

//判断栈是否满

public boolean isFull(){

return top==maxsize-1;

}

//添加一个元素

public void push(int value){

if(isFull()){

throw new RuntimeException("栈满");

}

top++;

arr[top]=value;

}

//弹出一个元素

public int pop(){

if(isEmpty())

aojVtKQLJG throw new RuntimeException("栈空");

int value=arr[top];

top--;

return value;

}

//遍历栈中的元素

public void traverse(){

if (isEmpty()){

return;

}

//需要从栈顶开始显示数据

for(int i = top; i >= 0 ; i--) {

System.out.printf("stack[%d]=%d\n", i, arr[i]);

}

}

}

入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value;

出栈操作可以将 int value=arr[top]; top–;return value;改为return ahttp://rr[top–];

三、链表实现栈

思路分析：

入栈操作：用一个临时节点保存当前栈顶节点，将入栈的新节点作为栈顶元素，并将next域指向原来的旧节点。 Node temp=top; top.setNext(temp);

出栈操作：先判断栈是否为空，不为空则将top节点的数据返回，并将top指向top的下一个next域：top=top.getNext();

public class LinkedListStack {

static class Node{

private V data;

private Node next;

public V getData() {

return data;

}

public void setData(V data) {

this.data = data;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

}

public int stackSize;//栈内元素的个数

public Node top;//栈顶元素

public LinkedListStack() {

stackSize = 0;

top = null;

}

//入栈

public void push(V element){

Node temp=top;

top=new Node<>();

top.setData(element);

top.setNext(temp);

stackSize++;

}

//出栈

public V pop(){

if (isEmpty())

throw new RuntimeException("empty stack");

V value=top.getData();

//栈顶指向下一个元素

top=top.getNext();

stackSize--;

return value;

}

//查看栈顶元素

public V peek(){

return top.getData();

}

//判断是否为空

public boolean isEmpty(){

return stackSize==0;

}

//查看栈内元素个数

public int getStackSize(){

return stackSize;

}

}

四、测试

public class Test {

public static void main(String[] args) {

LinkedListStack stack = new LinkedListStack<>();

stack.push("a");

stack.push("b");

stack.push("c");

System.out.println(stack.pop());

System.out.println(stack.peek());

System.out.println(stack.getStackSize());

}

}

测试结果:

c

b

2

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