栈类(C++)

GeekLiHua

发布于 2025-01-21 12:16:46

7600

代码可运行

文章被收录于专栏：Java

运行总次数：0

代码可运行

用C++实现栈

简介：通过题目的方式来介绍如何通过C++实现栈，通过理解栈的底层原理，来更好的学习这个数据结构题目

请设计通用栈类。

首先定义数据元素类型

typedef double ELEMENT; 然后定义栈

class STACK
{
public:
    STACK();
    ~STACK();
    bool Push(const ELEMENT &value);
    bool Pop(ELEMENT &value);
    bool Clear();
    bool Empty() const;
    int Length() const;

    const static int stackSize;

private:
    int size, top;
    ELEMENT *element;
};

const int STACK::stackSize = 5;

说明：

size 为动态数组的尺寸，top 为栈顶元素的下标，element 为动态数组的起始地址。
stackSize 为动态数组的尺寸，初始值为 5。
构造函数：初始化栈：将初始尺寸保存到 size，将栈顶下标 top 置为 -1，为动态数组分配内存并将起始地址保存到 element。
析构函数：清理栈：释放动态数组的内存。
Push 函数：若栈未满，则将元素 value 保存到栈中，函数值为 true；否则报告上溢错误，函数值为 false。
Pop 函数：若栈不空，则从栈中取出元素并保存到 value中，函数值为 true；否则报告下溢错误，函数值为 false。
Clear 函数：清空栈，操作成功，函数值为 true。
Empty 函数：若栈空，则函数值为 true，否则为 false。
Length 函数：函数值为栈中元素的数量。 裁判程序

#include <iostream>
#include <iomanip>
using namespace std;
#include <cctype>

typedef double ELEMENT;

class STACK
{
public:
    STACK();
    ~STACK();
    bool Push(const ELEMENT &value);
    bool Pop(ELEMENT &value);
    bool Clear();
    bool Empty() const;
    int Length() const;

    const static int stackSize;

private:
    int size, top;
    ELEMENT *element;
};

const int STACK::stackSize = 5;

/* 你提交的代码将被嵌在这里 */

int main()
{
    STACK stack;
    ELEMENT value;
    char choice;
    do
    {
        cout << "Push pOp Clear Empty Length Quit > ";
        cin >> choice;
        choice = toupper(choice);
        
        switch (choice)
        {
        case 'P':
            cout << "Value: ";
            cin >> value;
            if (stack.Push(value))
            {
                cout << "Push successfully!\n";
            }
            else
            {
                cout << "Push failed!\n";
            }
            break;
        case 'O':
            if (stack.Pop(value))
            {
                cout << "Pop successfully!\n";
                cout << "Value: " << value << endl;
            }
            else
            {
                cout << "Pop failed!\n";
            }
            break;
        case 'C':
            if (stack.Clear())
            {
                cout << "Clear successfully!\n";
            }
            else
            {
                cout << "Clear failed!\n";
            }
            break;
        case 'E':
            if (stack.Empty())
            {
                cout << "Stack is empty!\n";
            }
            else
            {
                cout << "Stack is not empty!\n";
            }
            break;
        case 'L':
            cout << "Stack length: " << stack.Length() << endl;
            break;
        case 'Q':
            break;
        default:
            cout << "Incorrect choice!\n";
        }
    }
    while (choice != 'Q');
}

测试样例1

Push pOp Clear Empty Length Quit > t
Incorrect choice!
Push pOp Clear Empty Length Quit > K
Incorrect choice!
Push pOp Clear Empty Length Quit > Q

测试样例2

Push pOp Clear Empty Length Quit > L
Stack length: 0
Push pOp Clear Empty Length Quit > e
Stack is empty!
Push pOp Clear Empty Length Quit > P
Value: 4.5
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 1.6
Push successfully!
Push pOp Clear Empty Length Quit > l
Stack length: 2
Push pOp Clear Empty Length Quit > E
Stack is not empty!
Push pOp Clear Empty Length Quit > o
Pop successfully!
Value: 1.6
Push pOp Clear Empty Length Quit > O
Pop successfully!
Value: 4.5
Push pOp Clear Empty Length Quit > O
Stack underflow!
Pop failed!
Push pOp Clear Empty Length Quit > q

测试样例3

Push pOp Clear Empty Length Quit > p
Value: 0.5
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 1.7
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 2.8
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 3.6
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 4.9
Push successfully!
Push pOp Clear Empty Length Quit > p
Value: 9.9
Stack overflow!
Push failed!
Push pOp Clear Empty Length Quit > L
Stack length: 5
Push pOp Clear Empty Length Quit > e
Stack is not empty!
Push pOp Clear Empty Length Quit > C
Clear successfully!
Push pOp Clear Empty Length Quit > l
Stack length: 0
Push pOp Clear Empty Length Quit > E
Stack is empty!
Push pOp Clear Empty Length Quit > p
Value: 8.5
Push successfully!
Push pOp Clear Empty Length Quit > O
Pop successfully!
Value: 8.5
Push pOp Clear Empty Length Quit > q

输出样例 Push pOp Clear Empty Length Quit >

输入样例 q

代码长度限
16 KB
时间限制
400 ms
内存限制
64 MB

题解：

STACK::STACK()
{
	size = stackSize;
	top = -1;
	element = new ELEMENT[size];      // 这里是c++程序 所以不能使用C语言的malloc和free函数因为new函数是每个元素都要构造的 但是malloc不会
}

STACK::~STACK()
{
	delete []element; // 释放资源
}
bool STACK::Push(const ELEMENT &value)
{
    if (top + 1 >= this->size) // 首先判断一下是否栈满了
    {
        cout << "Stack overflow!\n"; // 如果栈满了就需要输出Stack overflow!
        return false ; // 返回入栈失败
    }
    this->element[++top] = value; // 反之插入栈顶
    return true;
}
int STACK::Length() const // 因为初始值是top = -1所以返回长度的时候需要top+1
{
    return top + 1;
}

bool STACK::Pop(ELEMENT &value)
{
    if (top == -1) // 先判断栈是否为空
    {
        cout << "Stack underflow!\n";
        return false;
    }
    value = this->element[top--]; // 不为空的出栈第一个元素 然后top - 1
    return true;
}
bool STACK::Clear()  // 通过把top置为-1的方式快速清空栈
{
    // if (top == -1) return false; 
    top = -1;
    return true;
}
bool STACK::Empty() const // 如果top=-1那么栈为空
{
    return top == -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

测试