数据结构--栈的实现（顺序栈和链栈）

谁践踏了优雅 2021-08-14 00:41 517阅读 0赞

### 栈 ###

栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

### 栈的抽象数据类型 ###

package pers.zhang.stack;
    
    /** * @author zhang * @date 2020/1/16 - 14:05 * * 栈接口，描述栈的抽象数据类型，泛型参数T表示数据元素的数据类型 */
    public interface SStack<T> { 
        //判断栈是否为空
        boolean isEmpty();
        
        //元素x入栈
        void push(T x);
        
        //出栈，返回栈顶元素
        T pop();
        
        //取出栈顶元素，未出栈
        T get();
    }

### 栈的实现 ###

栈有两种基本的实现：

*  顺序栈：使用数组实现
 *  链栈：使用栈节点实现

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]

### 顺序栈 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]

package pers.zhang.stack;
    
    /** * @author zhang * @date 2020/1/16 - 14:12 * * 顺序栈，实现栈接口 */
    public class SeqStack<T> implements SStack<T> { 
    
        //存储栈数据元素的Object数组
        private Object element[];
    
        //栈顶元素下表
        private int top;
    
        //构造容量为size的栈
        public SeqStack(int size){ 
            this.element = new Object[Math.abs(size)];
            this.top = -1;
        }
    
        //默认构造，构造容量为64的空栈
        public SeqStack(){ 
            this(64);
        }
    
        //判断栈是否为空，若为空返回true
        @Override
        public boolean isEmpty() { 
            return this.top == -1;
        }
    
        //元素x入栈，空对象不操作
        @Override
        public void push(T x) { 
            if(x == null)
                return;
            if(this.top == element.length - 1){ //栈满，需要扩容
                Object[] temp = this.element;
                this.element = new Object[temp.length * 2];//重新申请一个2倍容量的数组
                for(int i = 0; i < temp.length; i++)//复制元素
                    this.element[i] = temp[i];
            }
            this.top++;//移动栈顶指针
            this.element[this.top] = x;//入栈
        }
    
        //出栈，返回栈顶元素，若栈空返回null
        @Override
        public T pop() { 
            return this.top == -1 ? null : (T) this.element[this.top--];
        }
    
        //取出栈顶元素，未出栈，若栈空返回null
        @Override
        public T get() { 
            return this.top == -1 ? null : (T) this.element[this.top];
        }
    
        //返回栈所有元素的描述字符串，形式为“(,)”，算法同顺序表
        @Override
        public String toString(){             
            String str = "(";
            if (this.top != -1)
                str += this.element[this.top].toString();
            for (int i= this.top - 1; i >= 0; i--)
                str += ", "+this.element[i].toString();
            return str + ") ";
        }
    }

### 链栈 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]

**节点类：**

public class Node<T> { 
        //数据域，保存数据元素
        public T data;
    
        //地址域，引用后继节点
        public Node<T> next;
    
        public Node(){ 
            this(null,null);
        }
    
        public Node(T data, Node<T> next){ 
            this.data = data;
            this.next = next;
        }
    
        public String toString(){ 
            return this.data.toString();
        }
    
        public boolean equals(Object obj){ 
            return obj == this || obj instanceof Node && this.data.equals(((Node<T>)obj).data);
        }
    
    }

**链栈的实现：**

package pers.zhang.stack;
    
    import pers.zhang.linearList.LinearList;
    import pers.zhang.linearList.Node;
    
    /** * @author zhang * @date 2020/1/16 - 14:28 * * 链栈，实现栈接口 */
    public class LinkedStack<T> implements SStack<T> { 
    
        //栈顶节点，同单链表节点一致
        private Node<T> top;
    
        //构造空栈
        public LinkedStack(){ 
            this.top = null;
        }
    
        //判断栈是否为空，若空返回true
        @Override
        public boolean isEmpty() { 
            return this.top == null;
        }
    
        //元素x入栈，空对象不操作
        @Override
        public void push(T x) { 
            if(x == null)
                return;
            this.top = new Node<>(x, this.top);//头插入，x节点作为新的栈顶
        }
    
        //出栈，返回栈顶元素，栈空返回null
        @Override
        public T pop() { 
            if(this.top == null)
                return null;
            T temp = this.top.data;//保存栈顶节点元素
            this.top = this.top.next;//删除栈顶节点
            return temp;
        }
    
        //取出栈顶元素，未出栈，空栈返回null
        @Override
        public T get() { 
            return this.top == null ? null : this.top.data;
        }
    
        //返回栈所有元素的描述字符串，形式为“(,)”。算法同不带头结点的单链表
        public String toString(){ 
            String str = "(";
            for (Node<T> p = this.top; p != null; p = p.next){ 
                str += p.data.toString();
                if (p.next != null)
                    str += ", ";//不是最后一个结点时后加分隔符
            }
            return str + ")";//空表返回()
        }
    }

### 测试 ###

package pers.zhang.stack;
    
    /** * @author zhang * @date 2020/1/16 - 14:36 */
    public class Stack_ex { 
        public static void main(String args[])
        { 
    /* SeqStack<String> stack = new SeqStack<String>(20); System.out.print("Push: "); char ch='a'; for(int i=0;i<5;i++) { String str = (char)(ch+i)+""; stack.push(str); System.out.print(str+" "); } */
            LinkedStack<Integer> stack = new LinkedStack<Integer>();
            System.out.print("Push: ");
            for (int i=1; i<=5; i++)
            { 
                Integer intobj = new Integer(i);
                stack.push(intobj);
                System.out.print(intobj+" ");
            }
    
            System.out.println("\nStack: "+stack.toString());
            System.out.print("Pop : ");
            while(!stack.isEmpty())                  //全部出栈
                System.out.print(stack.pop().toString()+" ");
            System.out.println();
        }
    }

输出如下：

Push: a  b  c  d  e  
    Stack: (e, d, c, b, a) 
    Pop : e  d  c  b  a  
    
    Push: 1  2  3  4  5  
    Stack: (5, 4, 3, 2, 1) 
    Pop : 5  4  3  2  1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/9c6f53ef534141b4a9116c5c86443950.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 1]: /images/20210813/c1d2242878414583b29a815c25374c18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 2]: /images/20210813/228878733ab242ffba142e1bcd291f2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 3]: /images/20210813/e6780abbc6f44a35b4e59d1ba285fe21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70 4]: /images/20210813/d1f9b62e5dce46dba72621955b7cb10a.png