首页 > 编程札记 > 编程

数据结构系列3——数组栈，链式栈和双向栈

阅读：评论：0

一、数组栈

1、数组栈的实现

2、数组栈的简单操作

1、入栈操作

2、出栈操作

3、判空操作

4、获取栈顶元素

3、运行测试

4、运行结果

二、链式栈

1、链式栈的创建和封装

2、链式栈的简单操作

1、入栈操作

2、出栈操作

3、获取栈顶节点里面的数据

4、链式栈判空

3、运行测试

4、运行结果

三、双向栈

1、双向栈的实现和创建

2、双向栈的简单操作

1、入栈操作

2、出栈操作

3、获取栈顶元素

4、判空处理

3、运行测试

4、测试结果

引入：栈是一种简单的数据结构，它的特点就是数据先进后出。当我们在电脑上为要存储的数据申请了一段内存，管理数据的时候采用先进后出的方式存储和访问数据的结构都可以称之为栈结构

一、数组栈

1、数组栈的实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define MAX 10        //数组栈的高度
typedef struct Stack
{int* number;    //数组充当栈，用一个指针int top;        //栈顶标记
}STACK,*STACKLINK;STACKLINK creatstack()            //创建数组栈
{STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));assert(pstack);//以下描述数组栈的最初状态pstack->number = (int*)malloc(sizeof(int) * MAX);pstack->top = -1;        //这里栈顶标记为-1方便操作，当然从0开始也可以return pstack;
}

2、数组栈的简单操作

1、入栈操作

void push(STACKLINK pstack, int data)
{if (pstack->top + 1 == MAX)        //入栈的时候记得判断栈是否已经满了{printf("栈已满，无法入栈！n");return;}//先将top标记做++运算，因为我们创建数组栈的时候将栈顶标记设置为了-1pstack->number[++pstack->top] = data;
}

2、出栈操作

void pop(STACKLINK pstack)
{if (pstack->top == -1)        //出栈判断栈是否为空{printf("栈为空，无法出栈！n");return;}pstack->top--;        //出栈只需要将栈顶标记做--运算就可以了
}

3、判空操作

//栈为空返回1，否则返回0
int empty(STACKLINK pstack)
{if (pstack->top == -1){return 1;}return 0;
}

4、获取栈顶元素

int gettopnumber(STACKLINK pstack)
{if (empty(pstack))       //取栈顶元素也要判空{printf("栈为空，无法获取栈顶数据！n");return 0;}return pstack->number[pstack->top];        //直接返回栈顶标记所在的数据就好了
}

3、运行测试


int main()
{int a = 0;STACKLINK pstack = creatstack();        //创建数组栈for (int i = 0; i < 10; i++)        //测试入栈{push(pstack, i);}while (!empty(pstack))        //打印栈顶数据{printf("%dt",gettopnumber(pstack));        //打印栈顶数据pop(pstack);                            //每次出栈一个元素，循环打印栈顶数据}printf("n");return 0;
}

4、运行结果

这里可以看到打印的数据的规律，我们是先从0开始入栈，根据先进后出的规律，在打印栈顶数据的时候确实是先打印的9，这印证了栈结构管理数据的特点

二、链式栈

1、链式栈的创建和封装

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//数据结构体
typedef struct Node
{int data;struct Node* next;
}NODE, * NODELINK;NODELINK linkcreatnode(int data)
{NODELINK newnode = (NODELINK)malloc(sizeof(NODE));assert(newnode);newnode->data = data;newnode->next = NULL;return newnode;
}//封装栈结构体
typedef struct Stack
{NODELINK listnode;    //这个就相当于栈顶标记int size;        //万金油参数，保存当前元素个数
}STACK, * STACKLINK;STACKLINK linkcreatstack()
{STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));assert(pstack);pstack->listnode = NULL;pstack->size = 0;return pstack;}

2、链式栈的简单操作

1、入栈操作

void linkpush(STACKLINK pstack, int data)
{NODELINK newnode = linkcreatnode(data);       //先将数据通过我们写的函数变成一个节点newnode->next = pstack->listnode;        //插入操作pstack->listnode = newnode;        //将栈顶标记移到新节点上pstack->size++;        //记得将万金油参数做++运算}

2、出栈操作


void linkpop(STACKLINK pstack)
{//入栈时不一定判满，但是出栈时一定要判空/*if (pstack->listnode == NULL)      //第一种判空（通过判断栈顶节点是否为空判空） {printf("栈为空！n");return;}*/if (pstack->size == 0)	{        //第二种判空（通过万金油参数判空）printf("栈为空，无法出栈！n");}//出栈操作NODELINK nextnode = pstack->listnode->next;free(pstack->listnode);        //记得将内存释放掉pstack->listnode = nextnode;pstack->size--;        //别忘了我们的万金油参数做--运算}

3、获取栈顶节点里面的数据

int linkgettopnumber(STACKLINK pstack)
{//像这种一步一步获取数据的操作，我们称之为剥洋葱return pstack->listnode->data;
}

4、链式栈判空

//判空
int linkempty(STACKLINK pstack)
{//判空有多种写法/*if (pstack->listnode == NULL)  //判空的第一种写法      {return 1;}return 0;*/return pstack->size == 0;        //判空的第二种写法
}

3、运行测试

int main()
{STACKLINK pstack = linkcreatstack();//创建链式栈for (int i = 0; i < 11; i++)        //测试入栈操作{linkpush(pstack, i);}while (!linkempty(pstack))    //打印数据{printf("%dt", pstack->listnode->data);linkpop(pstack);        //每次打印完栈顶节点里面的数据后记得要出栈才能继续打印}return 0;
}

4、运行结果

我们可以看到效果和上面的数组栈效果是一样的，要根据实际选择数组栈和链式栈

三、双向栈

1、双向栈的实现和创建

可能这个东西很多小伙伴都没听说过哈，我来给大家解释一下双向栈是个什么东西，说白了双向栈就是两个栈公用一个栈顶，左右两边都可以出栈和入栈，“两个栈”都有栈顶标记，当两个栈的栈顶标记只相差一的时候，就代表这个双向栈满了，无法入栈了。当两个栈顶标记为初始值的时候，就代表双向栈为空了，无法出栈和获取栈顶元素了

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define MAX 10        //双向栈的长度enum pushway { left, right };    //采用枚举类型typedef struct Stack
{int* number;int lefttop;        //左边的栈顶标记int righttop;        //右边栈的栈顶标记
}STACK, * STACKLINK;STACKLINK creatstack2()        //创建双向栈
{STACKLINK pstack = (STACKLINK)malloc(sizeof(STACK));assert(pstack);pstack->number = (int*)malloc(sizeof(int) * MAX);pstack->lefttop = -1;        //左边的栈顶标记pstack->righttop = MAX;        //右边的栈顶标记return pstack;
}

2、双向栈的简单操作

1、入栈操作

//入栈操作
void doublepush(STACKLINK pstack, int data, enum pushway way)
{if (pstack->righttop - pstack->lefttop == 1)//当左边栈顶和右边栈顶相差一的时候，栈满{printf("栈已满，无法插入！n");return;}switch (way)        //对传入的形参进行判断，执行不同的语句{case left:pstack->number[++pstack->lefttop] = data;break;case right:pstack->number[--pstack->righttop] = data;break;}
}

2、出栈操作

//出栈操作
void doublepop(STACKLINK pstack, enum pushway way)
{switch (way){case left:if (pstack->lefttop == -1){printf("左栈为空，无法出栈！n");return;}pstack->lefttop--;break;case right:if (pstack->righttop == MAX){printf("右栈为空，无法出栈！n");return;}pstack->righttop++;break;}
}

3、获取栈顶元素

//获取栈顶元素
int doubletop(STACKLINK pstack, enum pushway way)
{switch (way){case left:return pstack->number[pstack->lefttop];break;case right:return pstack->number[pstack->righttop];break;}
}

4、判空处理

//判空
int doubleempty(STACKLINK pstack)
{return pstack->lefttop == -1 && pstack->righttop == MAX;
}

3、运行测试

//增加判断奇偶性的函数，用于主函数里面数据入栈的时候，区分数据从哪边入栈
//判断奇偶性（奇数返回0，偶数返回1）
int isou(int number)
{if (number % 2 == 0)return 1;return 0;
}int main()
{//创建双向栈STACKLINK pstack = creatstack2();//将偶数数据从右方压入双向栈，奇数从左方压入双向栈for (int i = 0; i < 9; i++){if (isou(i)){doublepush(pstack, i, right);}else{doublepush(pstack, i, left);}}//从左侧输出双向栈while (!doubleempty(pstack) && pstack->lefttop != -1){printf("%dt", doubletop(pstack, left));doublepop(pstack, left);}printf("n");//从右侧输出双向栈while (!doubleempty(pstack) && pstack->righttop != MAX){printf("%dt", doubletop(pstack, right));doublepop(pstack, right);}return 0;
}