栈

栈的顺序存储结构

顺序栈的实现

栈的顺序存储类型可描述为：

#define MaxSize 50				//定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];			//存放栈中元素
    int top;						//栈顶指针
}SqStack;

顺序栈的基本运算

初始化

void InitStack(SqStack &s){
    s.top=-1;					//初始化栈顶指针
}

判栈空

bool StackEmpty(SqStack S){
    if(s.top == -1)			//栈空
        return true;
    else					//不空
        return false;      
}

进栈

bool Push(SqStack &s,ElemType x){
    if(s.top == MaxSize-1)				//栈满，报错
        return false;
    s.data[++s.top]=x;					//指针先加1，在入栈
    return true;
}

出栈

bool Pop(SqStack &s,ElemType &x){
    if(s.top == -1)						//栈空，报错
        return false;
    x=s.data[s.top--];					//先出栈，指针再减1
    return true;
}

读栈顶元素

bool GetTop(SqStack s,ElemType &x)
{
    if(s.top == -1 )					//栈空，报错
        return false;
   	x=s.data[s.top];					//x记录栈顶元素
    return true;
}

顺序栈的完整操作

程序源代码：

#include<bits/stdc++.h>
using namespace std; 
typedef int ElemType;
#define MaxSize 50				//定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];			//存放栈中元素
    int top;						//栈顶指针
}SqStack;
void InitStack(SqStack &s){
    s.top=-1;					//初始化栈顶指针
}
bool StackEmpty(SqStack S){
    if(S.top == -1)			//栈空
        return true;
    else					//不空
        return false;      
}
bool Push(SqStack &s,ElemType x){
    if(s.top == MaxSize-1)				//栈满，报错
        return false;
    s.data[++s.top]=x;					//指针先加1，在入栈
    return true;
}
bool Pop(SqStack &s,ElemType &x){
    if(s.top == -1)						//栈空，报错
        return false;
    x=s.data[s.top--];					//先出栈，指针再减1
    return true;
}
bool GetTop(SqStack s,ElemType &x)
{
    if(s.top == -1 )					//栈空，报错
        return false;
   	x=s.data[s.top];					//x记录栈顶元素
    return true;
}
void PrintSqStack(SqStack s)			//遍历栈 
{
	int tmp = s.top;
	while(tmp!=-1)						//如果tmp==-1说明遍历结束 
	{									 
		cout<<s.data[tmp--]<<" ";
	}
	cout<<endl; 
}
int main()
{
	SqStack s;							//声明一个顺序栈 
	InitStack(s);						//初始化一个顺序栈 
	for(int i=1;i<=5;i++)
	{
		Push(s,i);						//入栈 
	}
	PrintSqStack(s);					//遍历 
	for(int i=1;i<=5;i++){										//为了对比GetTop和Pop操作 
		int x; 
		GetTop(s,x);											//取栈顶元素 
		cout<<"这是GetTop操作,栈顶元素为"<<x<<endl;
		cout<<"这是GetTop操作后的栈遍历:";
		PrintSqStack(s); 
		Pop(s,x);												//出栈 
		cout<<"这是Pop操作,出栈的元素为"<<x<<endl;
		if(!StackEmpty(s))
		{
			cout<<"这是Pop操作后的栈遍历:";
			PrintSqStack(s); 
		}else{
			cout<<"此时栈空！"<<endl;
		}
		
	}
	return 0;
}

程序输出：

5 4 3 2 1
这是GetTop操作,栈顶元素为5
这是GetTop操作后的栈遍历:5 4 3 2 1
这是Pop操作,出栈的元素为5
这是Pop操作后的栈遍历:4 3 2 1
这是GetTop操作,栈顶元素为4
这是GetTop操作后的栈遍历:4 3 2 1
这是Pop操作,出栈的元素为4
这是Pop操作后的栈遍历:3 2 1
这是GetTop操作,栈顶元素为3
这是GetTop操作后的栈遍历:3 2 1
这是Pop操作,出栈的元素为3
这是Pop操作后的栈遍历:2 1
这是GetTop操作,栈顶元素为2
这是GetTop操作后的栈遍历:2 1
这是Pop操作,出栈的元素为2
这是Pop操作后的栈遍历:1
这是GetTop操作,栈顶元素为1
这是GetTop操作后的栈遍历:1
这是Pop操作,出栈的元素为1
此时栈空！

栈的链式存储结构

栈的链式存储类型可描述为

typedef struct Linknode{
    ElemType data;						//数据域
    struct Linknode *next;				//指针域
}*Linknode;								//栈类型操作