栈和队列

栈

　　栈（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.利用栈实现递归函数的非递归计算

 //算法思想
//用一个栈纪律，栈中每一个元素保存n和对应的Pn(x)的值
//在P0(x),P1(x)可以得到P2(x)的基础上，以此递推关系可层层得到后序结果
//因此，每次从栈顶P1和P2开始，读两个元素算出下一个，向下递推得到相应的后序结果
double P(int n,double x){                           //参数为n层函数和自变量x
    struct stack{                                   //定义栈中元素的结构体
        int n0;                                     //存放n值
        double val;                                 //存放Pn(x)
    }ST[MAXSIZE];                                   //顺序栈
    int top=-1;
    double fv1=1,fv2=2*x;                           //用于递推的两个自变量，f1表示第一个数，fv2表示第二个数
    for(i=n;i>=2;i--)                               //先赋值n，由于前两个已经由fv1和fv2记录，所以只需要赋值到2即可
        ST[top++].n0=i;
    while(top>=0){                                  //如果栈不空则循环，最终栈空时刚好计算出Pn(x)
        ST[top].val=2*x*fv2-2*x(ST[top].n0-1)*fv1;  //递归关系
        fv1=fv2; fv2=ST[top].val;                   //更新递推关系式子中的两个值，为下一次递归做准备
        top--;                                      //栈顶指针更新
    }
    if(n==0) return fv1;                            //特殊判定，如果n=0
    else return fv2;                                //如果n不是0.则根据计算结果，返回fv2即Pn(x)
}

队列

　　队列（Queue）是一种先入先出的数据结构，允许在队列头部进行出队操作，在队列尾部进行入队操作。

队列的ADT

 //队列的ADT
ADT Queue{
    数据对象：D={ai|ai ∈ Elemset , i=1,2,3...n,n>=0}
    数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3...n}，约定a1端为队列头，an为队列尾。
    基本操作：
        InitQueue(&Q)
            操作结果：构造一个空的队列。
        DestroyQueue(&Q)
            初始条件：队列Q已存在。
            操作结果：销毁队列Q的存储空间。
        ClearQueue(&Q)
            初始条件：队列Q已存在。
            操作结果：将S重置为空栈。
        IsEmpty(Q)
            初始条件：队列Q已存在。
            操作结果：若S为空栈，返回True，否则返回false。
        IsFull(Q)
            初始条件：队列Q已存在。
            操作结果：若S已满，返回True，否则返回false。
        QueueLength(Q)
            初始条件：队列Q已存在。
            操作结果：返回S中已经存放数据元素的个数。
        EnQueue(Q,&e)
            初始条件：队列Q已存在。
            操作结果：用e返回栈顶数据元素。
        DeQueue(&Q,e)
            初始条件：队列Q已存在。
            操作结果：将元素e压入栈中，成功则返回true，如果栈满打印错误信息并返回false。
        QueueTraverse(Q)
            初始条件：队列Q已存在。
            操作结果：从栈底到栈顶依次输出栈中的数据元素。
}

队列的表示与实现

　　队列的表示和实现有很多方式，包括使用链式结构实现，或者使用数组实现。下面分别给出两种实现方法的结构示意图和代码实现。

使用链表实现队列

　　使用链式结构实现队列时我们需要两个指针分别指向链表的头部和尾部，为了方便操作，我们在头部使用一个空的链表节点作为头部，front指针指向该空节点，rear指针指向尾部最后一个节点，如下图所示：

　　队列的代码实现：

 #include<bits/stdc++.h>
using namespace std;
 
typedef int ElemType;
//链式队列的节点
typedef struct node{
    ElemType data;
    struct node *next;
}QNode,*QNodePtr;
//队列结构定义
typedef struct queue{
    QNodePtr front,rear;
}Queue,*QueuePtr;
 
//初始化队列
void InitQueue(Queue &Q){
    Q.front = Q.rear = (QNodePtr)malloc(sizeof(QNode));
    Q.front->next = NULL;
}
//销毁队列
void DestroyQueue(Queue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    Q.front = Q.rear = NULL;
}
//判空
bool isEmpty(Queue Q){
    return Q.front == Q.rear;
}
//判满
bool isFull(Queue Q){
    return false;            //一般认为内存可以不停的申请
}
//入队
bool EnQueue(Queue &Q,ElemType e){
    QNodePtr p = (QNodePtr)malloc(sizeof(QNode));
    if(p==nullptr) return false;
    p->next = NULL;
    p->data = e;
    Q.rear->next = p;
    Q.rear = Q.rear->next;
    return true;
}
//出队
bool DeQueue(Queue &Q,ElemType &e){
    if(isEmpty(Q)) return false;
    QNodePtr p = Q.front->next;
    Q.front->next = p->next;
    e = p->data;
    if(Q.rear == p) Q.rear = Q.front;
    free(p);
    return true;
}
//打印队列
void PrintQueue(Queue Q){
    if(isEmpty(Q)){
        printf("Empty queue.\n");
        return;
    }
    QNodePtr p = Q.front->next;
    int cnt = 0;
    while(p){
        if(cnt++) printf(" -> ");
        printf("%d",p->data);
        p = p->next;
    }
}

　　代码测试：

 int main(){
    Queue Q;
    InitQueue(Q);
    printf("初始化队列后，队列为空吗？\n");
    if(isEmpty(Q)) printf("queue is empty.\n");
    int e;
    for (int i = 0; i < 10; i++){
        if(EnQueue(Q,i))
            printf("EnQueue %d Success\n",i);
    }
    printf("打印队列中的数据:\n");
    PrintQueue(Q);
    printf("\n取出前面6个元素：\n");
    for (int i = 0; i < 6; ++i) {
        DeQueue(Q,e);
        printf("%d ",e);
    }
    printf("\n");
    printf("队列数据如下：\n");
    PrintQueue(Q);
 
    return 0;
}

　　运行结果：

 初始化队列后，队列为空吗？
queue is empty.
EnQueue 0 Success
EnQueue 1 Success
EnQueue 2 Success
EnQueue 3 Success
EnQueue 4 Success
EnQueue 5 Success
EnQueue 6 Success
EnQueue 7 Success
EnQueue 8 Success
EnQueue 9 Success
打印队列中的数据:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
取出前面6个元素：
0 1 2 3 4 5 
队列数据如下：
6 -> 7 -> 8 -> 9

使用数组实现队列

　　使用数组实现队列，我们会遇到一个问题，数组的指针遍历到结尾时无法继续增长，我们可以通过占用一个空位置实现循环链表，保留一个空为止能够方便判断队列是否已满。其中初始化时，front和rear初始为同一个位置，front指向队列中的第一个元素，rear指向队列中最后一个元素的下一个位置。其表示如下图所示：

　　其中，队列空和队列满的状态如下图所示：

　　队列的代码实现：

 #include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;
struct CycleQueue{
    int *data;
    int front,rear;
    int maxSize;
};
//初始化循环队列
void InitQueue(CycleQueue &Q,int size) {
    Q.maxSize = size + 1;                               //循环队列的长度要比储存的数据长度要多一位，空出来一个位来区分队列空和队列满
    Q.data = (int *)malloc((Q.maxSize)*sizeof(int));
    Q.front = Q.rear = 0;
}
//销毁循环队列
void DestroyQueue(CycleQueue &Q) {
    free(Q.data);
    Q.data = NULL;
    Q.front = Q.rear = 0;
}
//判空
int isEmpty(CycleQueue Q) {
    return Q.front == Q.rear;
}
//判满
int isFull(CycleQueue Q) {
    return (Q.rear + 1) % Q.maxSize == Q.front;
}
//出队
int DeQueue(CycleQueue &Q,ElemType &e) {
    if(isEmpty(Q)) return 0;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % Q.maxSize;
    return 1;
}
//入队
int EnQueue(CycleQueue &Q,ElemType e) {
    if(isFull(Q)) return 0;
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % Q.maxSize;
    return 1;
}
void PrintQueue(CycleQueue Q){
    if(isEmpty(Q)){
        printf("Queue is empty\n");
        return;
    }
    int index = Q.front;
    int cnt = 0;
    while(index != Q.rear) { //Q.rear表示队尾的下一位，循环结束条件是index刚刚好到达rear前面那位
        if(cnt++) printf(" -> ");
        printf("%d",Q.data[index]);
        index = (index + 1) % Q.maxSize;
    }
    printf("\n");
}

　　代码测试：

 int main(){
    CycleQueue Q;
    InitQueue(Q,9);
    printf("初始化队列后，队列为空吗？\n%d\n",isEmpty(Q));
    int e;
    for (int i = 0; i < 20; i++){
        if(EnQueue(Q,i)){
            printf("EnQueue %d Success\n",i);
        }else{
            printf("EnQueue %d Fail\n",i);
            break;
        }
    }
    printf("插入元素后，队列满了吗？\n%d\n",isFull(Q));
    printf("打印队列中的数据:\n");
    PrintQueue(Q);
    printf("取出前面6个元素：\n");
    for (int i = 0; i < 6; ++i) {
        DeQueue(Q,e);
        printf("%d\n",e);
    }
    printf("删去6个元素后，队列还有数据吗？\n%d\n",!isEmpty(Q));
    printf("队列数据如下：\n");
    PrintQueue(Q);
 
    return 0;
}

　　运行结果：

 初始化队列后，队列为空吗？
1
EnQueue 0 Success
EnQueue 1 Success
EnQueue 2 Success
EnQueue 3 Success
EnQueue 4 Success
EnQueue 5 Success
EnQueue 6 Success
EnQueue 7 Success
EnQueue 8 Success
EnQueue 9 Fail
插入元素后，队列满了吗？
1
打印队列中的数据:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
取出前面6个元素：
0
1
2
3
4
5
删去6个元素后，队列还有数据吗？
1
队列数据如下：
6 -> 7 -> 8

栈和队列

栈和队列

栈

栈的ADT

栈的表示和实现

栈的常用函数实现

用于测试栈的main函数

栈的应用

使用栈进行括号的匹配

栈的知识点补充

栈的性质

栈的相关算法（伪代码）

队列

队列的ADT

队列的表示与实现

使用链表实现队列

使用数组实现队列

Hugo+github搭建个人博客（windows10）

线性表

songjiahao

Comments | NOTHING

取消回复

	//栈的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");
	}

	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!

	//算法思想：
	//前半部分入栈，然后出栈和后半部分进行比对，如果字符相同则继续比对，直到栈空；如果最后栈不空则不对称
	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; //否则表示不对称
	}

	//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;
	}
	}

	//算法思想
	//用一个栈纪律，栈中每一个元素保存n和对应的Pn(x)的值
	//在P0(x),P1(x)可以得到P2(x)的基础上，以此递推关系可层层得到后序结果
	//因此，每次从栈顶P1和P2开始，读两个元素算出下一个，向下递推得到相应的后序结果
	double P(int n,double x){ //参数为n层函数和自变量x
	struct stack{ //定义栈中元素的结构体
	int n0; //存放n值
	double val; //存放Pn(x)
	}ST[MAXSIZE]; //顺序栈
	int top=-1;
	double fv1=1,fv2=2*x; //用于递推的两个自变量，f1表示第一个数，fv2表示第二个数
	for(i=n;i>=2;i--) //先赋值n，由于前两个已经由fv1和fv2记录，所以只需要赋值到2即可
	ST[top++].n0=i;
	while(top>=0){ //如果栈不空则循环，最终栈空时刚好计算出Pn(x)
	ST[top].val=2xfv2-2x(ST[top].n0-1)fv1; //递归关系
	fv1=fv2; fv2=ST[top].val; //更新递推关系式子中的两个值，为下一次递归做准备
	top--; //栈顶指针更新
	}
	if(n==0) return fv1; //特殊判定，如果n=0
	else return fv2; //如果n不是0.则根据计算结果，返回fv2即Pn(x)
	}

	//队列的ADT
	ADT Queue{
	数据对象：D={ai\|ai ∈ Elemset , i=1,2,3...n,n>=0}
	数据关系：R1={<ai-1,ai>\|ai-1,ai∈D,i=2,3...n}，约定a1端为队列头，an为队列尾。
	基本操作：
	InitQueue(&Q)
	操作结果：构造一个空的队列。
	DestroyQueue(&Q)
	初始条件：队列Q已存在。
	操作结果：销毁队列Q的存储空间。
	ClearQueue(&Q)
	初始条件：队列Q已存在。
	操作结果：将S重置为空栈。
	IsEmpty(Q)
	初始条件：队列Q已存在。
	操作结果：若S为空栈，返回True，否则返回false。
	IsFull(Q)
	初始条件：队列Q已存在。
	操作结果：若S已满，返回True，否则返回false。
	QueueLength(Q)
	初始条件：队列Q已存在。
	操作结果：返回S中已经存放数据元素的个数。
	EnQueue(Q,&e)
	初始条件：队列Q已存在。
	操作结果：用e返回栈顶数据元素。
	DeQueue(&Q,e)
	初始条件：队列Q已存在。
	操作结果：将元素e压入栈中，成功则返回true，如果栈满打印错误信息并返回false。
	QueueTraverse(Q)
	初始条件：队列Q已存在。
	操作结果：从栈底到栈顶依次输出栈中的数据元素。
	}

	#include<bits/stdc++.h>
	using namespace std;

	typedef int ElemType;
	//链式队列的节点
	typedef struct node{
	ElemType data;
	struct node *next;
	}QNode,*QNodePtr;
	//队列结构定义
	typedef struct queue{
	QNodePtr front,rear;
	}Queue,*QueuePtr;

	//初始化队列
	void InitQueue(Queue &Q){
	Q.front = Q.rear = (QNodePtr)malloc(sizeof(QNode));
	Q.front->next = NULL;
	}
	//销毁队列
	void DestroyQueue(Queue &Q){
	while(Q.front){
	Q.rear = Q.front->next;
	free(Q.front);
	Q.front = Q.rear;
	}
	Q.front = Q.rear = NULL;
	}
	//判空
	bool isEmpty(Queue Q){
	return Q.front == Q.rear;
	}
	//判满
	bool isFull(Queue Q){
	return false; //一般认为内存可以不停的申请
	}
	//入队
	bool EnQueue(Queue &Q,ElemType e){
	QNodePtr p = (QNodePtr)malloc(sizeof(QNode));
	if(p==nullptr) return false;
	p->next = NULL;
	p->data = e;
	Q.rear->next = p;
	Q.rear = Q.rear->next;
	return true;
	}
	//出队
	bool DeQueue(Queue &Q,ElemType &e){
	if(isEmpty(Q)) return false;
	QNodePtr p = Q.front->next;
	Q.front->next = p->next;
	e = p->data;
	if(Q.rear == p) Q.rear = Q.front;
	free(p);
	return true;
	}
	//打印队列
	void PrintQueue(Queue Q){
	if(isEmpty(Q)){
	printf("Empty queue.\n");
	return;
	}
	QNodePtr p = Q.front->next;
	int cnt = 0;
	while(p){
	if(cnt++) printf(" -> ");
	printf("%d",p->data);
	p = p->next;
	}
	}

	int main(){
	Queue Q;
	InitQueue(Q);
	printf("初始化队列后，队列为空吗？\n");
	if(isEmpty(Q)) printf("queue is empty.\n");
	int e;
	for (int i = 0; i < 10; i++){
	if(EnQueue(Q,i))
	printf("EnQueue %d Success\n",i);
	}
	printf("打印队列中的数据:\n");
	PrintQueue(Q);
	printf("\n取出前面6个元素：\n");
	for (int i = 0; i < 6; ++i) {
	DeQueue(Q,e);
	printf("%d ",e);
	}
	printf("\n");
	printf("队列数据如下：\n");
	PrintQueue(Q);

	return 0;
	}

	初始化队列后，队列为空吗？
	queue is empty.
	EnQueue 0 Success
	EnQueue 1 Success
	EnQueue 2 Success
	EnQueue 3 Success
	EnQueue 4 Success
	EnQueue 5 Success
	EnQueue 6 Success
	EnQueue 7 Success
	EnQueue 8 Success
	EnQueue 9 Success
	打印队列中的数据:
	0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
	取出前面6个元素：
	0 1 2 3 4 5
	队列数据如下：
	6 -> 7 -> 8 -> 9

	#include <stdio.h>
	#include <stdlib.h>

	typedef int ElemType;
	struct CycleQueue{
	int *data;
	int front,rear;
	int maxSize;
	};
	//初始化循环队列
	void InitQueue(CycleQueue &Q,int size) {
	Q.maxSize = size + 1; //循环队列的长度要比储存的数据长度要多一位，空出来一个位来区分队列空和队列满
	Q.data = (int )malloc((Q.maxSize)sizeof(int));
	Q.front = Q.rear = 0;
	}
	//销毁循环队列
	void DestroyQueue(CycleQueue &Q) {
	free(Q.data);
	Q.data = NULL;
	Q.front = Q.rear = 0;
	}
	//判空
	int isEmpty(CycleQueue Q) {
	return Q.front == Q.rear;
	}
	//判满
	int isFull(CycleQueue Q) {
	return (Q.rear + 1) % Q.maxSize == Q.front;
	}
	//出队
	int DeQueue(CycleQueue &Q,ElemType &e) {
	if(isEmpty(Q)) return 0;
	e = Q.data[Q.front];
	Q.front = (Q.front + 1) % Q.maxSize;
	return 1;
	}
	//入队
	int EnQueue(CycleQueue &Q,ElemType e) {
	if(isFull(Q)) return 0;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear + 1) % Q.maxSize;
	return 1;
	}
	void PrintQueue(CycleQueue Q){
	if(isEmpty(Q)){
	printf("Queue is empty\n");
	return;
	}
	int index = Q.front;
	int cnt = 0;
	while(index != Q.rear) { //Q.rear表示队尾的下一位，循环结束条件是index刚刚好到达rear前面那位
	if(cnt++) printf(" -> ");
	printf("%d",Q.data[index]);
	index = (index + 1) % Q.maxSize;
	}
	printf("\n");
	}

	int main(){
	CycleQueue Q;
	InitQueue(Q,9);
	printf("初始化队列后，队列为空吗？\n%d\n",isEmpty(Q));
	int e;
	for (int i = 0; i < 20; i++){
	if(EnQueue(Q,i)){
	printf("EnQueue %d Success\n",i);
	}else{
	printf("EnQueue %d Fail\n",i);
	break;
	}
	}
	printf("插入元素后，队列满了吗？\n%d\n",isFull(Q));
	printf("打印队列中的数据:\n");
	PrintQueue(Q);
	printf("取出前面6个元素：\n");
	for (int i = 0; i < 6; ++i) {
	DeQueue(Q,e);
	printf("%d\n",e);
	}
	printf("删去6个元素后，队列还有数据吗？\n%d\n",!isEmpty(Q));
	printf("队列数据如下：\n");
	PrintQueue(Q);

	return 0;
	}