【数据结构】栈

1.1 什么是栈

1.2 顺序栈

1.2.1 特性

1.3 链式栈

1.3.1 特性

总结：

1.1 什么是栈

栈是只能在一端进行插入和删除操作的线性表(又称为堆栈)，进行插入和删除操作的一端称为栈顶，另一端称为栈底。

特点：栈是先进后出FILO(First In Last Out)

( LIFO(Last In First Out))

1.2 顺序栈

1.2.1 特性

逻辑结构：线性结构

存储结构：顺序存储

操作：创建、入栈、出栈、清空、判空和判满

创空：

#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct seqstack
{datatype *data; //指向装数据的数组的指针int maxlen;     //保存数组元素的个数（也就是栈的容量）int top;        //成为栈针，也就是栈顶的位置。使用时和之前顺序表中的last用法一样。
} seqstack_t;//创建空栈
seqstack_t *createEmptySeqstack(int len)
{//1.申请空间存放栈的结构体大小空间seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (NULL == p){perror("p malloc err");return NULL;}//2. 初始化p->maxlen = len;p->top = -1; //类似于顺序表中的last,表示栈顶也就是最后一个有效元素的下标。此时数组中没有数据，可以置为-1,那么来了第一个数据以后就可以加一变成0。p->data = (datatype *)malloc(sizeof(datatype) * len);if (NULL == p->data){perror("p->data malloc err");return NULL;}return p;
}//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{return p->top + 1 == p->maxlen;
}//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{//1. 判满if (isFullSeqStack(p)){printf("pushStack err\n");return -1;}//2. 将栈针p->top往上移动一个单位p->top++;//3. 将数据入栈p->data[p->top] = data;return 0;
}//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{return p->top == -1;
}//出栈
int popSeqStack(seqstack_t *p)
{//1. 判空if (isEmptySeqStack(p)){printf("popSeqStack err\n");return -1;}//2. 往下移动栈针p->top--;//3. 将之前栈顶数据出栈return p->data[p->top + 1];
}//清空
void clearSeqStack(seqstack_t *p)
{p->top = -1;
}//获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int getTopSeqStack(seqstack_t *p)
{if (!isEmptySeqStack(p))return p->data[p->top];return -1;
}int main(int argc, char const *argv[])
{seqstack_t *p = createEmptySeqstack(6);pushStack(p, 1);pushStack(p, 2);pushStack(p, 3);printf("top is: %d\n", getTopSeqStack(p));while (!isEmptySeqStack(p))printf("%d\n", popSeqStack(p));return 0;
}

练习：

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

A. 1,4,3,2 (1进1出，234进，4出，3出，2出)

B. 2,3,4,1 (12进，2出，3进，3出，4进，4出，1出)

C. 3,1,4,2

D. 3,4,2,1 (123进，3出，4进，4出，2出，1出)

2. 下列叙述正确的是( )

A. 线性表是线性结构

B. 栈与队列是非线性结构

C. 线性链表是非线性结构

D. 二叉树是线性结构

3. 下列关于栈叙述正确的是( )

A.在栈中只能插入数据

B.在栈中只能删除数据

C.栈是先进先出的线性表

D. D.栈是先进后出的线性表

4. 看以下程序有什么问题？

#include <stdio.h>
#include <stdlib.h>void get_mem(int *q)    //q=NULL
{q = (int *)malloc(sizeof(int)); //开辟空间大小不够
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(p); //p=NULLfor (i = 0; i < 10; i++)p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}

错误：相当于值传递，传递给函数的是NULL，函数内改变q是不会影响到主函数的p的。函数调用结束后p还是为NULL。开辟空间大小也不够。

修改：可以通过返回值，或者传递二级指针

#include <stdio.h>
#include <stdlib.h>void get_mem(int **q)    //q=&p
{*q = (int *)malloc(sizeof(int)*10); //*q= *&p = p//通过q里面的p的地址真的找到主函数中的p了
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(&p); //p=malloc的返回值//相当于地址传递，函数调用结束后，p真的指向了函数内开辟的堆区空间了。for (i = 0; i < 10; i++)p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}

1.3 链式栈

1.3.1 特性

逻辑结构：线性结构

存储结构：链式存储

操作：创建、入栈、出栈、判空、清空

出栈：

#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node
{datatype data;struct node *next;
} link_node_t, *link_node_p;//创建一个空链式栈
void createEmptyLinkStack(link_node_t **ptop) //ptop=&top
{*ptop = NULL; //*ptop=top
}//入栈, data是入栈的数据
//参数上之所以采用二级指针，因为我们要//随着入栈添加新的节点作为头，top需要永远指向当前链表的头//那么修改main函数中的top，我们能采用地址传递。
int pushLinkStack(link_node_t **ptop, datatype data) //ptop=&top
{//1.创建一个新节点用pnew指针去接收link_node_p pnew = (link_node_p)malloc(sizeof(link_node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}//2.初始化新节点pnew->data = data;pnew->next = NULL;//3.将新节点链接老链表的栈顶节点pnew->next = *ptop; //*ptop=top//4.移动栈针，栈针要永远指向新节点*ptop = pnew;return 0;
}//判断栈是否为空
int isEmptyLinkStack(link_node_t *ptop)
{return NULL == ptop;
}//出栈
datatype popLinkStack(link_node_t **ptop) //ptop=&top
{//1.容错判断：判空if (isEmptyLinkStack(*ptop)) //*ptop=top{printf("isEmptyLinkStack\n");return -1;}//2.定义一个指针pdel，记录此时栈顶节点，也就是将要删除的节点。link_node_p pdel = *ptop;//3.定义一个临时变量，保存要出栈数据，也就是此时栈顶节点中数据datatype temp = (*ptop)->data;//4.将栈针向后移动一个单位*ptop = (*ptop)->next;//5.释放要删除节点free(pdel);pdel = NULL;//6.返回要出栈数据return temp;
}//清空栈
void clearLinkStack(link_node_t **ptop)
{//只要不为空就出栈，直到为空为止while (!isEmptyLinkStack(*ptop))printf("%d ", popLinkStack(ptop));printf("\n");
}//求长度
//用一级指针，是因为只是求长度，不需要修改main函数中top指针的指向
int lengthLinkStack(link_node_t *ptop)
{int len = 0;while (ptop != NULL){len++;ptop = ptop->next;}return len;
}//获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype getTopLinkStack(link_node_t *ptop)
{//只要不是空就返回栈顶数据if(!isEmptyLinkStack(ptop))return ptop->data;return -1;
}int main(int argc, char const *argv[])
{link_node_p top;createEmptyLinkStack(&top);pushLinkStack(&top, 1);pushLinkStack(&top, 2);pushLinkStack(&top, 3);printf("top is:%d\n",getTopLinkStack(top));printf("len=%d\n",lengthLinkStack(top));clearLinkStack(&top);return 0;
}