算法练习(39): 以栈为目标的队列Steque(1.3.32)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 链表节点增删查改
• 环形链表

题目

1.3.32 Steque。一个以栈为目标的队列（或称steque），是一种支持push、pop和enqueue操作的数据类型。为这种抽象数据类型定义一份API并给出一份基于链表的实现。

---

1.3.32 Steque. A stack-ended queue or steque is a data type that supports push, pop, and enqueue. Articulate an API for this ADT. Develop a linked-list-based implementation.

答案

public class Steque<Item> implements Iterable<Item>{

    private class Node {
        Node next;
        Item item;
    }

    private Node first;
    private Node last;
    
    public void push(Item x){
        Node node = new Node();
        node.item = x;
        if (this.isEmpty()) {
            first = node;
            last = node;
        }else{
            node.next = first;
            first = node;
        }
    }
    
    public Item pop(){
        if (this.isEmpty()) {
            return null;
        }
        Item item = first.item;
        first = first.next;
        return item;
    }
    
    public void enqueue(Item x){
        Node node = new Node();
        node.item = x;
        if (this.isEmpty()) {
            first = node;
            last = node;
        }else{
            last.next = node;
            last = node;
        }
    }
    
    public boolean isEmpty(){
        return first == null;
    }
    
    
    public Iterator<Item> iterator()  
    {  
        return new StequeIterator();  
    }  
      
    private class StequeIterator implements Iterator<Item>  
    {  
        private Node current = first;  
        
        public boolean hasNext()  
        {  
            return current != null;  
        }  
          
        public Item next()  
        {  
            Item x = current.item;  
            current = current.next;  
            return x;  
        }  
    } 
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Steque<String> stringSteque1 = new Steque<String>();
        stringSteque1.enqueue("我");
        stringSteque1.enqueue("的");
        stringSteque1.enqueue("名字");
        stringSteque1.enqueue("叫顶级程序员不穿女装");
        stringSteque1.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
        
        for (String string : stringSteque1) {
            System.out.println(string);
        }
        
        Steque<String> stringSteque2 = new Steque<String>();
        stringSteque2.push("我");
        stringSteque2.push("的");
        stringSteque2.push("名字");
        stringSteque2.push("叫顶级程序员不穿女装");
        stringSteque2.push("微博:https://m.weibo.cn/p/1005056186766482");
        
        for (String string : stringSteque2) {
            System.out.println(string);
        }
        
    }

}

代码索引

Steque.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。