目录
4.栈 stack
4.2.1 特性
练习：
4.3 链式栈
4.3.1 特性
总结：
4.栈 stack
4.2.1 特性
逻辑结构：线性结构
存储结构：顺序结构
操作：创建、入栈、出栈、判空和判满
创空：
入栈：
出栈：
代码实现：
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{
int maxlen; //表示数组元素总个数
datatype *data; //指向存放数据的数组的指针
int top; //栈顶有可以称栈针，本质还是最后一个有效元素下标等同于之前学的顺序表的last
} seqstack_t;
//创建空顺序栈, len代表创建栈时的最大长度
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->top = -1; //如同之前的last初始化为-1，因为元素个数是0，下标是0-1=-1
p->maxlen = len; //保存数组长度可以通过传参获取
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. 判满： p->top + 1 == p->maxlen
if (isFullSeqStack(p))
{
printf("pushStack err\n");
return -1;
}
// 让top栈顶加一
p->top++;
// 将数据入栈
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\n");
return -1;
}
//printf("%d\n", p->data[p->top]); //或者加打印也可以
//2. 将栈针top减一
p->top--;
//3. 返回要出栈数据
return p->data[p->top + 1];
}
int main(int argc, char const *argv[])
{
seqstack_t *p = createEmptySeqStack(6);
for (int i = 0; i < 7; i++)
pushStack(p, i); //最后报一个pushStack err，因为栈满了
while (!isEmptySeqStack(p))
printf("%d\n", popSeqStack(p)); //5 4 3 2 1 0 后进先出
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
- 下列叙述正确的是( )
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
- 二叉树是线性结构
3. 下列关于栈叙述正确的是( )
A.在栈中只能插入数据
B.在栈中只能删除数据
C.栈是先进先出的线性表
D.栈是先进后出的线性表
4.请问下面的程序有问题吗？如果有问题在哪儿？
#include <stdio.h>
#include <stdlib.h>
void get_mem(int *q) //q=NULL
{
q = (int *)malloc(sizeof(int)); //改变q不会影响到函数外的p， 开辟空间也不够
}
int main(int argc, char const *argv[])
{
int i;
int *p = NULL;
get_mem(p); //函数调用完成后p还是等于NULL
for (i = 0; i < 10; i++)
p[i] = i;
for (i = 0; i < 10; i++)
printf("%d\n", p[i]);
free(p);
return 0;
}
错误：相当于值传递，改变函数内的q不会影响到主函数的p，函数调用后p还是等于NULL。再一个开辟空间大小不够，只开辟了4字节。
修改：可以通过传递二级指针，或者返回值
#include <stdio.h>
#include <stdlib.h>
void get_mem(int **q) //q=&p
{
*q = (int *)malloc(sizeof(int) * 10); //*q = *&p =p ,也就是操作*q就等同操作函数外的p
}
int main(int argc, char const *argv[])
{
int i;
int *p = NULL;
get_mem(&p); //函数调用结束后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;
}
4.3 链式栈
4.3.1 特性
逻辑结构：线性结构
存储结构：链式存储
顺序栈和链式栈的区别：存储结构不同，实现的方式也不同，顺序栈是用顺序表实现而链式栈用链表实现。
栈的操作：创建、入栈、出栈、判空
入栈：
出栈：
代码实现：
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{
datatype data;
struct node *next;
} node_t, *node_p;
//创建一个空栈
void createEmptyLinkStack(node_p *p) //p=&top
{
*p = NULL; //*p = top = NULL
}
//入栈, data是入栈的数据
int pushLinkStack(node_p *p, datatype data) //因为要用p接收函数外的&top来在函数内找到top, 所以参数需要为二级指针。
{
// 创建新节点
node_p pnew = (node_p)malloc(sizeof(node_t));
if (NULL == pnew)
{
perror("pnew malloc err");
return -1;
}
// 将要入栈数据存入新节点
pnew->data = data;
pnew->next = NULL;
// 将新节点连入到链表中
pnew->next = *p; //*p=top
// 移动栈针到新的栈顶节点
*p = pnew;
return 0;
}
//判断栈是否为空
int isEmptyLinkStack(node_p p)
{
return p == NULL;
}
//出栈
datatype popLinkStack(node_p *p) //p=&top
{
node_p pdel = NULL;
//1. 判空：*p == NULL;
if (isEmptyLinkStack(*p)) //*p=top
{
printf("popLinkStack err\n");
return -1;
}
//2. 让指针pdel指向栈顶节点
pdel = *p;
//3. 移动栈针到下一个节点
*p = (*p)->next; //*p=pdel->next;
//4. 定义临时变量保存要出栈数据: temp = pdel->data;
datatype temp = pdel->data;
//5. 释放要被删除节点: free(pdel);
free(pdel);
//6. 返回要出栈数据：return temp;
return temp;
}
//求栈的长度
int lengthLinkStack(node_p p) //传递一级指针，因为不需要移动栈针(也就是主函数的top)。
{
int len = 0;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
int main(int argc, char const *argv[])
{
node_p top;
createEmptyLinkStack(&top); //top=NULL
pushLinkStack(&top, 1);
pushLinkStack(&top, 2);
pushLinkStack(&top, 3);
printf("len=%d\n", lengthLinkStack(top));
while (!isEmptyLinkStack(top))
{
printf("%d\n", popLinkStack(&top)); //3 2 1
}
return 0;
}
总结：
顺序栈和链式栈的区别是什么？
- 顺序栈是顺序存储，内存连续，用顺序表实现；链表是链式存储，内存不连续，用链表实现。
- 顺序栈的长度固定，而链栈不会。
