Java教程

分别用数组和链表实现栈结构

本文主要是介绍分别用数组和链表实现栈结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

  • 用数组实现栈的结构
    • push方法的代码
    • pop方法的代码
    • 遍历栈中的元素的方法
    • 测试代码
  • 利用链表实现栈的结构
    • 节点类信息
    • push方法的代码
    • pop出栈方法
    • 遍历方法
    • 测试代码
    • 测试结果

我们都知道，栈的特点是后进先出，先进后出，也就是先进栈里的，最后才能出来。

用数组实现栈的结构

栈用数组实现的结构

push方法的代码

public boolean isFull(){
        //如果top指向最后，则说明栈满
        return maxsize-1==top;
    }
 public void push(int value){
        if(isFull()){
            System.out.println("栈满，不能在添加元素"+value);
            return;
        }
        //每添加一个元素，指针都要向上移动
        stack[++top]=value;
        System.out.println("数据"+value+"添加成功");
    }

pop方法的代码

     public boolean isEmpty(){
        return top==-1;
    }
    
      public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈空");
        }
        
        int value=stack[top];
        //取出当前的元素之后，还要把指针后移！
        top--;
        return value;
    }

遍历栈中的元素的方法

public void show(){
        if(isEmpty()){
            System.out.println("栈为空");
        }
        //遍历时，是要从栈顶开始遍历的。
        for(int i=top;i>=0;i--){
            System.out.println(stack[i]+"---"+i);
        }
    }

测试代码

package com.njupt.stack;

/**
 * Creat with IntelliJ IDEA
 *
 * @Auther:倔强的加瓦
 * @Date:2021/07/16/9:44
 * @Description:
 */
public class StackDemo {
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        for (int i = 1; i <= 8; i++) {
            stack.push(i);
        }
        stack.show();
        for (int j = 1; j <= 9; j++) {
            System.out.println("第" + j + "次弹栈" + stack.pop());

        }

    }
}

class Stack {
    public int maxsize;
    public int top = -1;
    public int[] stack;

    public Stack(int maxsize) {
        this.maxsize = maxsize;
        stack = new int[maxsize];
    }

    public boolean isFull() {
        //如果top指向最后，则说明栈满
        return maxsize - 1 == top;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("栈满，不能在添加元素" + value);
            return;
        }
        stack[++top] = value;
        System.out.println("数据" + value + "添加成功");
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈中的所有元素
    public void show() {
        if (isEmpty()) {
            System.out.println("栈为空");
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i] + "---" + i);
        }
    }
}

利用链表实现栈的结构

节点类信息

class Node {
    public int no;
    public Node next;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }

和数组类似，要始终保证在插入时，一定要把插入的元素放到最前面。取元素后，也要让指针指向下一个节点。链表插入图解

push方法的代码

 //判断栈已满
    public boolean isFull() {
        return maxSize == count();
    }

    //输出链表中有多少节点
    public int count() {
        int num = 0;
        Node temp = head.next;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        return num;
    }
 public void push(Node node) {
        //如果是满的话，则不可以添加
        if (isFull()) {
            System.out.println("栈已满，不能在加");
            return;
        }
		//如果是空的话，直接加在最后即可
        if (isEmpty()) {
            head.next = node;
            //这里可搞死我了，忘了加一个return，也没有写else语句。。。
            return;
        } else {
            //temp指针始终指向第一个节点
            Node temp = head.next;
            //先让node指向temp
            node.next = temp;
            //然后让头节点指向新插入的节点
            head.next = node;
            System.out.println(node.no + "成功入栈");
        }

    }

pop出栈方法

//判断为空的方法
public boolean isEmpty() {
        return head.next == null;
    }
public void pop() {
        if (isEmpty()) {
            System.out.println("栈已空");
            return;
        } else {
            Node temp = head.next;
            if (temp.next != null) {
                System.out.println(head.next.no + "出栈");
                head.next = temp.next;
            } else {
                System.out.println(temp.no + "出栈");
                head.next = null;
            }
        }
    }

遍历方法

public void show() {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (true) {
            System.out.println(temp);

            if (temp.next == null) {
                break;
            }

            temp = temp.next;
        }
    }

测试代码

package com.njupt.stack;

/**
 * Creat with IntelliJ IDEA
 *
 * @Auther:倔强的加瓦
 * @Date:2021/07/16/18:11
 * @Description:使用链表实现模拟栈的结构
 */
public class ListStackDemo {
    public static void main(String[] args) {

        ListStack list = new ListStack(9);
        for (int i = 1; i <= 10; i++) {
            Node node = new Node(i);
            list.push(node);
        }
        System.out.println("=-=====");
        list.show();
        System.out.println("=-=====");

        for (int j = 1; j <= 12; j++) {
            list.pop();
        }


    }
}

//知道啦！用链表的话，就相当于逆序输出。
class ListStack {
    public int maxSize;
    public Node head = new Node(0);

    public ListStack(int maxSize) {
        this.maxSize = maxSize;
    }

    /*public ListStack(Node node){

    }*/
    public boolean isEmpty() {
        return head.next == null;
    }

    //判断栈已满
    public boolean isFull() {
        return maxSize == count();
    }

    //输出链表中有多少节点
    public int count() {
        int num = 0;
        Node temp = head.next;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        return num;
    }

    public void push(Node node) {
        //如果是空的话，直接加在最后即可
        if (isFull()) {
            System.out.println("栈已满，不能在加");
            return;
        }

        if (isEmpty()) {
            head.next = node;
            System.out.println(node.no+"成功入栈");
          
        } else {
            //temp指针始终指向第一个节点
            Node temp = head.next;
            //先让node指向temp
            node.next = temp;
            //然后让头节点指向新插入的节点
            head.next = node;
            System.out.println(node.no + "成功入栈");
        }

    }

    public void pop() {
        if (isEmpty()) {
            System.out.println("栈已空");
            return;
        } else {
            Node temp = head.next;
            if (temp.next != null) {
                System.out.println(head.next.no + "出栈");
                head.next = temp.next;
            } else {
                System.out.println(temp.no + "出栈");
                head.next = null;
            }
        }
    }

    public void show() {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (true) {
            System.out.println(temp);

            if (temp.next == null) {
                break;
            }

            temp = temp.next;
        }
    }
}

class Node {
    public int no;
    public Node next;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}

测试结果

1成功入栈
2成功入栈
3成功入栈
4成功入栈
5成功入栈
6成功入栈
7成功入栈
8成功入栈
9成功入栈
栈已满，不能在加
=-=====
Node{no=9}
Node{no=8}
Node{no=7}
Node{no=6}
Node{no=5}
Node{no=4}
Node{no=3}
Node{no=2}
Node{no=1}
=-=====
9出栈
8出栈
7出栈
6出栈
5出栈
4出栈
3出栈
2出栈
1出栈
栈已空
栈已空
栈已空

Process finished with exit code 0
这篇关于分别用数组和链表实现栈结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航