第四章:栈


4.1栈的定义:后进先出

栈是允许在同一端进行插入和删除操作的数据结构。被允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为出栈(POP)。

 

由于栈规定只能在同一端进行插入和删除,因此栈的一个典型特点就是后进先出。

为了理解栈的后进先出特性,下面来看一道BAT的笔试题:

一个栈的入栈序列为ABCDE,则不可能的出栈序列为?

A.     ECDBA

B.      DCEAB

C.      DECBA

D.     ABCDE

E.      EDCBA

答案:A,B

分析:

AE最先出栈,所以ABCD已经先后入栈,所以,根据后进先出,C不可能比D先出栈

BD出,C出,EE出,AB已经先后入栈,所以,A不可能比B先出

CDEECBA

DAABBCCDDEE

EEDCBA

 

4.2栈的结构

栈的底层数据结构包含链表与数组。可以通过链表或者数组来构造栈,如下图所示:上边是基于链表的栈,下边是基于数组的栈。

   

 

4.3栈的基本操作

1栈的创建

int CreateStack();

负责初始化栈的基本结构,比如栈顶指针的初始化。

2入栈

int Push(int data);

将数据从栈顶插入

3出栈

int Pop(int *data);

获取栈顶数据,并将数据从栈顶删除

4栈空判断

int IsStackEmpty();

判断栈是否为空,栈为空,就不能再pop了。

5栈满

int IsStackFull();

判断栈是否为满,栈满就不能再插入数据了。只有基于数组的栈,才需要判断栈是否已满。

4.4基于链表的栈

现在来实现基于链表的栈的常规操作。(注意,在多线程环境下,下面的代码没有提供加锁机制,需要另外处理)。

 

先定义栈的结点结构:

typedef struct _node

{

       int value;

       struct _node *next;

}node,*pnode;

栈顶指针初始化:

node *top = NULL;

 

创建栈:

int CreateStack()

{

       top = NULL;

       return 1;

}

 

判断栈是否为空:

int IsStackEmpty()

{

       return top==NULL?1:0;//topNULL的时候,栈为空

}

入栈:

int Push(int value)

{

       node *p = (node *)malloc(sizeof(node));

       if(p==NULL)

       {

              return -1;

       }

       memset(p,0,sizeof(node));

       p->value=value;

       p->next=NULL;

 

       //栈为空的时候,插入的是第一个结点

       if(IsStackEmpty())

       {

              top=p;

              return 1;

       }

 

       //栈非空的时候,插入一个结点

       p->next = top;

       top=p;

 

       return 1;

 

}

出栈

int Pop(int *e)

{

       if(IsStackEmpty())

       {

              return -1;

       }

       if(e==NULL)

       {

              return -1;

       }

 

       //当栈只有一个结点的时候:

       if(top->next==NULL)

       {

              *e = top->value;

              free(top);

              top=NULL;

              return 1;

       }

 

       //当栈中存放不止一个元素的时候

       *e = top->value;

       node *p=top;

       top=top->next;

       free(p);

 

       return 1;

 

}

栈的遍历:

void TraverseStack()

{

       while(!IsStackEmpty())

       {

              int val;

              Pop(&val);

              printf("%d ", val);

      

       }

       printf("\n");

}

 

接口测试:

int _tmain(int argc, _TCHAR* argv[])

{

       CreateStack();

 

       for(int i=0;i<100;i++)

       {

              Push(i+1);

       }

       int val;

       Pop(&val);

       printf("val:%d\n", val);

 

       TraverseStack();

 

       return 0;

}

4.5基于数组的栈

下面来实现基于数组的栈的常规操作。(注意,在多线程环境下,下面的代码没有提供加锁机制,需要另外处理)。如下图所示,栈顶top指向数组中下一个空位:

 

#define MAXSIZE 1000//栈中数组容纳的元素个数

int Stack[MAXSIZE]={0};//栈的底层数据结构:数组stack

int top=0;//栈顶

 

创建栈

int CreateStack()

{

       top=0;//将top置零

       return 1;

}

 

判断栈是否满

int IsStackFull()

{

       return top==MAXSIZE?1:0;

}

判断栈是否空

int IsStackEmpty()

{

       return top==0?1:0;

}

入栈:

int push(int val)

{

 

       if(IsStackFull())

       {

              return -1;

       }

 

       Stack[top]=val;

       top++;

 

       return 1;

 

}

出栈:

int pop(int *e)

{

       if(IsStackEmpty())

       {

              return -1;

       }

 

       if(e==NULL)

       {

              return -1;

       }

 

       top--;

       *e = Stack[top];

 

       return 1;

}

栈的遍历:

void TraverseStack()

{

       while(!IsStackEmpty())

       {

              int val;

              pop(&val);

              printf("%d ",val);

       }

       printf("\n");

}

接口测试:

int _tmain(int argc, _TCHAR* argv[])

{

       CreateStack();

 

       for(int i=0;i<500;i++)

       {

              push(i+1);

       }

 

       int val;

       pop(&val);

       printf("val:%d\n", val);

 

       TraverseStack();

 

       return 0;

}



看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注