堆栈实现

Question

我无法理解push和pop如何与堆栈一起工作。我明白他们是如何工作的，因为他们推动一个号码让我们说到堆栈上，并且推出的最后一个号码将被弹出。我也理解指针背后的逻辑以及它们如何工作。我不明白的是代码应该如何编写。

我的程序应该让用户创建一个堆栈（确定它的大小），然后选择将堆栈中的内存（数字）推出或弹出。

这是我到目前为止，我卡住了。我已经通过cplusplus.com进行了研究，并阅读了关于这些东西的几乎所有内容，但仍然无法弄清楚该程序应该如何布置以及如何运行。

#include<iostream> 
#include<cstring> 
#include<cmath> 
#include<cstdlib> 

using namespace std; 

int choice; 
int * arrPtr = NULL; 
int * stack; 
int * top; 
int val, capacity, size; 
//stack would point to the location of the first element, 
// top would point to the location where the next element will be stored, 
// capacity is the number of elements that can be stored in the stack, 
// size would be the number of elements actually stored in the stack 

int main() 
{ 
//This is the menu 
cout << "1. Create" << endl; 
cout << "2. Push" << endl; 
cout << "3. Pop" << endl; 
cout << "4. Count" << endl; 
cout << "5. Display" << endl; 
cout << "6. Exit\n" << endl; 
cin >> choice; 

//I figured i would use choices for the menu and went ahead and wrote it out 
switch(choice) 
{ 
    case 1: 
     create(); 
     break; 
    case 2: 
     push(); 
     break; 
    case 3: 
     pop(); 
     break; 
    case 4: 
     count(0); 
     break; 
    case 5: 
     display(); 
     break; 
    case 6: 
     exit(); 
    default: 
     cout << "Please enter correct choice (1-4)!"; 
     break; 
    } 

    return 0; 
} //end main 

void create() 
{ 
    cout << "Enter the size of the stack you wish to create: "; 
    int capacity = 0; 
    cin >> capacity; 

    arrPtr = new int[capacity]; 
} //end create function 

//From here it went wrong, I cannot figure it out.   

void push(){ 
    for (int i = 0; i < capacity; i++) 
    { 
     cout << "Enter the number you wish to put on the stack: "; 
     cin >> val; 
     push(val) 
    }//end for 
}//end push 

请帮我理解这一点。

Answer 1

创建std::array。创建迭代器。将迭代器设置为数组的末尾。 （结尾含义array.end()）

推送：递减迭代器，插入值。
Pop：返回值，递增迭代器。
计数：堆栈上不是标准的，但你可以从最后减去当前的迭代器得到它。
Peek：返回值

很明显，您要确保不会推开阵列前面或弹出后面，所以应该添加一些检查。

堆栈非常简单。希望这可以帮助。

编辑：这

template <typename T, std::size_t N> 
class Stack { 
public: 
    Stack(); 
    void push(T value); 
    T pop(); 
    T peek() const; 
    std::size_t count() const; 

private: 
    std::array<T, N> m_baseArray; 
    std::array<T>::iterator m_it; 
}; 

template <typename T, std::size_t N> 
Stack::Stack() : m_baseArray(), m_it(m_baseArray.end()) { } 

template <typename T, std::size_t N> 
void Stack::push(T value) { 
    if (m_it == m_baseArray.begin()) 
    throw std::exception(); 
    --m_it; 
    *m_it = value; 
} 

template <typename T, std::size_t N> 
T Stack::pop() { 
    if (m_it == m_baseArray.end()) 
    throw std::exception(); 
    T res = *m_it; 
    ++m_it; 
    return res; 
} 

template <typename T, std::size_t N> 
T Stack::peek() const { 
    if (m_it == m_baseArray.end()) 
    throw std::exception(); 
    return *m_it; 
} 

template <typename T, std::size_t N> 
std::size_t Stack::count() const { 
    return m_baseArray.end() - m_it; 
} 

Answer 2

使用std::vector

#include <iostream> 
#include <vector> 
using namespace std; 

template<typename T> 
class Stack{ 
private: 
    vector<T> theArray; 
public: 
    Stack(){ theArray.clear(); } 
    void push(T data) { theArray.push_back(data); } 
    T pop() { T retData = theArray.back(); theArray.pop_back(); return retData; } 
    void display() { 
    for(size_t i = theArray.size() - 1; i != (size_t)-1; i--){ 
     cout << theArray[i] << '\n'; 
    } 
    } 
}; 

int main(int argc, char *argv[]) 
{ 
    Stack<int> s; 
    s.push(10); 
    s.push(20); 
    s.push(30); 
    s.display(); 

    int ret = s.pop(); 
    cout << "After popping : " << ret << '\n'; 
    s.display(); 
    return 0; 
} 

Answer 3

最简单的栈实现，提前未经测试的代码，还挺thought'ing流的，我编在Mac上这个代码，但它应该工作在装有bash的PC上的Linux上正常运行。

#include<iostream> 
#include<cstring> 
#include<cmath> 
#include<cstdlib> 

using namespace std; 

int choice; 
int capacity; /*size of stack*/ 

int stack[1000];/*THIS IS WHERE ALL THE STACK ENTRIES WILL BE STORED*/ 
int top=0; /* THIS WILL KEEP CHECK OF THE INDEX OF TOP MOST ELEMENT */ 

//stack would point to the location of the first element, 
// top would point to the location where the next element will be stored, 
// capacity is the number of elements that can be stored in the stack, 
// size would be the number of elements actually stored in the stack 

void create() //Set size of stack 
{ 
    cout << "Enter the size of the stack you wish to create: "; 
    cin >> capacity; 

} //end create function 


void push(int n) //Enter data into stack 

{ 

/* Ensures that there isn't a stack overflow */ 

    if(top<capacity) 
    { 
     stack[top++]=n; 
    } 


    else 
    { 
     cout<<"Stack FULL!!\n"; 
    } 

    //end for 
}//end push 

void pop() //Remove data from stack 
{ 
    /* Ensures that there isn't a stack underflow */ 
    if(top>0) 
    { 
     cout<<"Popped entry is:"<<stack[top-1]<<"\n"; 
     top--; 
    } 

    else 
    { 
     cout<<"Stack is EMPTY!!\n"; 
    } 


} 

void count() //Count number of elements 
{ 
    cout<<"Stack size is:"<<top<<"\n"; 
} 

void display() //Print elements from lowest stack entry to highest 
{ 
    int i=0; 
    cout<<"Your stack is:\n"; 
    while(i<top) 
    { 
     cout<<i+1<<") "<<stack[i]<<"\n"; 
     i++; 
    } 
} 



int main() 
{ 
    system("clear"); //Start with blank screen 



    int exitCheck=1,entry; 

    //I figured i would use choices for the menu and went ahead and wrote it out -- This is good approach!! 
    cout<<"Welcome user \n"; 

    create(); /*Size of stack can be set only once to prevent inconsistency */ 

    while(exitCheck == 1) /* This is the menu */ 
    { 

     cout << "1. Push" << endl; 
     cout << "2. Pop" << endl; 
     cout << "3. Count" << endl; 
     cout << "4. Display" << endl; 
     cout << "5. Exit\n" << endl; 
     cin >> choice; //Choice should be placed here as we need userinput during each turn 

     switch(choice) 
     { 
      case 1: 
       cout<< "Enter your data: "; 
       cin>>entry; 
       push(entry); 
       break; 
      case 2: 
       pop(); 
       break; 
      case 3: 
       count(); 
       break; 
      case 4: 
       display(); 
       break; 
      case 5: 
       { 
        exitCheck=1; 
        break; 
       } /*exit in this case wont achieve a proper result in a concole based app thats why i replaced it with loop exit condition */ 

      default: 
       cout << "Please enter correct choice (1-5)!\n"; 
       break; 
      } 

     cout<< "Enter 1 to continue else anything else to quit:\n"; 
     cin>> exitCheck; 


    } 

    cout<<"Thanks for using this code!!\n";  
return 0; 
} 
    //end main