Stack & Queue 棧和隊列的學習筆記

peixn 發布于2019-08-14 17:12 / 3034人閱讀

摘要：的前部分內容講的是棧和隊列的實現。學習環境在學習這門課之前，先引入的概念，即抽象數據類型。鏈表實現學習，鏈表實現簡單的數組實現鏈表實現簡單的數組實現解決使用棧或者隊列時，的數據類型指定問題。

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語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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