基於數組的棧實現

這裏是我的代碼，但有一個我無法理解的問題：每次當我在我的堆棧中推入一個整數時，剩餘的（未填充部分）堆棧將被0值填充。請解釋我的錯誤。基於數組的棧實現

#include <iostream> 
using namespace std; 

class Stack 
{ 
private: 
    int* base; 
    int max_size; 
    int top; 

public: 
    Stack(int size = 100) 
    { 
     base = new int[size]; 
     max_size = size; 
     top = -1; 
    } 
    ~Stack() 
    { 
     delete[] base; 
    } 
    bool empty() const 
    { 
     return top == -1; 
    } 

    bool full() const 
    { 
     return top == max_size - 1; 
    } 

    void push(int element) 
    { 
     if (top == max_size-1) { 
      cout<< "Stack overflow" << endl; 
      return; 
     } 
     base[++top] = element; 
    } 

    void pop() 
    { 
     if(top == -1) { 
      cout << "Stack underflow" << endl; 
      return; 
     } 
     top--; 
    } 

    int & read_top() const 
    { 
     return base[top]; 
    } 

    void print() 
    { 
     int i = 0 ; 
     cout << "Stack is "; 
     while(i <= max_size) 
     { 
      cout << base[i] <<" "; 
      i++; 
     } 
     cout << endl; 
    } 
}; 

int main() 
{ 
    Stack first(10); 
    for(int i = 0; i<=5; i++) 
    { 
     first.push(i*i); 
     first.print(); 
    } 
    return 0; 
}

來源

2016-09-28 Hayk Manukyan

你'print'顯示元素直至容量，而不是大小... – Jarod42

[OT]：你不要」尊重3/5/0規則。 – Jarod42

我跑了你的代碼，開始時堆滿了垃圾，還有未填充的部分在推後被垃圾填滿。 @ Jarod42是對的，你應該改變你的循環打印相關部分。但是你的代碼沒有問題，並且未填充的部分在我的機器中沒有零... – nrofis

-2

我不太確定我是否正確地回答您的問題：「每當我在堆棧中推送一個整數」時，您的意思是什麼？據我所知，你初始化你的堆棧，然後做一些推動，而不改變它們之間的未定數組。這裏發生的事情是你的數組被初始化爲0（不要指望你的編譯器每次都這樣做，但這次它確實 - 很可能你沒有進行優化編譯），然後添加單個元素，並且已經有人回答是，你不僅僅打印你的堆棧（也就是從0到頂部），而是整個未定義的數組。如果編譯優化，你可能會得到垃圾值而不是零（數組未初始化爲構造函數中的某些初始值，未分配的值可能包含任何值）。希望能幫助到你。

在代碼中的錯誤：在print()方法，你應該有while(i < max_size)

來源

2016-09-28 08:15:52 gmoruz

考慮重新形成你的答案聽起來更像是一個答案，而不是像一個持續的問答論壇帖子 – bolov

非常感謝你的優秀解釋 –

考慮：

Stack s(10); 
for(int i = 0; i<=5; i++) 
    s.push(i);

在print您有：

std::cout << "Stack is "; 
while(i <= max_size) 
    std::cout << base[i] << ' ';

在上述情況下

，s.max_size是10，所以你打算打印base [0,10）的值，其中5個是未初始化的。由於該應用程序在內存方面沒有做太多的工作，因此在執行分配時，您可能會得到一個原始（歸零）內存塊。

你的代碼的可能的變化：

#include <iostream> 
// using namespace std ; // unlearn the habbit of doing this. 
#include <memory> // for unique_ptr 

class Stack 
{ 
    // note: class is private by default. 
     // unique_ptr will automatically free memory for us. 
     using ptr_t = std::unique_ptr<int[]>; 

     ptr_t base_; 
     int* top_; 
     int* end_; 

    public : 
     Stack(int size=100) 
      : base_(new int[size]) 
      , top_(base_.get()) 
      , end_(top_ + size) 
     {} 

     bool empty() const 
     { return top_ == base_.get(); } 

     bool full() const 
     { return top_ == end_; } 

     // don't print errors from a library 
     bool push(int value) 
     { 
      if (full()) // written in terms of our own members 
       return false; 
      *(top_++) = value; 
      return true; 
     } 

     bool pop() 
     { 
      if (empty()) // written in terms of our own members 
       return false; 
      --top_; 
      return true; 
     } 

     const int& read_top() const // const ref so it's not modifiable 
     { return *(top_-1); } 

     int size() const { return end_ - top_; } 
     int capacity() const { return end_ - base_.get(); } 

     std::ostream& print(std::ostream& to) 
     { 
      to << "Stack is "; 
      for (int* ptr = base_.get(); ptr != top_; ++ptr) 
       to << *ptr << ' '; 
      to << '\n'; 
      return to; 
     } 

     // or we could do this: 
     friend std::ostream& operator << (std::ostream& to, const Stack& s) 
     { 
      to << '['; 
      for (int* ptr = s.base_.get(); ptr != s.top_; ++ptr) { 
       to << *ptr << ','; 
      } 
      return to << ']'; 
     } 
}; 

int main() 
{ 
    Stack s(5); 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    s.print(std::cout); 
    std::cout << "stack is: " << s << '\n'; 
}

現場演示：http://ideone.com/JsA4EU

來源

2016-09-28 08:24:54 kfsone

基於數組的棧實現

回答

相關問題