栈和队列

  (Stack)是一种仅在表末进行插入和删除的线性表。对栈来说,表尾称为栈顶,表头称为栈底。不包含元素的空表称为空栈。

栈的ADT

//栈的ADT
ADT Stack{
    数据对象:D={ai|ai ∈ Elemset , i=1,2,3...n,n>=0}
    数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,3...n},约定an为为栈顶,a1为栈底
    基本操作:
        InitStack(&S)
            操作结果:构造一个空的栈。
        DestroyStack(&S)
            初始条件:栈S已存在。
            操作结果:销毁栈S的存储空间。
        ClearStack(&S)
            初始条件:栈S已存在。
            操作结果:将S重置为空栈。
        IsEmpty(S)
            初始条件:栈S已存在。
            操作结果:若S为空栈,返回True,否则返回false。
        IsFull(S)
            初始条件:栈S已存在。
            操作结果:若S已满,返回True,否则返回false。
        StackLength(S)
            初始条件:栈S已存在。
            操作结果:返回S中已经存放数据元素的个数。
        GetTop(S,&e)
            初始条件:栈S已存在。
            操作结果:用e返回栈顶数据元素。
        Push(&S,e)
            初始条件:栈S已存在。
            操作结果:将元素e压入栈中,成功则返回true,如果栈满打印错误信息并返回false。
        Pop(&S,&e)
            初始条件:栈S已存在。
            操作结果:将栈顶元素出栈并赋值给e,成功则返回true,如果栈空打印错误信息并返回false。
        StackTraverse(S)
            初始条件:栈S已存在。
            操作结果:从栈底到栈顶依次输出栈中的数据元素。
}

栈的表示和实现

  这里对栈的实现使用顺序结构进行实现。

//栈的定义
#define MAXSIZE 100                 //栈所能容纳的最多元素个数
using namespace std;
typedef int Elem;                   //栈内元素类型
typedef struct SqStack{ 
    Elem *base;                     //栈底指针,指向分配的连续的数组空间
    Elem *top;                      //栈顶指针,指向栈顶元素的后一个位置
    int size;                       //栈的大小
}SqStack;

//元素的打印函数,用于输出Elem,对数据元素的访问进行封装
void PrintData(Elem x){
    printf("%d",x);
}

栈的常用函数实现

//初始化栈,分配栈空间,并初始化栈顶指针
bool InitStack(SqStack &S){         //分配MAXSIZE+1个空间,栈顶指针指向栈顶元素的后一个位置
    S.base=(Elem*)malloc(sizeof(Elem)*(MAXSIZE+1));
    if(S.base==NULL) return false;  //如果分配空间失败
    S.top=S.base;                   //初始化栈顶指针
    S.size=MAXSIZE;
    return true;
}

//销毁栈,释放栈所占有的内存空间
void DestoryStack(SqStack &S){
    free(S.base);
}

//清空栈,将S清除为空栈
void ClearStack(SqStack &S){
    S.top=S.base;                   //惰性删除,直接将栈顶指针对齐到栈底
}

//判断栈空
bool IsEmpty(SqStack S){
    return S.top==S.base;           //如果栈顶和栈底相同,则是空栈
}

//判断栈满
bool IsFull(SqStack S){
    return S.top-S.base==MAXSIZE;   //如果栈顶这栈底的距离为MAXSIZE就是栈满
}

//返回栈的长度,即栈中现有的元素个数
int StackLength(SqStack S){
    return S.top-S.base;
}

//读取栈顶元素,并用e返回
void GetTop(SqStack S,Elem &e){
    if(IsEmpty(S)){                 //如果栈空,打印错误信息并返回
        printf("Stack is empty!\n");
        return;
    }
    e=*(S.top-1);                   //top指向栈顶元素的后一个位置,因此-1 取元素
}

//入栈
bool Push(SqStack &S,Elem e){
    if(IsFull(S)){                  //如果栈满,无法入栈,打印错误信息
        printf("Stack is full!\n");
        return false;
    }
    *S.top++=e;                     //栈顶指针的位置进行填装,然后栈顶指针后移
    return true;
}

//出栈
bool Pop(SqStack &S,Elem &e){
    if(IsEmpty(S)){                 //如果栈空,无法出栈,打印错误信息
        printf("Stack is empty!\n");
        return false;
    }
    e=*--S.top;                     //因为top指向栈顶元素的后一个位置,先将top减一,再读取栈顶的元素
}

//从栈底到栈顶依次输出栈中元素
void StackTraverse(SqStack S){
    printf("栈中元素个数:%d,栈底到栈顶元素依次为:\n栈底 ",StackLength(S));
    for(Elem *p=S.base;p!=S.top;p++){
        PrintData(*p); putchar(' ');
    }
    printf("栈顶\n");
}

用于测试栈的main函数

int main(void){
    Elem temp;
    SqStack S;
    printf("-------------------------------------\n");
    printf("初始化栈,把0-25压入栈中.\n");
    InitStack(S);
    for(int i=0;i<=25;i++){         
        temp=i;
        Push(S,temp);
    }
    StackTraverse(S);
    printf("-------------------------------------\n");
    printf("读取并打印栈顶元素:");
    GetTop(S,temp);                 
    PrintData(temp);    putchar('\n');

    printf("-------------------------------------\n");
    printf("出栈并打印出栈元素:");
    Pop(S,temp);
    PrintData(temp);    putchar('\n');
    StackTraverse(S);

    printf("-------------------------------------\n");
    printf("空栈出栈测试:");
    ClearStack(S);
    Pop(S,temp);

    printf("-------------------------------------\n");
    printf("满栈入栈测试:");
    for(int i=0;i<101;i++){
        temp=i;
        Push(S,temp);
    }

    printf("-------------------------------------\n");

    return 0;
}

  测试结果:

-------------------------------------
初始化栈,把0-25压入栈中.
栈中元素个数:26,栈底到栈顶元素依次为:
栈底 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 栈顶
-------------------------------------
读取并打印栈顶元素:25
-------------------------------------
出栈并打印出栈元素:25
栈中元素个数:25,栈底到栈顶元素依次为:
栈底 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 栈顶
-------------------------------------
空栈出栈测试:Stack is empty!
-------------------------------------
满栈入栈测试:Stack is full!
-------------------------------------

栈的应用

使用栈进行括号的匹配

  一个算术表达式中包含() [] {}三种英文括号,编写一个算法来判别运算表达式中的三种括号是否匹配。

//这里直接使用了C++的stl中的stack,为了使得代码更加简短,并且可以直接复制使用
//需要包含stack头文件
#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool BracketCheck(string str){
    stack<char> s;
    int i=0;
    while(i<str.size()){
        if(s.empty()){
            s.push(str[i++]); continue;                 //如果是[])))这种情况中间可能遇到栈空,所以加此特判
        }   
        switch(str[i]){
            case '{': 
            case '[': 
            case '(': s.push(str[i]); break;            //左括号则入栈
            case '}': if(s.top()!='{') return false;    //如果是右括号则和栈顶元素进行匹配,如果不匹配返回false
                      s.pop();break;                    //如果匹配,则出栈并继续循环
            case ']': if(s.top()!='[') return false;
                      s.pop();break;  
            case ')': if(s.top()!='(') return false;
                      s.pop();break;                   
            default : break;
        }
        i++;
    }
    if(s.empty()) return true;                          //如果字符串遍历完毕后栈中没有剩余,则说明匹配
    else return false;                                  //如果有剩余,则说明不匹配
}

int main(void){
    string str;
    cout<<"请输入一串带括号的表达式,进行表达式括号匹配的检测(输入q 结束):";
    while(1){
        cin>>str;
        if(str=="q") break;
        if(BracketCheck(str)) cout<<"括号匹配!"<<endl;
        else                  cout<<"括号不匹配!"<<endl;
        cout<<"请继续输入要进行括号匹配检测的表达式(输入q 结束):";
    }
    cout<<"Bye!";
    return 0;
}

  运行可测试结果:

请输入一串带括号的表达式,进行表达式括号匹配的检测(输入q 结束):(){}[]
括号匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):{{{}}}((([[[]]])))
括号匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):{{()[]
括号不匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):()[]]]
括号不匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):(3+1)
括号匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):(4+6]
括号不匹配!
请继续输入要进行括号匹配检测的表达式(输入q 结束):q
Bye!

栈的知识点补充

栈的性质

  1.栈的出栈和入栈
  由于栈的操作方式,如果已知入栈序列和出栈序列,则对于出栈序列来说,某个元素之前的只能是在其之前进栈的元素。
  【例题】:
  如果已知入栈序列是1,2,3,4,5...n,出栈序列为p1,p2,p3...pn;若p2=3,则p1可能是1和2,因为在3后边的元素不可能比3更早出栈。
  2.进出栈的序列个数
  n个不同的元素进栈,出栈序列的个数为:

栈的相关算法(伪代码)

  1.用栈判别单链表是否对称
  设单链表的头指针为L,带头结点,结构为data和next,data为字符型,设计使用栈的算法判断链表的全部n个字符是否中心对称。

//算法思想:
//前半部分入栈,然后出栈和后半部分进行比对,如果字符相同则继续比对,直到栈空;如果最后栈不空则不对称
bool dc(LinkList L, int n){
    int i;                              //自定义栈的指针,指向栈顶的后一个位置,初始化为0
    char [n/2];                         //字符栈
    LinkList p=L->next;                 //p为遍历的工作指针
    for(i=0;i<n/2;i++){                 //前一半入栈
        s[i]=p->data;                   //入栈赋值
        p=p->next;                      //遍历指针更新
    }
    i--;                                //由于for循环的边界判定,要对i进行减1修正
    if(n%2==1) p=p->next;               //如果n个字符串是奇数个,则p要后移一位,跨过中间结点
    while(p!=NULL&&s[i]==p->data){      //后半部分进行不对,当链表未结尾并且比对成功(即对称位置字符串相同)
        i--;                            //出栈修改栈顶指针
        p=p->next;                      //遍历指针后移
    }
    if(i==-1) return true;              //如果while循环结束后,栈空则说明比对成功,字符序列对称
    else      return false;             //否则表示不对称
}

  对于循环双链表,可以从头指针开始,两个指针p向前遍历,q向后依次遍历比对。如果是奇数个元素,比对成功的结束条件是两个最后指向最中间的结点(即p==q);如果是偶数个元素,则比对成功时的结束条件为p走到了q的前边(即p->next==q)。  
  2.共享栈的出栈和入栈操作
  设两个栈S1和S2,都采用顺序栈的方式,并且共享[0,1,2,...maxsize-1]的空间,为充分利用空间,减少溢出,请设计与S1和S2相关的入栈和出栈算法。其中,共享栈的示意图如下所示:

//1.共享栈的类型定义说明
#define MAXSIZE 100                             //栈空间大小
typedef int Elemtype;                           //栈中元素类型
typedef struct {                        
    Elemtype stack[MAXSIZE];                    //顺序栈的数组
    int top[2];                                 //共享栈的两个栈顶指针,指向栈顶元素,分别初始化为-1和MAXSIZE
}ShareStack;
ShareStack S;                                   //用于操作的栈的声明

//2.入栈函数
bool Push(int i,Elemtype x){                    //i表示入栈的栈号,其中0代表左边的栈,1代表右边的栈,x为入栈元素
    bool ret=true;                              //为了统一函数的返回出口
    if(i<0||i>1){                               //如果入栈的栈号不正确,输出错误信息
        printf("栈号错误!");
        ret=false;
    }
    if(S.top[1]-S.top[0]==1){                   //判定栈是否已经满了,当栈满时,两个栈顶指针刚好相差一,所有的空间都被利用
        printf("栈已满!");
        ret=false;
    }
    switch(i){
        case 0:S.stack[++S.top[0]]=x; break;    //如果是插入左侧的栈,先增加栈顶指针再赋值入栈
        case 1:S.stack[++S.top[1]]=x; break;    //如果是插入右侧的栈,先增加栈顶指针再赋值入栈
        default: break;
    }
    return ret;                                 //返回是否入栈成功
}

//3.出栈函数
Elemtype Pop(int i){
    if(i<0||i>1){                               //如果出栈的栈号不正确,则错误退出
        printf("栈号错误!");
        exit(0);
    }
    switch(i){      
        case 0:                     
            if(S.top[0]==-1){                   //判断是否为空,左侧栈的判别栈顶指针是否等一-1
                printf("栈空");
                exit(0);
            }
            else    return S.stack[S.top[0]--]; //不空时返回栈顶元素,并更新栈顶指针
            break;
        case 1:
            if(S.top[1]==MAXSIZE){              //判断是否为空,左侧栈的判别栈顶指针是否等一-1
                printf("栈空");
                exit(0);
            }
            else    return S.stack[S.top[1]++]; //不空时返回栈顶元素,并更新栈顶指针
            break;
    }
}

  3.利用栈实现递归函数的非递归计算