栈的基本操作及应用

于 2024-11-01 17:45:22 发布
阅读量406 收藏
点赞数 12
文章标签： 算法 数据结构 c++ c5全栈
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/lightfuturezyx99/article/details/143437211
版权

第1关：顺序栈的基本操作实现

任务描述
本关任务是实现顺序栈的初始化、栈的判空、读栈顶元、入栈以及出栈操作。

#include <iostream>
#include <cstring>
using namespace std;
#define MAXSIZE 100
typedef enum { push, pop, read, endp} Operation;
typedef char ElemType;
typedef struct
{
    ElemType *a;
    int top;  //top指向真实的栈顶元所在下标，初始值为-1
} SqStack;

bool Init(SqStack &st);//栈的初始化，为动态数组分配一个预定义大小的空间,top初值为-1,如果申请存储空间失败返回false，否则返回true；
bool Empty(SqStack st);//判断栈是否为空，如果为空返回true，否则返回false
bool Read(SqStack st,ElemType &x);//取栈顶元，若栈为空，返回false ；否则返回true，并将栈顶元赋值到x
bool Push(SqStack &st,ElemType x);//入栈操作，若栈已满，入栈失败，返回false ；否则将x入栈，并返回true
bool Pop(SqStack &st,ElemType &x);//出栈操作，若栈为空，出栈失败，返回false；否则将栈顶元出栈，并返回true,并将栈顶元赋值到x。
void Destroy(SqStack &st);// 销毁栈
Operation GetOp();//取操作指令

bool Init(SqStack &st)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/

 // 为栈分配空间
    st.a = new ElemType[MAXSIZE];
    // 初始化栈顶指针
    st.top = -1;
    // 检查内存分配是否成功
    if (st.a == NULL) {
        return false;
    }
    return true;

     /********** End **********/
}
bool Empty(SqStack st)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
 // 栈为空的条件是栈顶指针为-1
    return st.top == -1;



     /********** End **********/
}


bool Read(SqStack st,ElemType &x)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
      // 如果栈为空，则返回false
    if (Empty(st)) {
        return false;
    }
    // 否则，读取栈顶元素
    x = st.a[st.top];
    return true;



     /********** End **********/

}

/*入栈操作 */
bool Push(SqStack &st,ElemType x)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
 // 如果栈已满，则返回false
    if (st.top == MAXSIZE - 1) {
        return false;
    }
    // 将元素入栈，栈顶指针上移
    st.top++;
    st.a[st.top] = x;
    return true;




    /********** End **********/
    
}

/*出栈操作 */
bool Pop(SqStack &st,ElemType &x)
{
 // 请在这里补充代码，完成本关任务
    /********** Begin *********/
// 如果栈为空，则返回false
    if (Empty(st)) {
        return false;
    }
    // 将栈顶元素出栈，并将栈顶指针下移
    x = st.a[st.top];
    st.top--;
    return true;

    /********** End **********/   

}

void Destroy(SqStack &st)  //
{
    
    delete []st.a;  //释放动态获取的空间
    st.top=-1;
}



Operation GetOp()
{
    char op[5];
    cin>>op;
    if (strcmp(op,"push")==0) return push;
    if (strcmp(op,"pop")==0) return pop;
    if (strcmp(op,"read")==0) return read;
    if (strcmp(op,"endp")==0) return endp;
}

第2关：顺序栈的应用-无符号十进制整数转换成十六进制数

任务描述
本关任务要求借助栈编写函数 void Dto16(unsigned int M) 实现无符号十进制整数 M 到十六进制数的转换功能。

 #include <iostream>
using namespace std;
#define MAXSIZE 100
typedef char ElemType;
typedef struct
{
    ElemType *a;
    int top;  //top指向真实的栈顶元所在下标，初始值为-1
} SqStack;

bool Init(SqStack &st);//栈的初始化，为动态数组分配一个预定义大小的空间,top初值为0,如果申请存储空间失败返回false，否则返回true；
bool Empty(SqStack st);//判断栈是否为空，如果为空返回true，否则返回false
bool Read(SqStack st,ElemType &x);//取栈顶元，若栈为空，返回false ；否则返回true，并将栈顶元赋值到x
bool Push(SqStack &st,ElemType x);//入栈操作，若栈已满，入栈失败，返回false ；否则将x入栈，并返回true
bool Pop(SqStack &st,ElemType &x);//出栈操作，若栈为空，出栈失败，返回false；否则将栈顶元出栈，并返回true,并将栈顶元赋值到x。
void Destroy(SqStack &st);// 销毁栈
void Dto16(unsigned int M); //请采用该程序中定义的栈来辅助完成将十进制M（无符号类型）转换为十六进制,并输出，输出要求每个字符之后空2格。
bool Init(SqStack &st)
{
    st.a=new ElemType[MAXSIZE];
    if (st.a==NULL) return false;
    st.top=-1;
    return true;
}
bool Empty(SqStack st)
{
    if (st.top==-1) return true;
    return false;
}

void Destroy(SqStack &st)  //
{
    delete []st.a;  //释放动态获取的空间
    st.top=-1;
}



bool Read(SqStack st,ElemType &x)
{
    if (st.top==-1)
    {
        return false;
    }
    else
    {
        x=st.a[st.top];
        return true;
    }

}


bool Push(SqStack &st,ElemType x)
{
    if (st.top==MAXSIZE-1)
    {
        return false;
    }
    st.top++;
    st.a[st.top]=x;
    return true;
}
bool Pop(SqStack &st,ElemType &x)
{
    if (st.top==-1)
    {
        return false;
    }
    else
    {
        x=st.a[st.top];
        st.top--;
        return true;
    }

}

/*请采用该程序中定义的栈来辅助完成将十进制M（无符号类型）转换为十六进制,并输出，输出要求每个字符之后空2格。*/
/*你的代码写在这里，请提交完整程序，完成Dto16函数*/
void Dto16(unsigned int M)
{
// 请在这里补充代码，完成本关任务
    /********** Begin *********/
// 初始化栈
    SqStack st;
    if (!Init(st)) {
        cout << "Stack initialization failed." << endl;
        return;
    }
    
    // 当M不为0时，进行转换
    while (M != 0) {
        // 取余数
        unsigned int remainder = M % 16;
        // 将余数转换为十六进制字符
        ElemType hexChar;
        if (remainder < 10) {
            hexChar = '0' + remainder;  // 0-9直接转换为字符
        } else {
            hexChar = 'A' + (remainder - 10);  // A-F转换为字符
        }
        // 将字符入栈
        if (!Push(st, hexChar)) {
            cout << "Stack overflow." << endl;
            Destroy(st);
            return;
        }
        // 更新M为M除以16的结果
        M /= 16;
    }
    
    // 输出栈中的元素，即十六进制数
    ElemType x;
    while (!Empty(st)) {
        if (!Pop(st, x)) {
            cout << "Stack underflow." << endl;
            break;
        }
        cout << x << "  ";  // 输出每个字符，后面空2格
    }
    
    // 销毁栈
    Destroy(st);


    /********** End **********/       

}

第3关：链式栈的基本操作实现

任务描述
本关任务是实现链式栈的初始化、读栈顶元、入栈以及出栈操作。

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

typedef enum { push, pop, read, endp} Operation;
typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
} LinkNode, *LinkStack;

void Init(LinkStack &S);
bool Read(LinkStack S, ElemType &x);
bool Push(LinkStack &S, ElemType x);
bool Pop(LinkStack &S, ElemType &x);
Operation GetOp();

void Init(LinkStack &S)
{
    S = NULL; // 初始化为空栈
}

bool Read(LinkStack S, ElemType &x)
{
    if (S == NULL) // 栈为空
        return false;
    x = S->data; // 获取栈顶元素
    return true;
}

bool Push(LinkStack &S, ElemType x)
{
    LinkNode *newNode = new LinkNode; // 申请空间
    if (newNode == NULL) // 申请空间失败
        return false;
    newNode->data = x; // 设置新节点的数据
    newNode->next = S; // 新节点指向原来的栈顶
    S = newNode; // 更新栈顶指针
    return true;
}

bool Pop(LinkStack &S, ElemType &x)
{
    if (S == NULL) // 栈为空
        return false;
    LinkNode *temp = S; // 临时指针指向栈顶
    x = S->data; // 获取栈顶元素
    S = S->next; // 更新栈顶指针
    delete temp; // 释放原栈顶元素的空间
    return true;
}

Operation GetOp()
{
    char op[5];
    cin >> op;
    if (strcmp(op, "push") == 0) return push;
    if (strcmp(op, "pop") == 0) return pop;
    if (strcmp(op, "read") == 0) return read;
    if (strcmp(op, "endp") == 0) return endp;
    return endp; // 如果输入不是以上四个，默认结束程序
}

第4关：链式栈的应用-无符号十进制整数转换成十六进制数

任务描述
本关任务要求借助链式栈编写函数 void Dto16(unsigned int M)实现无符号十进制整数M到十六进制数的转换功能。

 #include <iostream>
using namespace std;

typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
} LinkNode,*LinkStack;

void Init(LinkStack &S);//栈的初始化
bool Read(LinkStack S,ElemType &x);//取栈顶元，若栈为空，返回false ；否则返回true，并将栈顶元赋值到x
bool Push(LinkStack &S,ElemType x); //入栈操作，若申请空间失败，入栈失败，返回false ；否则将x入栈，并返回true，
bool Pop(LinkStack &S,ElemType &x); //出栈操作，若栈为空，出栈失败，返回false ；否则将栈顶元出栈，并返回true，,并将栈顶元赋值到x。
void Dto16(unsigned int M);//请采用该程序中定义的栈来辅助完成将十进制M（无符号类型）转换为十六进制,并输出，输出要求每个字符之后空2格。

void Init(LinkStack &S)
{
    S=NULL;
}
bool Read(LinkStack S,ElemType &x)
{
    if (!S) return false;
    else
    {
        x=S->data;
        return true;
    }

}


bool Push(LinkStack &S,ElemType x)
{
    LinkStack p;
    p=new LinkNode;
    if (!p) return false;
    p->data=x;
    p->next=S;
    S=p;
    return true;
}
bool Pop(LinkStack &S,ElemType &x)
{
    LinkStack p;
    if (!S) return false;
    x=S->data;
    p=S;
    S=S->next;
    delete p;
    return true;
}

//请采用该程序中定义的栈来辅助完成将十进制M（无符号类型）转换为十六进制,并输出，输出要求每个字符之后空2格。
void Dto16(unsigned int M)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
 LinkStack S; // Declare the stack here
    ElemType x;  // Declare the element here
    Init(S); // Initialize the stack

    while (M > 0) {
        int rem = M % 16; // Calculate remainder
        if (rem < 10) {
            Push(S, '0' + rem); // Convert 0-9 to character
        } else {
            Push(S, 'A' + rem - 10); // Convert 10-15 to character A-F
        }
        M /= 16; // Update M
    }

    // Output the hexadecimal number
    while (Read(S, x)) {
        cout << x << "  "; // Output character followed by two spaces
        Pop(S, x); // Pop the stack
    }
    /********** End **********/

}

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

小狗碎碎念

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值