Stack & Queue 栈和队列的学习笔记

peixn 发布于2019-08-14 17:12 / 3033人阅读

摘要：的前部分内容讲的是栈和队列的实现。学习环境在学习这门课之前，先引入的概念，即抽象数据类型。链表实现学习，链表实现简单的数组实现链表实现简单的数组实现解决使用栈或者队列时，的数据类型指定问题。

Week2 的前部分内容讲的是栈和队列的Java实现。
学习环境：mac, inteliJ, java version "1.8.0_77"

在学习这门课之前，先引入Abstract Data Types(ABT)的概念，即抽象数据类型。ABT将operators封装起来，例如pop,push,这样使用者就不必深入了解技术细节，而是更多关注与解决问题本身。

1 Stacks 1.1 链表实现

/**
 * 学习stack，链表实现
 * Created by susu on 17/1/9.
 */
public class LinkStackTest {
    private Node first = null;
    private class Node
    {
        String item;
        Node next;
    }

    public boolean isEmpty()
    {
        return first == null;
    }

    public void push(String item)
    {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public String pop()
    {
        String item = first.item;
        first = first.next;
        return item;
    }
}

1.2 简单的数组实现 2 Resizing Arrays 3 Queues 3.1 链表实现 3.2 简单的数组实现 4 Generics

解决使用栈或者队列时，item 的数据类型指定问题。例如在基础的class中指定了 String item; 那么在其他地方每次使用时，要么复制代码修改类型，要么强制转换。问题是，强制转换是在用户使用端进行转换，报错了的话是无法监测到的，所以可以在链表实现中修改成generics。

note:数组很难实现generics.

/**
 * Generic stack: linked-list implementation
 * Created by susu on 17/1/10.
 */
public class Stack {
    private Node first = null;

    private class Node
    {
        Item item;
        Node next;
    }

    public boolean isEmpty()
    { return first == null; }

    public void push(Item item)
    {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public Item pop()
    {
        Item item = first.item;
        first = first.next;
        return item;
    }
}

5 Iterators

Iteration，迭代器，解决的问题是，使得client 端口在使用stack等数据结构时，能够遍历集合中的元素，而不必要知道我是用数组还是链表实现的。

Iterable，Java的可遍历类，接口,has a method that returns an iterator.
Iterable Interface

public interface Iterable
{
    Iterator Iterator();
}

Iterators has methods hasNext(),next()
Iterator Interface

public interface Iterator
{
    Boolean hasNext();
    Item next();
    void remove();//教授认为这不是一个好method,可能成为调试隐患
}

for-each statement

for (String s : Stack)
    StdOut.println(s);

Stack Iterator: 链表实现

/**
 * Generic stack: linked-list implementation
 * Created by susu on 17/1/10.
 */
import java.util.Iterator;
import java.util.ListIterator;

public class Stack implements Iterable{
    private Node first = null;

    private class Node
    {
        Item item;
        Node next;
    }

    public boolean isEmpty()
    { return first == null; }

    public void push(Item item)
    {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public Item pop()
    {
        Item item = first.item;
        first = first.next;
        return item;
    }
    
    public Iterator iterator()
    { return new ListIterator()}
    
    private class ListIterator implements Iterator
    {
        private Node current = first;
        
        public boolean hasNext() { return current != null; }
        public void remove { /* not supported */ }
        public Item next()
        {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

6 Stack and Queue Application 7 作业

作业描述

GPU云服务器云服务器栈和队列的c语言栈和队列面试题队列queue 栈和队列 c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66488.html

学习javascript数据结构(一)——栈和队列

摘要：原文地址学习数据结构一栈和队列博主博客地址的个人博客几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。他们就是栈和队列。我们称作栈顶，而另一端我们称作栈底。移除栈顶的元素，同时返回被移除元素。前言只要你不计较得失，人生还有什么不能想法子克服的。原文地址：学习javascript数据结构(一)——栈和队列博主博客地址：Damonare的个人博客几乎所有的编程...

doodlewind 2019-08-21 14:42 评论0 收藏0
【Java实现】栈和队列就是这么简单

摘要：一前言上一篇已经讲过了链表实现单向链表了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦，如果有更好的理解的方式也希望能够在评论下留言，让大家学习学习二数据结构栈就是这么简单数据结构一、前言上一篇已经讲过了链表【Java实现单向链表】了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用：栈和队列如果写错的地方希望大家...

Ethan815 2019-08-16 11:09 评论0 收藏0
JS数据结构与算法_栈&amp;队列

摘要：下一篇数据结构与算法链表写在前面说明数据结构与算法系列文章的代码和示例均可在此找到原计划是把你不知道的三部全部看完的，偶然间朋友推荐了数据结构与算法的一套入门视频，学之。手头上恰好有学习数据结构与算法的书籍，便转而先把数据结构与算法学习。下一篇：JS数据结构与算法_链表写在前面说明：JS数据结构与算法系列文章的代码和示例均可在此找到原计划是把《你不知道的Javascript》...

AndroidTraveler 2019-08-23 14:45 评论0 收藏0
LeetCode 232：用栈实现队列 Implement Queue using Stacks

摘要：题目使用栈实现队列的下列操作将一个元素放入队列的尾部。用栈实现队列，可以用两个栈完成题解。入队列时用存入节点，出队列时内节点顺序出栈压入中。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队...

cloud 2019-08-19 10:26 评论0 收藏0
LeetCode 225：用队列实现栈 Implement Stack using Queues

摘要：下面是入栈时代码获得队列长度反转次数为队列长度减一反转语言没有栈和队列数据结构，只能用数组或双端队列实现。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Impl...

AlanKeene 2019-08-19 10:28 评论0 收藏0