【数据结构】C语言实现---栈
1、栈的概念与结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出：LIFO(Last in first out)的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
2、栈的实现
栈的实现方式：
（1）数组实现
（2）链表实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一点。因为数组在尾上插入数据的代价比较小。
3、数组实现栈
声明：我是在vs2022中实现的。
Stack.h头文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;//栈的容量
}ST;
void STInit(ST* pst);//栈初始化
void STDestory(ST* pst);//栈的销毁
void STPush(ST* pst,STDataType);//在栈顶插入数据
void STPop(ST* pst);//在栈顶删除数据
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//求栈中数据元素个数
STDataType STTop(ST* pst);//获取栈顶元素的值
Stack.c源文件
#include "Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//表示top指向栈顶元素的下一个位置
pst->capacity = 0;}
void STDestory(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc failed\n");
return;}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty( pst));
pst->top--;
}
testStack.c源文件
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include "Stack.h"
void test()
{
//初始化、进栈、出栈、取栈顶元素、判断栈是否为空、遍历
ST st;
STInit(&st);//初始化；
STPush(&st, 1);//插入数据
STPush(&st, 2);//
STPush(&st, 3);//
STPush(&st, 4);//
STPush(&st, 5);//
printf("栈中元素个数：%d\n", STSize(&st));
printf("栈顶元素数据为：%d\n", STTop(&st));
//判断栈是否为空
if (STEmpty(&st))
{
printf("栈为空\n");
}
else
{
printf("栈不为空\n");
}
遍历栈中元素：
printf("栈中元素为：");
while (!STEmpty(&st))
{
printf(" %d ", STTop(&st));
STPop(&st);
}
printf("\n");
STDestory(&st);
printf("栈已经销毁");
}
int main()
{
test();
return 0;}
通过在vs2022中，运行以上三个代码，则结果为：
4、单链表实现栈
单链表实现栈主体框架：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int ElemType;
typedef struct Node
{
ElemType data;//数据域
struct Node* next;//指针域}Node;
typedef struct LinkedStack
{
Node* top;//栈顶指针
int size;//链栈的长度}LinkedStack;
//初始化栈
void initStack(LinkedStack* pstack)
{
pstack->top = NULL;
pstack->size = 0;
}
//判断栈是否为空
bool isEmpty(LinkedStack stack)
{
return stack.size == 0;
}
//求栈里面的元素个数
int size(LinkedStack stack)
{
return stack.size;
}
//实现入栈
void push(LinkedStack* pstack, ElemType elem)
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL)
{
perror("内存溢出");
}
newnode->data = elem;
//使用头插法把newnode插入到链表的头部（top)
newnode->next = pstack->top;//指针域指向栈顶指针top
pstack->top = newnode;
pstack->size++;
}
//获取栈顶元素的数据域，并删除栈顶元素
ElemType pop(LinkedStack* pstack)
{
if (pstack->size == 0)
{
perror("栈是空的");
}
Node* poppedNode = pstack->top;//即将删除的链表首元结点
ElemType poppedElem = poppedNode->data;
pstack->top = pstack->top->next;
free(poppedNode);//释放申请的内存
return poppedElem;
}
//打印栈中的元素数据域（从栈顶到栈底）
void printStack(LinkedStack stack)
{
Node* temp = stack.top;
while (temp != NULL)
{
printf("%d", temp->data);
temp = temp->next;
}
printf("\n");
}
//获取栈顶元素，不删除
ElemType peek(LinkedStack stack)
{
if (isEmpty(stack))
{
perror("栈是空的");
}
return stack.top->data;
}
void test()
{
//....}
int main()
{
test();
return 0;
}
上面这个代码是单链表实现栈的框架，只需要在test()函数中，写具体的代码就可以了。
5、单链表实现栈的具体案例
将十进制转换为二进制：
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int ElemType;
typedef struct Node
{
ElemType data;//数据域
struct Node* next;//指针域}Node;
typedef struct LinkedStack
{
Node* top;//栈顶指针
int size;//链栈的长度}LinkedStack;
//初始化栈
void initStack(LinkedStack* pstack)
{
pstack->top = NULL;
pstack->size = 0;
}
//判断栈是否为空
bool isEmpty(LinkedStack stack)
{
return stack.size == 0;
}
//求栈里面的元素个数
int size(LinkedStack stack)
{
return stack.size;
}
//实现入栈
void push(LinkedStack* pstack, ElemType elem)
{
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL)
{
perror("内存溢出");
}
newnode->data = elem;
//使用头插法把newnode插入到链表的头部（top)
newnode->next = pstack->top;//指针域指向栈顶指针top
pstack->top = newnode;
pstack->size++;
}
//获取栈顶元素的数据域，并删除栈顶元素
ElemType pop(LinkedStack* pstack)
{
if (pstack->size == 0)
{
perror("栈是空的");
}
Node* poppedNode = pstack->top;//即将删除的链表首元结点
ElemType poppedElem = poppedNode->data;
pstack->top = pstack->top->next;
free(poppedNode);//释放申请的内存
return poppedElem;
}
//打印栈中的元素数据域（从栈顶到栈底）
void printStack(LinkedStack stack)
{
Node* temp = stack.top;
while (temp != NULL)
{
printf("%d", temp->data);
temp = temp->next;
}
printf("\n");
}
//获取栈顶元素，不删除
ElemType peek(LinkedStack stack)
{
if (isEmpty(stack))
{
perror("栈是空的");
}
return stack.top->data;
}
void test()
{
LinkedStack linkedstack;
//初始化栈 //判断栈是否为空 //求栈里面的元素个数 //实现入栈 //获取栈顶元素的数据域，并删除栈顶元素
//打印栈中的元素数据域（从栈顶到栈底）
initStack(&linkedstack);
int number = 0;
printf("请输入要转换为二进制的十进制数字：");
scanf("%d", &number);
//while (num != 0)
//{
// push(binaryStack, num % 2); //余数入栈
// num /= 2;
//}
printf("十进制数字%d 转化为二进制数据为：", number);
while (number != 0)
{
push(&linkedstack , number%2);
number /= 2;}
printStack(linkedstack);}
int main()
{
test();
return 0;
}
实验结果：
