栈的顺序与链式存储（Java）

冷不防 2023-06-27 06:09 78阅读 0赞

**栈**：限定仅在表尾进行插入和删除操作的线性表。

栈的插入（进栈）和删除（出栈）操作如下图所示。

![format_png][]

![format_png 1][]

** 1.栈的顺序存储结构**

用数组存放数据，top变量来指示栈顶元素在数组中的位置（栈顶指针）。一个长度为5的栈的示意图如下：

![format_png 2][]

实现程序：

/**
     * 栈的顺序储存结构
     *
     * 问题：构造器中，泛型数组创建是否有更好的方法？
     *
     */
    public class SqStack<E> {
        private E[] data;
        private int top;  //栈顶指针，top=-1时为空栈
        private int maxSize;
        private static final int DEFAULT_SIZE= 10;
         
        public SqStack() {
            this(DEFAULT_SIZE);
        }
        public SqStack(int maxSize) {
            //无法创建泛型数组 data=new E[maxSize];
            data=(E[]) new Object[maxSize];
            top=-1;
            this.maxSize=maxSize;
        }
         
        public void push(E e) {
            if(top==maxSize-1)
                throw new RuntimeException("栈已满，无法进栈！");
            top++;
            data[top]=e;
        }
         
        public E pop() {
            if(top==-1)
                throw new RuntimeException("空栈，无法出栈！");
            E e=data[top];
            top--;
            return e;
        }
         
        public void printStack() {
            if(top==-1) {
                System.out.println("空栈");          
            }else {
                for(int i=0;i<=top;i++) {
                    System.out.println(data[i]);
                }
            }      
        }
    }

测试代码：

public class StackTest {
        public static void main(String[] args) {
            SqStack<Student> sqStack=new SqStack<Student>();       
            Student[] students= {new Student("小A",11),new Student("小B",12),new Student("小C",13),
                    new Student("小D",14),new Student("小E",151)};
            for(int i=0;i<5;i++) {
                sqStack.push(students[i]);
            }
            sqStack.printStack();
            for(int i=0;i<5;i++) {
                sqStack.pop();
            }
            sqStack.printStack();      
        }      
    }
     
    class Student{
        public Student(String name, int age) {
            this.name=name;
            this.age=age;
        }
        String name;
        int age;
        public String toString() {
            return name;
        }
    }

**2.两栈共享空间**

通过一个数组存放两个栈，能较好地利用空间。用top1和top2变量表示栈1和栈2的栈顶指针，两个栈的栈底分别位于数组的头部和尾部。

![format_png 3][]

实现程序（在SqStack程序的基础上稍加改造即可）：

/**
     * 栈的顺序储存结构（两栈共享空间）
     *
     * 注意点：栈满条件为top1+1==top2
     *
     * @author Yongh
     *
     */
    public class SqDoubleStack<E> {
        private E[] data;
        private int top1;  //栈1栈顶指针，top=-1时为空栈
        private int top2;  //栈2栈顶指针，top=maxSize-1时为空栈
        private int maxSize;
        private static final int DEFAULT_SIZE= 10;
         
        public SqDoubleStack() {
            this(DEFAULT_SIZE);
        }
        public SqDoubleStack(int maxSize) {
            //无法创建泛型数组 data=new E[maxSize];
            data=(E[]) new Object[maxSize];
            top1=-1;
            top2=maxSize-1;
            this.maxSize=maxSize;
        }
         
        /*
         * 进栈操作，stackNumber代表要进的栈号
         */
        public void push(int stackNumber,E e) {    
            if(top1+1==top2)
                throw new RuntimeException("栈已满，无法进栈！");
            if(stackNumber==1) {
                data[++top1]=e;        
            }else if(stackNumber==2) {
                data[--top2]=e;        
            }else {
                throw new RuntimeException("栈号错误！");
            }
     
        }
         
        /*
         * 出栈操作
         */
        public E pop(int stackNumber) {
            E e;
            if(stackNumber==1){
                if(top1==-1)
                    throw new RuntimeException("空栈1，无法出栈！");
                e=data[top1--];
            }else if(stackNumber==2) {
                if(top2==maxSize-1)
                    throw new RuntimeException("空栈2，无法出栈！");
                e=data[top2++];
            }else {
                throw new RuntimeException("栈号错误！");
            }
            return e;
        }  
    }

**3.栈的链式存储结构**

通过单向链表实现的栈，栈顶放在单链表的头部（注意进栈操作并不是往链表的后面插入，而是从头部插入）。

链栈的示意图如下。

![format_png 4][]

插入与删除操作示意图：

![format_png 5][]　　![format_png 6][]

实现程序：

/**
     *
     * 栈的链式存储结构
     *
     */
    public class LinkStack<E> {
        private StackNode<E> top;
        private int count;
         
        private class StackNode<E>{
            E data;
            StackNode<E> next;
            public StackNode(E data,StackNode<E> next) {
                this.data=data;
                this.next=next;
            }
        }
         
        public LinkStack() {
            top=new StackNode<E>(null, null);
            count=0;
        }
         
        public void push(E e) {
            StackNode<E> node=new StackNode<E>(e, top);
            top=node;
            count++;
        }
         
        public E pop() {
            if(count==0)
                throw new RuntimeException("空栈，无法出栈！");
            StackNode<E> node;
            node=top;
            top=top.next;
            count--;
            E e=node.data;
            node=null;
            return e;
        }
         
        public void printStack() {
            if(count==0) {
                System.out.println("空栈");          
            }else {
                StackNode<E> node=top;
                for(int i=0;i<count;i++) {
                    System.out.println(node.data);
                    node=node.next;
                }
            }      
        }
         
        /*
         * 测试代码
         */
        public static void main(String[] args) {
            LinkStack<Student> linkStack=new LinkStack<Student>();     
            Student[] students= {new Student("小A",11),new Student("小B",12),new Student("小C",13),
                    new Student("小D",14),new Student("小E",151)};
            for(int i=0;i<5;i++) {
                linkStack.push(students[i]);
            }
            linkStack.printStack();
            System.out.println("----");
            for(int i=0;i<5;i++) {
                System.out.println(linkStack.pop());
            }
            linkStack.printStack();    
        }
    }

**4.栈的应用**

（1）实现递归

一些问题（如斐波那契数列的求解），可通过递归函数获得，而递归函数是由栈来实现的。

![format_png 7][]

典型的斐波那契数列

（2）四则运算表达式求值

利用**后缀表达式（逆波兰表示法）**结合栈可以实现四则运算表达式的求解。而且通过栈，就可以把我们平时用的**中缀表达式**转化为后缀表达式。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIxNTM0NzkzNC04MTMyMTU3NDUucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIxNTM1MTkzOS0xMjE1NDI2NzMzLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIxNTgxNTY4OS0yMTQwMDE1NTY4LnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIyMDQ1NzExNC05MzA4MjI4OTAucG5n?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIyMTUxNDA1MS04OTA3NjUyNTYucG5n?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIyMTUxOTM3NC0xOTg3NDM1MTcxLnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIyMTUyOTcxOS00NDc1NzAwNTYucG5n?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNTIyMjExMTU0Mi03OTk4MTY5NzUucG5n?x-oss-process=image/format,png