用链表代码实现栈

深碍√TFBOYSˉ_ 2024-03-31 17:27 76阅读 0赞

## 定义 ##

> 栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出  
> 的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一  
> 个数据被第一个读出来）。  
> 我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

![在这里插入图片描述][2ebaed9bd33a48adb85a6e1a629a56a6.png]

## API设计 ##

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>Stack</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法Stack)：</td> 
   <td>创建Stack对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td>1.public boolean isEmpty()：判断栈是否为空，是返回true，否返回fals 2.public int size():获取栈中元素的个数3.public T pop():弹出栈顶元素4.public void push(T t)：向栈中压入元素t</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td>1.private Node head:记录首结点 2.private int N:当前栈的元素个数</td> 
  </tr> 
 </tbody> 
</table>

## 代码实现 ##

package practise7;
    
    import java.util.Iterator;
    
    public class Stack<T> implements Iterable<T>{
        
        // 定义一个泛型的Stack类，实现Iterable接口
    
        public static void main(String[] args) throws Exception{
        
            Stack<String> stack = new Stack<>();
            // 创建一个可以保存String类型元素的Stack实例
    
            stack.push("a");
            stack.push("b");
            stack.push("c");
            // 向栈中添加三个元素
    
            for(String str :stack){
        
                System.out.println(str+"");
            }
            // 遍历栈中的元素并输出
    
            System.out.println("-----------------");
    
            String result = stack.pop();
            // 从栈中弹出顶部元素并存入result变量
    
            System.out.println("弹出了元素"+result);
            // 输出弹出的元素
    
            System.out.println(stack.size());
            // 输出栈的大小
        }
    
        private class Node{
        
            // 定义一个内部类Node，表示链表中的一个节点
    
            public T item;
            // 节点中存储的元素
    
            public Node next;
            // 指向链表中下一个节点的引用
    
            public Node (T item, Node next){
        
                this.item =item;
                this.next= next;
            }
        }
    
        @Override
        public Iterator<T> iterator(){
        
            // 实现Iterable接口中的iterator()方法
            // 返回内部类SIterator的实例，允许遍历栈中的元素
            return new SIterator();
        }
    
        private class SIterator implements  Iterator<T>{
        
            // 定义内部类SIterator，实现Iterator接口
    
            private Node n =head;
            // 将当前节点初始化为链表的头部
    
            @Override
            public boolean hasNext(){
        
                // 实现Iterator接口中的hasNext()方法
                // 如果栈中还有其他元素，返回true
                return n.next!=null;
            }
    
            @Override
            public  T next(){
        
                // 实现Iterator接口中的next()方法
                // 返回栈中的下一个元素
                Node node = n.next;
                n=n.next;
                return node.item;
            }
        }
        private Node head;
        // 栈中元素的链表的头节点
        private int N;
        // 栈中元素的数量
        public Stack(){
        
        // 构造函数
        // 初始化链表的头节点和栈的大小为0
    	    head = new Node(null,null);
    	    N=0;
        }
        public boolean isEmpty(){
        
            // 如果栈为空，返回true
            return N==0;
    
        }
        public void push(T t){
        
            // 向栈中添加一个新元素
            // 在链表头部添加一个新节点
            Node oldNext = head.next;
            Node node = new Node(t,oldNext);
            head.next= node;
            N++;
        }
        public T pop(){
        
            // 从栈中弹出顶部元素
            // 从链表头部删除节点
            Node oldNext = head.next;
            if(oldNext == null){
        
                return null;
            }
            head.next= head.next.next;
            N--;
            return oldNext.item;
        }
        public int size(){
        
            // 返回栈中元素的数量
            return N;
        }
    }

## 运行结果 ##

c
    b
    a
    -----------------
    弹出了元素c
    2

[2ebaed9bd33a48adb85a6e1a629a56a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d7ef4a7829ea4ba8a4ee6876aac41058.png