瞭解堆棧數據結構和實現它

請看看下面的代碼瞭解堆棧數據結構和實現它

template <typename T> 

class Stack 
{ 
public: 
    Stack(int number) 
    { 
     maxSize = number; 
     top = -1; 
     stackData = new T*(maxSize); 
    } 

    ~Stack() 
    { 
     delete [] stackData; 
    } 

    int count() 
    { 

    } 

    bool isEmpty() 
    { 
     if(top==-1) 
     { 
      return true; 
     } 
     else 
     { 
      return false; 
     } 
    } 

    bool isFull() 
    { 
     if(top== (maxSize-1)) 
     { 
      return true; 
     } 
     else 
     { 
      return false; 
     } 
    } 

    *T pop() 
    { 
     if(!isEmpty()) 
     { 
      return stackData[top--]; // Remove Item From Stack 
     } 
    } 

    *T peek(); 

    void push(T *pushValue) 
    { 
     if(!isFull()) 
     { 
      stackData[++top] = pushValue; 
     } 
    } 

private: 
    int maxSize; 
    T ** stackData; 
    int top; 
};

在上面的代碼中，註釋行說，「從棧中刪除項目」。但實際上，這並不是消除，它只是提供了一個值的背後，對吧？在這裏，我指的是刪除從堆棧中徹底摧毀特定值。

ex：在包含數據1,2,3,4的數組中，刪除'2'。所以現在它是1,3,4

其次，在「peek（）」方法裏面會發生什麼？

三，有沒有我沒有發現的錯誤？

請幫忙！

來源

2013-02-07 Yohan Weerasinghe

從概念上說，減少top與「刪除」頂部項目之間沒有區別。「刪除」這個詞是一個概念抽象，用於描述堆棧中的頂層項目不再是堆棧中元素的想法。它不是從字面上從該位置在內存中刪除的事實是無關緊要的。

如果你的意思是要「消滅」前項目，即調用它的析構函數和釋放它，你需要考慮你的Stack類如何管理內存較大的影響。如果堆棧應該佔用每個對象的所有權，並且每個對象使用new已分配，則可以在減少top之前將pop()函數delete設置爲頂級項目。（但是pop()不能返回指向已刪除元素的指針）。如果堆棧不是取得每個項目的所有權，則由pop()的調用者來管理元素的生存期/取消分配。

接下來，peek()方法只是返回指向頂層項目的指針，而不將其從堆棧中移除。

最後，你沒有正確地分配T*指針的數組。語法應爲：

stackData = new T*[maxSize];

您發佈的代碼new，而不是括號後使用括號，這是不是你想要的這裏。

來源

2013-02-07 15:47:08

太好了。感謝您的幫助：） –

他們使用數組作爲堆棧。事實上，頂點指向堆棧中的頂層元素。所以，當你這樣做：

return stackData[top--];

頂部被降低，因此堆棧的大小確實下降。你真的彈出一個元素。

peek應該返回堆棧頂部的當前元素 - 找出如何爲自己做到這一點。

來源

2013-02-07 15:44:22

1）pop確實會彈出一個元素，但它會保留在數組中，直到將某個元素推到它的上面。但是你已經改變了top，所以堆棧不會「知道」它已經存在了。如果是複雜類型，則不會在pop上調用析構函數。

2）peek通常顯示堆棧的頂部而不彈出它。

3）您不驗證構造函數的number參數。

此外，您可以簡單地編寫isFUll(){ return (top== (maxSize-1));}。

來源

2013-02-07 15:47:43 AShelly

你確定這是正確引用：

stackData = new T*(maxSize);

豈不是：

stackData = new T*[maxSize];

你是正確的，pop方法不「破壞」的數據，它只是移動堆棧頂部到下一個位置（從頂部元素到頂部第二個元素）。我不知道你爲什麼想「從堆棧中摧毀特定的價值」......總的來說，這不會起到任何有意義的目的。

另外，你所描述的「在中間去除某些東西」並不是你通常用堆棧做的事情 - 這是一個列表，deque或類似的東西。

至於寫一個窺視功能，這將涉及幾乎相同的步驟，pop，除非你不動的top ...

來源

2013-02-07 15:47:52

的想法是，指數在每一個元素大於top是無效，而索引小於頂部的任何元素都是有效的。通過減少頂部你正在刪除一個元素，通過增加頂部你添加一個元素。

來源

2013-02-07 15:48:00 UmNyobe

瞭解堆棧數據結構和實現它

回答

相關問題