• 中文
    • English
  • 注册
  • 查看作者
  • C++实现进栈,出栈的操作

    栈(stack)是一种特殊的线性表。

    举一个简单的例子,我们将3本书,三本书取名为123,并按照这个顺序依次放入收纳箱中

    取书的时候,最后放进去的3最先取出,第一个放进去的1最后取出

    也就是:后进栈的先出栈

    因为我们没法从收纳箱的底部放入书(除非你非要把收纳箱底部砸个洞)

    所以,其所有的插入和删除操作均是限定在线性表的一端进行的

    允许插入和删除的一端称栈顶(Top),不允许插入和删除的一端称栈底(Bottom)

    若给定一个栈S=(a, b,c……z),则称a为栈底元素,z为栈顶元素,元素b位于元素a之上

    栈中元素按a,b,c……z 的次序依次进栈

    并依次按照z,y,x……a 的次序依次出栈

    也就是说,栈中元素的进出是按后进先出的原则进行,这是栈结构的重要特征

    栈一般有两种的典型的存储表示,基于数组的存储表示和基于链表的存储表示

    这里以基于数组的表示为例

    #include<iostream>
    using namespace std;
    const int n = 10;//栈溢出的时候,用于扩展栈的大小
    class Stack
    {
    private :
        int *data;//存放栈里所有元素的数组
        int size;//栈里面最大可以容纳的元素个数
        int top;//栈顶的指针,表示最后加入的元素的存储位置
        bool overflow();//栈的溢出处理
    public:
        Stack(int sz = 3);//构造函数
        ~Stack();//析构函数
        bool push(int x);//进栈
        int pop();//出栈
        bool isEmpty();//判断栈是否为空
        bool isFull();//判断栈是否已满
        int getTop();//获得当前栈顶的指针
    
    };
    int Stack :: getTop()
    {
        return top ;
    }
    
    Stack :: Stack(int sz)
    {
        size = sz;
        data = new int[size];
        top = -1;
    }
    
    Stack :: ~Stack()
    {
        delete[] data;
    }
    
    bool Stack :: isEmpty()
    {
        return top == -1;
    }
    
    bool Stack :: isFull()
    {
    
        return top ==size - 1;
    }
    
    bool Stack :: overflow()
    {
        cout<< "大哥,我要扩充栈的空间了\n"<< endl;
        int *newData = new int [size + n];
        for(int i = 0; i <= top; i++)
        {
            newData[i] = data[i];
        }
        size += n;
        delete []data;
        data = newData;
    }
    bool Stack :: push(int x)
    {
        if(isFull())
        {
            cout << "大哥,栈慢了"<< endl;
            overflow();
        }
    
        data[++top] = x;
        cout << "将"<< x <<"存入栈,Top = " << top << endl;
        return true;
    }
    
    int Stack :: pop()
    {
        if(isEmpty())
        {
    
            cout << "大哥,我都被你榨干了"<< endl;
            return false;
        }
    
    
        return  data[top --];;
    }
    
    int  main()
    {
        int sz;
        int num;
        cout<< "请输入栈的大小"<< endl;
        cin >> sz ;
        Stack s(sz);
        for(int i = 0; i <= sz; i++) {// <= 是为了测试时溢出
        cout<< "请输入第" << i + 1<< "个数" << endl;
        cin >> num;
        s.push(num);
    }
      cout << "开始出栈啦"<< endl;
        int n = s.getTop() + 1;
        for(int i = 0; i < n ;i++) {
        cout << s.pop() ;
    }
    
    }
  • 0
  • 1
  • 0
  • 4.8k
  • 请登录之后再进行评论

    登录
  • 0
    XP0
    打赏了51金币。
  • 单栏布局 侧栏位置: