栈的实现顺序存储和链式存储

本是古典何须时尚 2024-02-19 16:15 81阅读 0赞

栈是一种特殊的线性结构，只能对其一段进行操作，有两种存储方式：顺序和链式。

都不难（不用担心）

1.顺序存储：

\#include<iostream>  
using namespace std;  
\#include<stdio.h>  
\#define ok 1  
\#define error 0  
\#define overflew -1  
\#define maxsize 10  
typedef int SElemType;  
typedef int Status;  
typedef struct  
\{  
SElemType \*base;  
SElemType \*top;  
int stacksize;  
\}SqStack;  
Status InitStack(SqStack &s) //创建一个新栈  
\{  
s.base=new SElemType\[maxsize\];  
if(!s.base) return error;  
s.top=s.base;  
s.stacksize=maxsize;  
return ok;  
\}  
Status Push(SqStack &s,SElemType e) //入栈  
\{  
if(s.top-s.base==s.stacksize)  
return overflew;  
\*s.top++=e;  
return ok;  
\}  
Status Pop(SqStack &s,SElemType &e) //出栈  
\{  
if(s.top==s.base) return error;  
e=\*--s.top;  
return ok;  
\}  
SElemType Gettop(SqStack s) //取栈顶元素（而非出栈，出栈是把栈顶元素取出后，删除；而取栈顶元素并未改变栈的元素）  
\{ //--s->top和s->top-1不一样，前者改变了指针的指向，而后者并未改变  
if(s.top==s.base) return error;  
return \*(s.top-1);  
\}  
Status AssignStack(SqStack &s) //顺序栈的初始化  
\{  
int i;  
SElemType e;  
cout<<"请输入你要入栈的元素个数："<<endl;  
cin>>i;  
for(;i>0;i--)  
\{  
cout<<"请输入你要入栈的元素："<<endl;  
cin>>e;  
Push(s,e);  
\}  
return ok;  
\}  
Status DisplayStack(SqStack s) //查看栈中元素  
\{  
SElemType \* p;  
cout<<"此时此刻栈中元素为："<<endl;  
for(p=s.top-1;p>=s.base;p--)  
\{  
cout<<\*p<<" ";  
\}  
return ok;  
\}  
int main()  
\{  
SqStack s;  
int e;  
InitStack(s);  
AssignStack(s);  
DisplayStack(s);  
cout<<"此时栈顶元素为："<<endl;  
cout<<Gettop(s)<<endl;  
cout<<"请输入你要入栈的元素："<<endl;  
cin>>e;  
Push(s,e);  
DisplayStack(s);  
cout<<endl;  
cout<<"此时栈顶元素为："<<endl;  
cout<<Gettop(s)<<endl;  
return 0;  
\}

2.链式栈

\#include<iostream>  
\#include<stdio.h>  
using namespace std;  
\#define null 0  
\#define ok 1  
\#define error 0  
\#define overflew -1  
\#define maxsize 10  
typedef int ElemType;  
typedef int Status;  
typedef struct StackLnode  
\{  
ElemType data;  
struct StackLnode \*next;  
\}StackLnode,\*LinkStack;  
Status InitStack(LinkStack &s)  
\{  
s=null;  
return ok;  
\}  
Status Push(LinkStack &s,ElemType e)  
\{  
StackLnode \*p;  
p=new StackLnode;  
p->data=e;  
p->next=s;  
s=p;  
return ok;  
\}  
Status Pop(LinkStack &s,ElemType &e)  
\{  
StackLnode \*p;  
if(s==null) return error;  
e=s->data;  
p=s;  
s=s->next;  
delete p;  
return ok;  
\}  
ElemType GetTop(LinkStack s)  
\{  
if(s==null) return error;  
return s->data;  
\}  
Status AssignStack(LinkStack &s)  
\{  
int i,e;  
cout<<"请输入你要入栈元素的个数："<<endl;  
cin>>i;  
for(;i>0;i--)  
\{  
cout<<"请输入你要入栈的元素："<<endl;  
cin>>e;  
Push(s,e);  
\}  
return ok;  
\}  
Status DisplayStack(LinkStack s)  
\{  
StackLnode \*p;  
p=s;  
cout<<"此时栈中的元素为："<<endl;  
while(p!=null)  
\{  
cout<<p->data<<" ";  
p=p->next;  
\}  
return ok;  
\}  
int main()  
\{  
LinkStack s;  
int m,n;  
InitStack(s);  
AssignStack(s);  
cout<<"此时栈顶元素为："<<endl;  
cout<<GetTop(s)<<endl;  
DisplayStack(s);  
cout<<"请输入你要入栈的元素："<<endl;  
cin>>m;  
Push(s,m);  
DisplayStack(s);  
cout<<"此时栈顶元素为："<<endl;  
cout<<GetTop(s)<<endl;  
Pop(s,n);  
cout<<"出栈元素为："<<n<<endl;  
DisplayStack(s);  
cout<<"此时栈顶元素为："<<endl;  
cout<<GetTop(s)<<endl;  
return 0;  
\}