数据结构-3

顺序栈

【Elemtype为数据类型】

顺序栈本身是操作受限制的顺序表，只能在栈顶做插入删除，称入栈出栈，因为操作受限，算法相较普通顺序表简单。

创建

typedef struct 
{
	Elemtype *base;					//定义栈底指针
	Elemtype *top;					//定义栈顶指针
	int maxsize;					//定义最大栈的最大容量
}SQstack;

初始化

bool initstack(SQstack &sq)			//传址需要初始化的表
{
	sq.base=new Elemtype[MAXSIZE];
	//分配大小为MAXSIZE的空间，并返回首地址给表的栈底指针
	if(!sq.base) return false;      //若分配失败则返回
	sq.top=sq.base;					//栈顶指针等于栈底指针，表示空栈
	sq.maxsize=MAXSIZE;				//记录栈的最大容量为MAXSIZE
	return true;					//返回创建成功
}

入栈（从栈顶插入）

bool Push(SQstack &sq,Elemtype e)		//传址需要操作的栈，传值需要入栈的值
{
	if(sq.top-sq.base>=sq.maxsize) return false;
    //若栈顶指针与栈底指针的差为最大空间（即栈满），返回入栈失败
    *sq.top=e;
	//栈顶指针总是指在栈顶元素的下一个位置，故而直接赋值
	sq.top++;							//栈顶指针后移
	return true;						//返回入栈成功
}

出栈（从栈顶删除）

bool Pop(SQstack &sq,Elemtype &e)			//传址需要操作的表和出栈的元素
{
	if(sq.top==sq.base) return false;
	//若栈顶指针与栈底指针相同（即栈空），则返回失败
	sq.top--;
	//栈顶指针总是指在栈顶元素的下一个位置，故而栈顶指针后移
	e=*sq.top;								//将出栈的元素传给e
	return true;
}

取栈顶（取值）

Elemtype gettop(SQstack &sq)
//传址需要操作的表，返回栈顶元素，该操作只取栈顶，不修改栈顶指针
{
	if(sq.top!=sq.base)			//若该栈非空
	{
	return *(sq.top-1);			//取栈顶指针的前一个位置，即栈顶元素向外传递
	}
}

链式栈

【Elemtype为数据类型】

在无法估计栈数据量时，通常采用链式栈，而且因为栈的主要操作是插入和删除，所以用链表的头部作栈顶更加方便。

创建

typedef struct Lnode
{
	Elemtype data;			//定义链表结点的数据域
	struct Lnode *next;		//定义指向下一节点的指针域
}*Linkstack;

初始化

bool initstack(Linkstack &ls)
{
	ls=NULL;
	//由于栈不需要对栈顶以外的元素操作，故而不需要设置头结点来使表头操作与表中表尾一致
	return true;			//返回初始化成功
}

入栈（从栈顶插入）

bool Push(Linkstack &ls,Elemtype e)		//传址需要操作的表，传值需要插入的元素
{
	Lnode *p;
	p=new Lnode;				//重新分配一个结点空间，首地址赋给p
	p->data=e;					//新结点的数据域为e
	p->next=ls;					//新结点的指针域指向头指针ls，即将新结点作头插
	ls=p;						//头指针前移
	return true;				//返回入栈成功
}

出栈（从栈顶删除）

bool Pop(Linkstack &ls，Elemtype &e)   //传址需要操作的表和出栈的元素
{
	if(ls==NULL) return false;		//栈空则返回删除失败
	e=ls->data;						//e接收出栈元素
	Lnode *p=ls;					//定义一个p指针指向原栈顶元素
	ls=ls->next;					//让头指针后移
	delete p;						//删除p指向的结点
	return true;					//返回删除完成
}

取栈顶（取值）

Elemtype gettop(Linkstack &ls)	//传址需要操作的表
{
	if(ls!=NULL)				//栈非空
	return ls->data;			//返回栈顶元素的值，栈顶指针不变
}

实际题目

R7-1 堆栈操作合法性 (20 分)

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式:
输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式:
对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

解法：

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

typedef struct
{
    char *top;
    char *base;
    int size;
}SQstack;

bool init(SQstack &sq,int m)
{
    sq.base=new char[m];
    if(!sq.base) return false;
    sq.top=sq.base;
    sq.size=m;
    return true;
}

bool pop(SQstack &sq)
{
    if(sq.top==sq.base) return false;
    sq.top--;
    return true;
}

bool push(SQstack &sq,char e)
{
    if(sq.top-sq.base==sq.size) return false;
    *sq.top=e;
    sq.top++;
    return true;
}

int main()
{
    int n,m,i,j=0;
    bool flag=true;
    cin>>n>>m;
    string str;
    SQstack L;
    for(i=0;i<n;i++)
    {
        init(L,m);
        cin>>str;
        flag=true;
        for(j=0;str[j]!='\0';j++)
        {
            if(str[j]=='S') 
            {
                flag=push(L,str[j]);
            }
            if(str[j]=='X') 
            {
                flag=pop(L);
            }
        }
    if(L.base==L.top&&flag==true) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }
    return 0;
}

R7-2 回文判断 (20 分)

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。

输入格式:
输入待判断的字符序列，按回车键结束，字符序列长度<20。

输出格式:
若字符序列是回文，输出“YES”；否则，输出“NO”。

输入样例:

abdba

输出样例:

YES

解法：

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

typedef struct 
{
    char *top;
    char *base;
    int size;
}SQstack;

bool init(SQstack &sq)
{
    sq.base=new char[20];
    if(!sq.base) return false;
    sq.top=sq.base;
    sq.size=20;
    return true;
}

bool push(SQstack &sq,char a)
{
    if(sq.top-sq.base==sq.size) return false;
    *sq.top=a;
    sq.top++;

    return true;
}

bool pop(SQstack &sq)
{
    if(sq.top==sq.base) return false;
    sq.top--;

    return true;
}

bool gettop(SQstack &sq,int &a)
{
    if(sq.base==sq.top) return false;
    a=*(sq.top-1);
    return true;
}

int main()
{
    SQstack L;
    init(L);
    string str;
    int i,n=0,a;
    bool flag=true;
    cin>>str;
    n=str.size();
    if(n%2==0)
    {

        for(i=0;i<n;i++)
        {
            if(i<n/2) push(L,str[i]);
            else 
            {

                gettop(L,a);

                if(str[i]==a) pop(L);
                else 
                {
                    flag=false;
                    break;
                }
            }
        }
    }
    else
    {

        for(i=0;i<n;i++)
        {
            if(i==(n-1)/2);
            else 
            {
                if(i<(n-1)/2) push(L,str[i]);
                else 
                {
                    gettop(L,a);

                    if(str[i]==a) pop(L);
                    else 
                    {

                        flag=false;
                        break;
                    }
               }
        }
    }
    }
            if(flag==true) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
}

R7-3 括号匹配 (20 分)

检查一段C语言代码的小括号( )、 中括号 [ ] 和大括号{ } 是否匹配。

输入格式:
在一行中输入一段C语言代码，长度不超过1000个字符（行末以换行符结束）。

输出格式:
第一行输出左括号的数量和右括号的数量，中间以一个空格间隔。
若括号是匹配的，在第二行打印YES，否则打印NO。

输入样例1:

for(int i=0; i<v; i++){ visited[i] = 0; for(int j=0; j<v; j++) scanf("%d",&(g->Adj[i][j])); }

输出样例1:

8 8
YES

输入样例2:

for(int i=0; i<v; i++) a(i]=0;

输出样例2:

2 2
NO

解法：

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

typedef struct
{
    char *top;
    char *base;
    int size;
}SQstack;

bool init(SQstack &sq)
{
    sq.base=new char[500];
    if(!sq.base) return false;
    sq.top=sq.base;
    sq.size=500;
    return true;
}

bool push(SQstack &sq,char a)
{
    if(sq.top-sq.base==sq.size) return false;
    *sq.top=a;
    sq.top++;
    return true;
}

bool pop(SQstack &sq)
{
    if(sq.top==sq.base) return true;
    sq.top--;
    return true;
}

bool gettop(SQstack &sq,char &a)
{
    if(sq.top==sq.base) return false;
    a=*(sq.top-1);
    return true;
}

int main()
{
    SQstack L;
    init(L);
    char a='1';
    bool flag=true;
    int i,left=0,right=0,k=0;
    char str[500];
    for(i=0;i<500;i++)
    {
        cin>>str[i];
        k++;
    }
    for(i=0;i<k;i++)
    {
        if(str[i]=='('||str[i]=='['||str[i]=='{')
        {
            left++;
            push(L,str[i]);
        }
        else
        {
        if(str[i]==')'||str[i]==']'||str[i]=='}')
        {
            right++;
            gettop(L,a);
            if((str[i]==')'&&a=='(')||(str[i]==']'&&a=='[')||(str[i]=='}'&&a=='{'))
            {
                pop(L);
            }
            else flag=false;
        }
        }
    }
    if(L.top!=L.base) flag=false;
    if(left==0&&right==0) flag=true;
    cout<<left<<" "<<right<<endl;
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}