c++ - 堆栈实现

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:返回值，自增迭代器。
计数:在堆栈上不是标准的，但是你可以通过从结束中减去当前迭代器来得到它。
窥视:返回值

显然，您想要确保您没有从阵列的前面推开，或者从后面弹出，所以您应该添加一些检查。

堆栈非常简单。希望这会有所帮助。

编辑:实现，前面未经测试的代码，有点思路

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;
}