堆栈学习笔记

顺序栈的表示和实现

#include <iostream>
using namespace std;

#define MAXSIZE 100
#define another 50

typedef struct
{
    int *base;
    int *top;
    int stacksize;
}SqStack;

//顺序栈的初始化
void InitStack(SqStack &S)
{
    S.base=new int[MAXSIZE];
    S.top=S.base;
    S.stacksize=MAXSIZE;
}
//入栈
void Push(SqStack &S,int e)
{
    if(S.top-S.base>=S.stacksize)
    {
        S.base=(int *)realloc((S.base,(another+S.stacksize)*sizeof(int));
        /*realloc(void *__ptr, newsize)：更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
        参数ptr为原有的空间地址,newsize是重新申请的地址长度.*/
        S.top=S.base+S.stacksize;
        S.stacksize+=another;
    }
    *S.top++=e;
}

//出栈
int Pop(SqSatck &S,int &e)
{
    if(S.base==S.top)
        return false;
    else
        return e=*--S.top;
}
//取栈顶元素
int GetTop(SqStack S)
{
    if(S.base==S.top)
        return false;
    else 
        return *(S.top-1);

}

//判断是否为空
bool IsEmpty(SqStack &S)
{
    if(S.top==S.base)
        return true;
    return false;
}
int main()
{

    return 0;
}

链栈的实现与表示

#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;


typedef struct StackNode
{
    int data;
    struct stackNode *next;
}StackNode,*LinkStack;

//顺序栈的初始化
LinkStack CreateStack()
{
    StackNode S;
    S=(LinkStack)malloc(sizeof(StackNode));
    S->next=NULL;
    return S;
}

//判断是否为空
int IsEmpty(LinkStack S)
{
   return (S->next==NULL);
}

//入栈
void Push(LinkStack &S,int &e)
{
    /*将元素item压入堆栈S*/
    Linkstack TmpCell;
    TmpCell=(LinkStack)malloc(sizeof(StackNode));
    TmpCell->data=e;
    Tmpcell->next=S->next;
    S->next=TmpCell;
}

//出栈
int Pop(LinkStack &S，int &e )
{
    /*删除并返回堆栈S的栈顶元素*/
    LinkStack FirstCell;
    int tope;
    if(IsEmpty(S))
    {
        printf("堆栈空");
        return NULL;
    }else{
        FirstCell=S->next;
        S->next=FirstCelll;
        tope=FirstCell->data;
        delete(FirstCell);
        return tope;
    }
}
//取栈顶元素
int GetTop(LinkStack S)
{
    if(S->next)
        return S->next->data;
}


int main()
{

    return 0;
}

循环队列的顺序表示及实现？？？写得有些乱了，还需重新整理

#include <iostream>
using namespace std;

#define MAXQSIZE 100
typedef struct
{
    int *base;
    int front;//队伍中第一个元素的前一个位置
    int rear;//实际上最后一个元素的位置
}SqQueue,*Queue;

//循环队列的初始化
void InitQueue(SqQueue &Q)
{
    Q.base=new int[MAXQSIZE];
    Q.front=Q.rear=0;//头指针和尾指针置零，队列为空
}

//求队列的长度
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

//循环队列的入队
void AddQ(SqQueue &Q,int e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)//队满
        return ;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    Q.base[Q.rear]=e;
}

//循环队列的出队
int DeleteQ(SqQueue &Q)
{
    if(Q.front==Q.rear)//队列为空
        return false;
    Q.front=(Q.front+1)%MAXQSIZE;
    return Q.base[Q.front];
}


int main()
{

}

---

运算符优先级

例如,‘+’‘+’：左边的‘+’比右边的‘+’优先级大。

1.后缀表达式求值策略：

从左向右“扫描”，逐个处理运算数和运算符号。

2.如果将ABCD四个字符按顺序压入堆栈，是不是ABCD的所有排列都可能是出栈的序列？可以产生CADB这样的序列吗？

如果有三个字符ABC出入栈时，全排列有3！=6种可能。其中的CAB是没法生成的。
因为先输出C，需要C进栈再出栈，而要求按照ABC这样的顺序进栈，所以C出栈时AB必然还在栈里，而且A还压在B下面。 其他五种排列都会生成。
如果有四个字符ABCD出入栈时，排列有4！=24种可能。 不是所有排列都有可能时出栈的序列，像CADB这样的序列是产生不了的。
四个字符出栈的所有可能序列有几种？（14种）？？？？（待解决。。。现在有些疲惫，比较清醒的时再来思考）