顺序栈

2022-10-032024-01-21 数据结构 20 分钟读完 (大约3050个字) 0次访问

栈的顺序存储表示

1、顺序存储结构

利用一组地址连续的存储单元
顺序栈定义：

typedef struct{
    SElemType *base;   // 栈底指针
    SElemType *top;    // 栈顶指针
    int stacksize;   // 当前栈的最大容量 
}Sqstack;

注：当用数组作为存储结构时，可以用下标代替指针

2、基本操作算法描述

对栈的常用操作做简要描述：

栈的初始化

Status InitStack(SqStack &S)
{
    // 构造空栈S
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

以初始化容量申请一块连续的内存，S.top=S.base保证 top=base时栈空。

返回栈顶元素

Status GetTop(SqStack S, SElemType &e)
{
    if(S.top == S.base)  return ERROR;
    e = *(S.base-1);
    return OK;
}

压栈操作

Status Push(SqStack &S, SElemType e)
{
    //首先判断是否栈满
    if(S.top-S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType));   //申请增量空间
        if(!S.base) exit(OVERFLOW);
        // 更新回原来位置
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}

出栈操作

Status Pop(SqStack &S, SElemType &e)
{
    // 栈空标志
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

判断栈空

Status StackEmpty(SqStack S)
{
    if(S.base == S.top) return true;
    return false;
}

清空栈

Status ClearStack(SqStack &S)
{
    // 利用栈空标志进行清空
    S.top = S.base;
    return OK;
}

释放栈空间

Status DestroyStack(SqStack &S)
{
    if(S.base != NULL) free(S.base);
    return OK;
}

3、栈的应用举例

3.1 数制转换

十进制数与其他d进制数转换时，一个简单算法原理：
N = (N div d) X d + N mod d,其中 div表示整除操作，mod表示求余操作

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

typedef int SElemType;
typedef bool Status;

const bool OK = true;
const bool ERROR = false;
const SElemType STACK_INIT_SIZE = 100;
const SElemType STACKINCREMENT = 10;
typedef struct{
    SElemType *base;   // 栈底指针
    SElemType *top;    // 栈顶指针
    int stacksize;   // 当前栈的最大容量 
}SqStack;
Status InitStack(SqStack &S)
{
    // 构造空栈S
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(EOVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status Push(SqStack &S, SElemType e)
{
    //首先判断是否栈满
    if(S.top-S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType));   //申请增量空间
        if(!S.base) exit(EOVERFLOW);
        // 更新回原来位置
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
    // 栈空标志
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}
Status StackEmpty(SqStack S)
{
    if(S.base == S.top) return true;
    return false;
}
Status Conversion()
{
    SqStack S;
    InitStack(S);
    SElemType data;
    int Obj = 0;
    cin >> data >> Obj;
    while(data){
        Push(S,data % Obj);
        data = data/Obj;
    }
    while(!StackEmpty(S))
    {
        SElemType e;
        if(!Pop(S,e)) break;
        cout << e;
    }
    cout << endl;
    return OK;
}
int main()
{
    // 对于输入的十进制数和目标进制，打印输出目标进制数
    Conversion();
    return 0;
}

3.2 行编辑程序

将用户从键盘输入的符号存入一个输入缓冲区，然后逐行存入用户数据区；这个过程允许用户删除字符，删除整行字符
基本操作规则：

1
2
3

# 退格符
@ 退行符
^ 结束符

程序实现：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;

typedef char SElemType;
typedef bool Status;

const bool OK = true;
const bool ERROR = false;
const SElemType STACK_INIT_SIZE = 100;
const SElemType STACKINCREMENT = 10;
typedef struct{
    SElemType *base;   // 栈底指针
    SElemType *top;    // 栈顶指针
    int stacksize;   // 当前栈的最大容量 
}SqStack;
Status InitStack(SqStack &S)
{
    // 构造空栈S
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(EOVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status Push(SqStack &S, SElemType e)
{
    //首先判断是否栈满
    if(S.top-S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType));   //申请增量空间
        if(!S.base) exit(EOVERFLOW);
        // 更新回原来位置
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
    // 栈空标志
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}
Status StackEmpty(SqStack S)
{
    if(S.base == S.top) return true;
    return false;
}
Status StackPrint(SqStack S)
{
    SElemType *mp = S.base;
    while(mp != S.top){
        putchar(*mp);
        mp++;
    }
    putchar('\n');
    return OK;
}
Status ClearStack(SqStack &S)
{
    // 利用栈空标志进行清空
    S.top = S.base;
    return OK;
}
Status DestroyStack(SqStack &S)
{
    if(S.base != NULL) free(S.base);
    return OK;
} 
Status LineEdit()
{
    //构造字符栈
    SqStack S;
    InitStack(S);
    SElemType ch;
    ch = getchar();  //从终端接受一个字符
    while(ch != '^'){
        while(ch != '^' && ch != '\n'){
            switch(ch){
                case '#':Pop(S,ch);  //退字符
                         break;
                case '@':ClearStack(S); //退行
                         break;
                default:Push(S,ch); //字符入栈
            }
            ch = getchar(); //从终端接受下一个字符
        }
        //对缓冲区的一行字符存入数据区，这里只是打印输出
        StackPrint(S);
        ClearStack(S);
        if(ch != '^') ch = getchar();
    }
    DestroyStack(S);
    return OK;
}
int main()
{
    LineEdit();
    return 0;
}

3.3 括号匹配问题

给定一个包含各种括号的表达式，判断是否满足括号匹配利用栈操作，可在线性时间内检查出是否匹配，具体实现如下：

利用 STL模板库

bool paren(const char exp[]) { //表达式括号匹配检查，可兼顾三种括号
    Stack<char> S; //使用栈记录已出现但尚未匹配的左括号
    for (int i = 0; exp[i]; i++) /* 逐一检查当前字符 */
        switch (exp[i]) { //左括号直接进栈；右括号若不栈顶失配，则表达式必不匹配
            case '(': case '[': case '{': S.push(exp[i]); break;
            case ')': if ((S.empty()) || ('(' != S.pop())) return false; break;
            case ']': if ((S.empty()) || ('[' != S.pop())) return false; break;
            case '}': if ((S.empty()) || ('{' != S.pop())) return false; break;
            default: break; //非括号字符一律忽略
        }
    return S.empty(); //整个表达式扫描过后，栈中若仍残留（左）括号，则不匹配；否则（栈空）匹配
}

自定义栈操作

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;

typedef char SElemType;    //栈元素类型
typedef bool Status;

const bool OK = true;
const bool ERROR = false;
const SElemType STACK_INIT_SIZE = 100;
const SElemType STACKINCREMENT = 10;
typedef struct{
    SElemType *base;   // 栈底指针
    SElemType *top;    // 栈顶指针
    int stacksize;   // 当前栈的最大容量 
}SqStack;
Status InitStack(SqStack &S)
{
    // 构造空栈S
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if(!S.base) exit(EOVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status Push(SqStack &S, SElemType e)
{
    //首先判断是否栈满
    if(S.top-S.base >= S.stacksize){
        S.base = (SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType));   //申请增量空间
        if(!S.base) exit(EOVERFLOW);
        // 更新回原来位置
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
SElemType Pop(SqStack &S)
{
    // 栈空标志
    if(S.top == S.base) return ERROR;
    return *--S.top;
}
Status StackEmpty(SqStack S)
{
    if(S.base == S.top) return true;
    return false;
}
Status paren()
{

    //构造字符栈
    SqStack S;
    InitStack(S);
    SElemType ch;
    ch = getchar();
    while(ch != '\n'){
        switch (ch) { //左括号直接进栈；右括号若不栈顶失配，则表达式必不匹配
            case '(': case '[': case '{': Push(S, ch); break;
            case ')': if ((StackEmpty(S)) || ('(' != Pop(S))) return false; break;
            case ']': if ((StackEmpty(S)) || ('[' != Pop(S))) return false; break;
            case '}': if ((StackEmpty(S)) || ('{' != Pop(S))) return false; break;
            default: break; //非括号字符一律忽略
        }
        ch = getchar();
    }
    return StackEmpty(S);
}
int main()
{
    if(paren()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

3.4 表达式求值

延迟缓冲
在一些应用问题中，输入可分解为多个单元并通过迭代依次扫描处理，但过程中的各步计算
往往滞后于扫描的进度，需要待到必要的信息已完整到一定程度之后,才能作出判断并实施计算。在这类场合，栈结构则可以扮演数据缓冲区的角色。

表达式求值
关于运算符执行次序的规则(即运算优先级)，一部分决定于事先约定的惯例(比如乘除优先于加减)，另一部分则决定于括号。也就是说，仅根据表达式的某一前缀，并不能完全确定其中各运算符可否执行以及执行的次序；只有在已获得足够多后续信息之后，才能确定其中哪些运算符可以执行。

由于栈基本结构较为简单，常用操作内容上文已经介绍，因此本代码在此处调用 STL中 stack模板直接进行相关操作。

定义优先级表

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
#define N_OPTR 9 //运算符总数
#define Opr 100  //表达式最大长度
typedef enum {ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE} Operator; //运算符集合
 //加、减、乘、除、乘斱、阶乘、左括号、右括号、起始符不终止符

const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [弼前]
/* |-------------- 当前运算符 --------------| */
/* + - * / ^ ! ( ) \0 */
/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* | - */  '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* | ) */  ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0*/ '<', '<', '<', '<', '<', '<', '<', ' ', '='
};
void readNumber(char*& p, stack<float>& stk) { //将起始于p癿子串解析为数值，并存入操作数栈
    stk.push((float)(*p - '0')); //当前数位对应的数值进栈
    // 处理多位整数情况
    while (isdigit(*(++p))){
        float temp = stk.top();
        stk.pop();
        stk.push(temp * 10 + (*p - '0'));   //弹出原操作数，转换新数值重新入栈
    }
    if ('.' != *p) return ; //此后非小数点，则意味着当前操作数解析完成

    //处理小数部分  fraction设置挺关键
    float fraction = 1; //否则，意味着还有小数部分 
    while (isdigit(*(++p))){ //逐位加入
        float temp = stk.top();
        stk.pop();
        stk.push(temp + (*p - '0')*(fraction /= 10)); //小数部分
    }
    return ;
}
Operator optr2rank(char op) { //由运算符转译出编号
    switch (op) {
        case '+' : return ADD; //加
        case '-' : return SUB; //减
        case '*' : return MUL; //乘
        case '/' : return DIV; //除
        case '^' : return POW; //乘斱
        case '!' : return FAC; //阶乘
        case '(' : return L_P; //左括号
        case ')' : return R_P; //右括号
        case '\0': return EOE; //起始符与终止符
        default : exit(-1); //未知运算符
    }
}
char orderBetween(char op1, char op2) //比较两个运算符之间的优先级
{ 
    return pri[optr2rank(op1)][optr2rank(op2)]; 
}

void append(char*& rpn, float opnd) { //将操作数接至RPN末尾
    char buf[64] = {0};
    //分数值类型进行压栈
    if (opnd != (float)(int)opnd) sprintf(buf, "%.2f \0", opnd); //浮点格式，或
    else sprintf(buf, "%d \0", (int)opnd); //整数格式

    if(rpn==NULL){
        rpn = (char*) malloc(sizeof(char) * (strlen(buf) + 1));
        strcpy(rpn,buf);
    }
    else{
        int n = strlen(rpn); //RPN当前长度（以'\0'结尾，长度n + 1）
        rpn = (char*) realloc(rpn, sizeof(char) * (n + strlen(buf) + 1)); //扩展空间
        strcat(rpn, buf); //RPN加长
    }
    return ;
}

void append(char*& rpn, char optr) { //将运算符接至RPN末尾
    if(rpn == NULL){
        rpn = (char*) malloc(sizeof(char) * (3));
        sprintf(rpn, "%c ", optr); rpn[2] = '\0'; //接入指定癿运算符
    }
    else{
        int n = strlen(rpn); //RPN当前长度（以'\0'结尾，长度n + 1）
        rpn = (char*) realloc(rpn, sizeof(char) * (n + 3)); //扩展空间
        sprintf(rpn + n, "%c ", optr); rpn[n + 2] = '\0'; //接入指定癿运算符
    }
    return ;
}
int calcu(char op, float data)
{
    // 一元计算
    if((int)data == 0) return 0;
    int sum_data = 1;
    for(int i=1;i<=(int)data;i++) sum_data *= i;
    return sum_data;
}
float calcu(float opd1,char op, float opd2)
{
    //前后操作数
    switch(op){
        case '+': return opd1+opd2;
                  break;
        case '-': return opd1-opd2;
                  break;
        case '*': return opd1*opd2;
                  break;
        case '/': return opd1/opd2;
                  break;
        case '^': return pow(opd1,opd2);
                  break;
        default:  return 0;
                  break;
    }
}
bool evaluate(char* S, char*& RPN, float &result) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
    stack<float> opnd; stack<char> optr; //运算数栈、运算符栈
    optr.push('\0'); //尾哨兵'\0'也作为头哨兵首先入栈，主要为了判断计算结束退出
    while (!optr.empty()) { //在运算符栈非空之前，逐个处理表达式中各字符
        if (isdigit(*S)) { //若当前字符为操作数，则
            readNumber(S, opnd);   // 读入操作数
            append(RPN, opnd.top()); //并将其接至RPN末尾
        } else //若当前字符为运算符，则
            switch(orderBetween(optr.top(), *S)) { //视其与栈顶运算符之间优先级高低分别处理
                case '<': //栈顶运算符优先级更低时
                    optr.push(*S); S++; //计算推迟，当前运算符入栈
                    break;
                case '=': //优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
                    optr.pop(); S++; //脱括号并接收下一个字符
                    break;
                case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
                    char op = optr.top();
                    optr.pop(); 
                    append(RPN, op); //栈顶运算符出栈并续接至RPN末尾
                    if ('!' == op) { //若属于一元运算符
                        float pOpnd = opnd.top(); //叧需取出一个操作数，并
                        opnd.pop();
                        opnd.push(calcu(op, pOpnd)); //实施一元计算，结果入栈
                    } else { //对于其它（二元）运算符
                        float pOpnd2 = opnd.top();
                        opnd.pop();
                        float pOpnd1 = opnd.top(); //取出后、前操作数
                        opnd.pop();
                        opnd.push(calcu(pOpnd1, op, pOpnd2)); //实施二元计算，结果入栈
                    }
                    break;
                    }
                default:
                    return false; //逢语法错误，并做处理直接退出
            }//switch
    }//while
    result = opnd.top();
    opnd.pop();
    return true; //弹出并返回最后的计算结果
}
int main()
{
    float ans = 0;
    char* RPN = NULL;
    char S[Opr] = {0};
    cin >> S;
  
    if(evaluate(S,RPN,ans))
        cout << "Ans = " << ans << endl;
    else
        cout << "Error!" << endl;
    cout << "Reverse Polish Notation:\n";
    cout << RPN;
    return 0;
}

算法计算示例:
计算给定表达式 (0!+1)*2^(3!+4)-(5!-67-(8+9))的值
运行结果

1
2
3

Ans = 988
Reverse Polish Notation:
0 ! 1 + 2 3 ! 4 + ^ * 5 ! 67 - 8 9 + - -

顺序栈

https://markstiff.github.io/数据结构/顺序栈/

作者

Mark Stiff

发布于

2022-10-03

更新于

2024-01-21

许可协议

数据结构,算法

顺序栈