DataStructure_SqStack

栈的定义：

#include "iostream"
using namespace std;
typedef int ElemType;
#define Maxsize 10              //定义栈的最大个数
typedef struct {
    ElemType data[Maxsize];     //静态数组存放中元素
    int top;                    //栈顶指针
}SqStack;

初始化栈

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

注释:
	我们在初始化栈的时候也就是把我们的指针指向外边

新元素入栈

//新元素入栈
bool Push(SqStack &S,ElemType x){
    if (S.top==Maxsize-1){      //栈满了
        return false;
        cout<<"The Stack is Full"<<endl;
    }
    S.top = S.top + 1;          //指针先加一
    S.data[S.top] = x;          //新元素入栈
    return true;
}

注释:
	我们在存放数据的时候也就是这样的
        [4][]
        [3][]
        [2][]
        [1][]	我们在第0各位插入数据首先得让指针指向0对吧 所以上面的操作使得指针先+1 
        [0][]	然后再赋值并且此时的指针指向的是0。	
        -1		开始的top指向-1对吧
        

出栈操作

bool Pop(SqStack &S,ElemType &x){
    if (S.top==-1){             //栈为空
        return false;
        cout<<"The Stack is Empty"<<endl;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    return true;
}


注释:
	我们删除放数据的时候也就是这样的
        [4][]		注意我们删除的时候只能删除栈顶元素，此时我们都
        [3][]		知道现在top指向的是栈顶元素，那么我们就在这个时候
        [2][]		取出栈顶元素的值，赋给x，此时这个节点就值了
        [1][]	 	那么指针指向的值4也要减一了
        [0][]	

读取栈顶元素

//读取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if (S.top == -1){
        return false;
    }
    x = S.data[S.top];
    return true;
}

注释:
	这个和删除没多大区别

所有代码

#include "iostream"
using namespace std;
typedef int ElemType;
#define Maxsize 10              //定义栈的最大个数
typedef struct {
    ElemType data[Maxsize];     //静态数组存放中元素
    int top;                    //栈顶指针
}SqStack;
//初始化栈顶指针
void InitStack(SqStack &S){
    S.top = -1;
}
void PrintSqStack(SqStack S)			//遍历栈
{
    int tmp = S.top;
    while(tmp!=-1)						//如果tmp==-1说明遍历结束
    {
        cout<<S.data[tmp--]<<" ";
    }
}
//新元素入栈
bool Push(SqStack &S,ElemType x){
    if (S.top==Maxsize-1){      //栈满了
        return false;
        cout<<"The Stack is Full"<<endl;
    }
    S.top = S.top + 1;          //指针先加一
    S.data[S.top] = x;          //新元素入栈
    return true;
}
//出栈操作(也就是我们的删除)
bool Pop(SqStack &S,ElemType &x){
    if (S.top==-1){             //栈为空
        return false;
        cout<<"The Stack is Empty"<<endl;
    }
    x = S.data[S.top];
    S.top = S.top - 1;
    return true;
}
//读取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if (S.top == -1){
        return false;
    }
    x = S.data[S.top];
    return true;
}
int main(){
    SqStack s;							    //声明一个顺序栈
    InitStack(s);							//初始化一个顺序栈
    ElemType x ;
    for(int i=1;i<=5;i++)
    {
        Push(s,i);							//入栈
        cout<<"栈加入元素:"<<i<<endl;
    }
    PrintSqStack(s);
    GetTop(s,x);
    cout<<"栈找出栈顶元素"<<x<<endl;
    PrintSqStack(s);
    ElemType y;
    Pop(s,y);
    cout<<"栈取出栈顶元素"<<y<<endl;
    PrintSqStack(s);
}

程序输出:

栈加入元素:1
栈加入元素:2
栈加入元素:3
栈加入元素:4
栈加入元素:5
5 4 3 2 1
栈找出栈顶元素5
5 4 3 2 1
栈取出栈顶元素5
4 3 2 1

特别的我们有

共享栈

#include "iostream"
using namespace std;
typedef int ElemType;
#define Maxsize 10              //定义栈的最大个数
typedef struct {
    ElemType data[Maxsize];     //静态数组存放中元素
    int top0;                   //栈底指针
    int top1;					//栈顶指针
}SqStack;

//初始化栈顶指针
void InitStack(SqStack &S){
    S.top0 = -1;
    S.stop1 = Maxsize -1;
}

栈的链式存储

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