首页 > 其他 > 详细

数据结构之栈

时间:2020-12-06 00:22:01      阅读:35      评论:0      收藏:0      [点我收藏+]

一.数组实现栈

package com.bzw.stack;

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {

        ArrayStack arrayStack = new ArrayStack(5);
        Scanner scanner = new Scanner(System.in);
        String key = " ";
        boolean flag = true;
        while (flag){
            System.out.println("显示菜单(show):");
            System.out.println("入栈(push):");
            System.out.println("出栈(pop):");
            System.out.println("退出(exit):");
            System.out.println("输入要进行的操作:");

            key = scanner.next();
            switch (key){
                case "show":
                    arrayStack.showStack();
                    break;
                case "push":
                    System.out.println("输入入栈的值:");
                    int val = scanner.nextInt();
                    try {
                        arrayStack.push(val);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "pop":
                    try {
                        System.out.println("出栈的是:" + arrayStack.pop());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
    }
}

//用数组实现栈
class ArrayStack{

    private int maxSize;
    private int top ;
    private int[] stack;

    public ArrayStack(int maxSize){
        this.top = -1;
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

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

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

    public void push(int data){
        if (isFull()){
            //System.out.println("栈满,无法插入");
          throw  new RuntimeException("栈满,无法插入");//如果不抛异常,仍然会执行下面的代码就会报错
        }
        top++;
        stack[top] = data;
    }

    public int pop(){
        if (isEmpty()){
           //System.out.println("栈空,无法出栈");
            throw  new RuntimeException("栈空,无法出栈");
        }
        int res = stack[top];
        top--;
        return res;
    }

    public void showStack(){
       if (isEmpty()){
           System.out.println("空栈");
       }
       for (int i=top;i>=0;i--){
           System.out.printf("stack[%d]=%d\n",i,stack[i]);
       }
    }
}

 

二.单链表实现栈

package com.bzw.stack;

import java.util.Scanner;

//单链表实现栈
public class SingleLinkedStackDemo {
    public static void main(String[] args) {

        SingleLinkedStack singleLinkedStack = new SingleLinkedStack();
        Scanner scanner = new Scanner(System.in);
        String key = " ";
        boolean flag = true;
        while (flag){
            System.out.println("显示菜单(show):");
            System.out.println("入栈(push):");
            System.out.println("出栈(pop):");
            System.out.println("退出(exit):");
            System.out.println("输入要进行的操作:");

            key = scanner.next();
            switch (key){
                case "show":
                    singleLinkedStack.show();
                    break;
                case "push":
                    System.out.println("输入入栈的值:");
                    int val = scanner.nextInt();
                    try {
                        singleLinkedStack.push(val);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "pop":
                    try {
                        //singleLinkedStack.reserver();
                        System.out.println("出栈的是:" + singleLinkedStack.pop());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
    }
}

class Node{
    public int num;
    public Node next;

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

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ‘}‘;
    }
}
class SingleLinkedStack{

    Node head = new Node(-1);

    public Node getHead() {
        return head;
    }


//    public void add(Node node){
//        Node temp = head;
//        while (true){
//            if (temp.next == null)
//                break;
//            else temp = temp.next;
//        }
//        temp.next = node;
//    }
//
//    public void reserver(){
//        Node temp = head.next;
//        Node head2 = new Node(-1);
//        Node temp2 = null;
//
//        if (temp == null)
//            return;
//        while (temp != null){
//            temp2 = temp.next;
//            temp.next = head2.next;
//            head2.next = temp;
//            temp = temp2;
//        }
//
//        head.next = head2.next;
//    }
//
//    public int pop(){
//        int res = head.next.num;
//        return res;
//    }

//    为了实现栈先进后出的特点,直接将结点插在最前端就可以。
    public void add(Node node){
        Node temp = head.next;
        head.next = node;
        node.next = temp;
    }

    public void push(int val){
        Node node = new Node(val);
        add(node);
    }

    public int pop(){

        int res = head.next.num;
        head.next = head.next.next;
        return res;
    }



    public void show(){
       Node temp = head.next;
       if (temp == null){
           System.out.println("空栈");
           return;
       }
       while (temp != null){
           System.out.println(temp);
           temp = temp.next;
       }
    }


}

 

数据结构之栈

原文:https://www.cnblogs.com/tiger2048/p/14091647.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!