栈

一、堆栈（链表实现）

堆栈.jpg

这种栈只有一个入口，它也是出口。从入口把数据放进去，取的时候只能取出最上面的数据。了解了数据结构，在看来代码就很简单了。

/**
 * 把元素放到栈顶，然后每次从栈顶取元素
 */
class Stack {
    //他有两个成员变量  一个是size N   一个是first 节点

    private var N  = 0;
    private var first : Node? = null;

     class Node(var content: String, var next : Node?)

    //压站
    fun pop(content : String){
       //这里其实可以专门写个添加first的方法，然后做判断的
        if (first == null){
            first = Node(content,null)
            return
        }
        val olderFirst = first
        first = Node(content, olderFirst)
        N++
    }

    //出栈
    fun push() : String?{
        val content = first?.content
        first = first?.next
        N--
        return content
    }
   //栈是否为空
   fun isEmpty() : Boolean{
        return first == null
    }

    fun getSize() : Int{
        return N
    }

}

写了一个最简易的栈，看下如何使用

        var stack = Stack()
       //压栈
        stack.pop("1")
        stack.pop("2")
        stack.pop("3")
        stack.pop("4")
        stack.pop("5")
        stack.pop("6")

      //其实可以在Stack里面写个迭代器，迭代打印。不会的可以看下面例子的代码
        for (i in 0 .. stack.getSize()){
            //出栈
            Log.d("azy",stack.push())
        }

打印结果

2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 6
2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 5
2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 4
2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 3
2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 2
2020-06-14 15:24:48.034 6075-6075/com.example.kotlindemo D/azy: 1

总结：先压栈的最后出来

I get it.jpeg

二、队列(链表实现)

队列.jpg

如上图，从队尾插入数据，从队头取数据。这样保存的数据，插入的顺序和取出来的顺序是一样的。

来个最简单的实现

**
 * 需要一个头节点来出队列
 * 需要一个尾节点来进队列
 * 需要一个队列的长度
 *
 */
class Queue  : Iterable<String>{
    class Node(var  content : String,var  next : Node?)
    private var first : Node? = null
    private var last : Node? = null
    private var N : Int = 0

    fun isEmpty() : Boolean{
        return first == null
    }

    fun getSize() : Int{
        return N;
    }

    //进栈
    fun enqueue( content : String){
        //从队尾添加元素
        var oldLast = last;
        last = Node(content,null)
        if (isEmpty()){
            first = last
        }else
        oldLast?.next = last
        N++
    }
    //出栈
   fun dequeue() : String?{
        var item = first?.content
        first = first?.next
        if (isEmpty()){
           last = null
        }
        N++
        return item
    }

   override fun iterator(): Iterator<String> {
        return ListIterator()
    }

    inner class ListIterator : Iterator<String> {
        private var current = first
        override fun hasNext(): Boolean {
            return current == null
        }


        override fun next(): String {
                var content = current?.content
                current = current?.next
                //这个迭代器不知道为什么不能使用String？ 所以这里转换了一下
                return  content ?: "" 
        }
    }

}

如何使用？

 var queue = Queue()
        queue.enqueue("1")
        queue.enqueue("2")
        queue.enqueue("3")
        queue.enqueue("4")
        queue.enqueue("5")
        queue.enqueue("6")

        for (i in 0 .. queue.getSize()){
            Log.d("azy",queue.dequeue())
        }

打印结果

2020-06-21 10:47:16.356 7529-7529/com.example.kotlindemo D/azy: 1
2020-06-21 10:47:16.356 7529-7529/com.example.kotlindemo D/azy: 2
2020-06-21 10:47:16.356 7529-7529/com.example.kotlindemo D/azy: 3
2020-06-21 10:47:16.357 7529-7529/com.example.kotlindemo D/azy: 4
2020-06-21 10:47:16.357 7529-7529/com.example.kotlindemo D/azy: 5
2020-06-21 10:47:16.357 7529-7529/com.example.kotlindemo D/azy: 6

总结一下：根据堆栈和队列的打印结果，不难看出，堆栈是存入和取出的顺序是相反的，而队列存入和取出的顺序是相同的。

这是讨论啥呢.jpeg