顺序栈，两栈共享空间，链栈1.顺序栈的基本操作：2.两栈共享空间：3.链栈的基本操作4.顺序栈与链栈的区别：5.栈的应用：

80 阅读 0 评论 53 点赞

我是靠谱客的博主超级大炮，最近开发中收集的这篇文章主要介绍顺序栈，两栈共享空间，链栈1.顺序栈的基本操作：2.两栈共享空间：3.链栈的基本操作4.顺序栈与链栈的区别：5.栈的应用：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.顺序栈的基本操作：

栈是一种特殊的线性表,线性表的顺序存储结构和链式存储结构同样适用于栈。LIFO

应用：浏览网页时的撤销回退操作

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXSIZE 1000
typedef int SElemType;
typedef struct
{
    SElemType data[MAXSIZE];
    int top;
}SqStack;
void Push(SqStack *s,SElemType e)
{
    if(s->top==MAXSIZE-1)
       {
           printf("栈已满!，不能入栈n");
       }else{
            s->top++;
            s->data[s->top]=e;
            printf("已成功入栈n");
       }
}
void Pop(SqStack *s)
{
    if(s->top==-1)
      {
          printf("栈为空！，不能出栈n");
      }else{
            s->top--;
            printf("已成功出栈n");
      }
}
int GetStackTop(SqStack *s)
{
    return s->data[s->top];
}
int main()
{
    SqStack p;
    p.top = -1;//p.top而不能是p->top
    int a,x;
    do{
        printf("请选择进栈(1)or出栈操作(2)取栈顶元素(3)退出(4):");
        cin>>a;
        switch(a)
        {
            case 1:printf("请输入元素：");
                    scanf("%d",&x);
                    Push(&p,x);
                    break;
            case 2:Pop(&p);
                    break;
            case 3:printf("栈顶元素为：%dn",GetStackTop(&p));
        }
    }while(a!=4);
    return 0;
}

2.两栈共享空间：

顺序栈存储空间的大小需要事先申请，不方便。

可以两栈共享空间，不过这种情况适用于一个栈的大小不断增大，另一个栈的大小不断减小。而且必须两栈存储相同数据类型的元素。例如：（买彩票）

#include <iostream>
#include <cstdio>
using namespace std;
#define MAXSIZE 10
typedef int SElemType;
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;
void Push(SqDoubleStack *s,int stackNumber,SElemType e)
{
    if(s->top1+1==s->top2)
    {
        printf("栈已满，不能入栈n");
    }else
    {
        if(stackNumber==1)
        {
            s->data[++s->top1]=e;
            printf("入栈1成功！n");
        }

        if(stackNumber==2)
        {
            s->data[--s->top2]=e;
            printf("入栈2成功！n");
        }

    }
}
int Pop(SqDoubleStack *s,int stackNumber)
{
    SElemType e;
    if(stackNumber==1)
    {
        if(s->top1==-1)
           {
               printf("栈1空，出栈失败！n");
           }else
           {
               e=s->data[s->top1--];

               printf("出栈1成功n");
           }

    }
    if(stackNumber==2)
    {
        if(s->top2==MAXSIZE-1)
         {
              printf("栈2空，出栈失败！n");
         }else
         {
             e=s->data[s->top2++];

             printf("出栈2成功n");
         }

    }
    return e;
}
void output(SqDoubleStack *s)
{
    int i;
    for(i=0;i<MAXSIZE;i++)
    {
        if(s->data[i])
            printf("%d ",s->data[i]);
    }
}
int main()
{
    SElemType e;
    SqDoubleStack s;
    int stackNumber;
    int x,i;
    s.top1=-1;
    s.top2=MAXSIZE;

    do{
        printf("选择入栈（1）出栈（2）输出栈（3）退出（4）");
        scanf("%d",&i);
        switch(i)
        {
            case 1:
                printf("n输入要入栈的元素：");
                scanf("%d",&x);
                printf("n选择入栈1 or 栈2:：");
                scanf("%d",&stackNumber);
                Push(&s,stackNumber,x);
                break;
            case 2:printf("选择出栈1 or栈2：");
                    scanf("%d",&stackNumber);
                    e=Pop(&s,stackNumber);
                    printf("出栈的元素为%dn",e);
                    break;
            case 3: printf("n输出栈:");
                    output(&s);
                    break;

        }
    }while(i!=4);

    return 0;
}

3.链栈的基本操作

链式存储结构头头指针，栈有指向栈顶的指针，可以将二者合二为一，不需要头结点；

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;
void Push(LinkStack *S,SElemType e)
{
     LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
     p->data=e;
     p->next = S->top;
     S->top = p;
     S->count++;
}
int Pop(LinkStack *S)
{
    LinkStackPtr p;
    SElemType e;
    if(S->count==0)
    {
        printf("栈为空，不能出栈n");
    }else
    {
        p=S->top;
        e=p->data;
        S->top = p->next;
        free(p);
        S->count--;
    }
    return e;
}
int main()
{
    LinkStack S;
    SElemType e;
    int i,x;
    S.count=0;
    do
    {
        printf("n请选择入栈（1）or出栈（2）or 退出（3）：n");
        scanf("%d",&i);
        switch(i)
        {
            case 1: printf("请输入入栈元素：");
                    scanf("%d",&x);
                    Push(&S,x);
                    break;
            case 2: e=Pop(&S);
                    printf("出栈元素为%d",e);
                    break;
        }
    }while(i!=3);

    return 0;
}