首页 > 代码库 > 顺序栈

顺序栈

2024-07-16 08:52:46   220人阅读

　　栈是限定尽在表尾进行插入或者删除操作的线性表，分为顺序栈和链式栈。

　　对于malloc()一次申请的内存地址，在逻辑上是连续的，也就是我们用的时候可以当做连续的来用，但是在物理内存上未必是连续的；

　　顺序栈：

　　　　利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设top指示栈顶元素在顺序栈中的位置，top永远指向栈顶元素的下一个元素位置，下面我们来看         一下顺序栈的基本操作和其应用如下：

      链式栈：

　　　　由单链表来实现，具体操作是在头指针head的后面进行插入或者删除操作；

　　顺序栈和链式栈比较

　　　　顺序栈需要固定空间长度，存在溢出问题，而链式栈不存在；

　　　　链式栈的每个元素都有指针域，增加了空间开销，并且求栈长度时候时间复杂度为O（n），也就是遍历整个链；

#include <iostream>using namespace std;#define  STACK_INIT_SIZE 100#define  STACKINCREMRNT 10struct Stack{    int *base;    int *top;    int stacksize;};bool InitStack(Stack &s){    s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));// 分配内存    if (!s.base)//detect     {        exit(OVERFLOW);    }    s.top=s.base;//empty stack    s.stacksize=STACK_INIT_SIZE;//init stacksize    return true;}bool StackPush(Stack &s,int e)//{    if (s.top-s.base>=s.stacksize)//very important, s.top, s.base and s.stacksize all changed    {        s.base=(int*)realloc(s.base,(s.stacksize+STACKINCREMRNT)*sizeof(int));        if (!s.base)        {            exit(OVERFLOW);        }        s.top=s.base+s.stacksize;        s.stacksize+=STACKINCREMRNT;    }    *s.top=e;    s.top++;    return true;}bool GetTop(Stack &s,int &e){    if (s.top==s.base)    {        return false;    }    else        e=*(s.top-1);    return true;}bool StackPop(Stack &s, int &e){    if (s.base==s.top)    {        return 0;    }    else    {        s.top--;        e=*s.top;    }    return true;}bool StackEmpty(Stack &s){    if (s.base==s.top)    {        return true;    }    else        return false;}void main(){    Stack s={0};    bool stats=InitStack(s);    if (stats)    {        cout<<"initial stack success!"<<endl;    }    else        cout<<"initial stack error!";    int pushnum=0,pushnum2=0;    cout<<"please input the number:";    cin>>pushnum;    StackPush(s,pushnum);    cout<<"please input the number:";    cin>>pushnum2;    StackPush(s,pushnum2);    int popnum=0;    StackPop(s,popnum);    StackPop(s,popnum);    cout<<"the popnum is:"<<popnum<<endl;    int topnum=0;    if (GetTop(s,topnum))    {        cout<<topnum<<endl;    }    else    {        cout<<"the stack is empty"<<endl;    }}//顺序栈应用  由十进制转换为8进制数void Convers8(){    int num;    Stack s={0};    InitStack(s);    cout<<"please input the 10 number:";    cin>>num;    while (num)    {        StackPush(s,num%8);        num/=8;    }    int num8;    while(!StackEmpty(s))    {        StackPop(s,num8);        cout<<num8;    }}void main(){    Convers8();    cout<<endl;}

 

下面是链式栈的基本操作

#include <iostream>using namespace std;//栈的链式存储结构//栈顶指针为链表的头结点//插入元素要在头结点后面插入struct ChainStack{    ChainStack * next;    int data;};ChainStack *InitStack(){    ChainStack*    head=(ChainStack*)malloc(sizeof(ChainStack));    head->next=NULL;    return head;}void PushStack(ChainStack *head,int num)//在头结点后插入{    ChainStack *p=(ChainStack*)malloc(sizeof(ChainStack));    p->data=http://www.mamicode.com/num;    p->next=head->next;    head->next=p;}bool PopStack(ChainStack *head,int &num){        if (head->next==NULL)    {        cout<<"the stack is empty"<<endl;        return false;    }    else        {            ChainStack *p=head->next;            num=p->data;            head->next=p->next;            free(p);//别忘了释放内存        }    return true;}void main(){    ChainStack*s=NULL;    s=InitStack();    int pushnum=0;    cout<<"请输入栈区总长度：";    int leng;    cin>>leng;    for (int i=0;i<leng;i++)    {        cout<<"please input the "<<i+1<<" number: ";        cin>>pushnum;        PushStack(s,pushnum);    }    int popnum=0;    for ( ;PopStack(s,popnum); )    {        cout<<"the pop num is "<<popnum<<endl;    }}

 

　　　　


联系
我们