c++ - スタックの実装

Question

プッシュとポップがスタックでどのように機能するか理解できません。たとえば、数字をスタックにプッシュすると、最後にプッシュされた数字がポップオフされるため、それらがどのように機能するかを理解しています。また、ポインターの背後にあるロジックとそのしくみも理解しています。私が理解していないのは、コードがどのように書かれるべきかということです。

私のプログラムは、ユーザーがスタックを作成し (サイズを決定)、スタックにメモリ (数値) をプッシュするか、ポップオフするかを選択できるようにすることになっています。

これが私がこれまでに得たもので、行き詰まっています。私は 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。イテレータを作成します。iterator を配列の末尾に設定します。(終わりの意味array.end())

プッシュ: イテレータをデクリメントし、値を挿入します。
Pop: 戻り値、インクリメント イテレータ。
カウント: スタックでは標準ではありませんが、現在の反復子を end から減算することで取得できます。
ピーク: 戻り値

明らかに、配列の前面を押したり、背面から飛び出したりしていないことを確認したいので、いくつかのチェックを追加する必要があります。

スタックは実にシンプルです。お役に立てれば。

編集：実装、テストされていないコード先、ちょっとした思考の流れ

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

このコードは 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