八、数据结构——链表中链式栈详解(入栈、出栈、清空栈、遍历弹出元素、打印栈等基本操作和在数据结构中的实现)
线性栈是一种遵循后进先出(LIFO)原则的数据结构。它类似于我们日常生活中的栈,如一摞书堆叠起来,只能从顶部插入和移除。线性栈只允许在栈顶进行插入和删除操作,其他位置的元素无法直接访问。
·
深入理解线性栈:基本操作和数据结构中的实现
在计算机科学中,数据结构是处理和组织数据的基本工具。其中,线性栈是一种常见且重要的数据结构。本文将深入探讨线性栈的基本操作,包括入栈、出栈和获取栈顶元素,同时介绍线性栈在数据结构中的实现方式,并提供相应的代码示例。
目录
一、什么是线性栈?
线性栈是一种遵循后进先出(LIFO)原则的数据结构。它类似于我们日常生活中的栈,如一摞书堆叠起来,只能从顶部插入和移除。线性栈只允许在栈顶进行插入和删除操作,其他位置的元素无法直接访问。
二、线性栈基本操作:
入栈(Push):将一个元素添加到栈顶。插入后,新元素成为栈顶,原有的元素依次下移。
出栈(Pop):从栈顶移除一个元素,并返回该元素。出栈后,栈顶指针向下移动,指向新的栈顶元素。
三、线性栈的实现:
线性栈可以通过数组或链表实现。这里我们将介绍基于数组的实现方式。
定义结构体
//定义结构体
typedef struct Node {
typData *data; //定义栈的数组
int top; //定义栈顶指针
int capacity; //定义栈的容量
}ListStack, *PListStack;
初始化栈
//初始化栈
void stack_init(PListStack *stack, int capacity){
*stack = (PListStack)malloc(sizeof(ListStack));//分配栈结构体内存
(*stack)->data = (typData *)malloc(capacity * sizeof(typData));//分配栈数组内存
(*stack)->top = -1;//初始化栈顶指针为-1
(*stack)->capacity = capacity;//设置栈容量
}
判空
//判空
int isEmpty(PListStack stack){
return (stack->top == -1);
}
判满
//判满
int isFull(PListStack stack){
return (stack->top == stack->capacity - 1);
}
入栈
//入栈
void push(PListStack stack, typData item){
if(isFull(stack)){
printf("Stack is full, cannot push element.(栈已满,无法继续压入元素!)\n");
return ;
}
stack->top++;//栈指针自增
stack->data[stack->top] = item;//将元素压入栈顶的位置
}
出栈
//出栈
typData pop(PListStack stack){
if(isEmpty(stack)){
printf("Stack is empty, cannot pop element.(栈是空的,无法弹出元素!)\n");
return -1; // 返回一个默认值,表示栈为空
}
typData item = stack->data[stack->top];//取出栈顶的元素
stack->top--;
return item;//返回出栈的元素
}
获取栈大小
//获取栈大小
int get_stacksize(PListStack stack){
return (stack->top + 1);
}
遍历已出栈元素
//遍历已出栈元素
void traverse_pop(PListStack stack){
if (stack->top == -1) {
printf("No popped elements.(没有弹出元素)\n");
return;
}
printf("Popped elements(弹出的元素):");
for(int i = stack->capacity - 1; i > stack->top; i--){
printf("%d ",stack->data[i]);
}
puts("");
}
打印栈内元素
//打印栈内元素
void show(PListStack stack){
printf("Stack elements(栈元素):\n");
for(int i = stack->top; i >= 0; i--){
printf("%-8d\n",stack->data[i]);
}
}
清空栈
//清空栈
void clear_stack(PListStack stack){
stack->top = -1;
}
四、结论:
线性栈是一种基本的数据结构,它遵循后进先出的原则。本文详细介绍了线性栈的基本操作,包括入栈、出栈和获取栈顶元素,并提供了基于数组的实现方式的代码示例。线性栈在许多领域都有广泛的应用,例如编译器设计、表达式求值、回文判断等。通过深入理解线性栈,我们可以更好地应用它解决实际问题。
五、完整代码
同样分三个文件来执行:①接口文件liststack.h ②接口实现文件liststack.c ③函数调用文件liststack_main.c
①接口文件liststack.h
#ifndef _LISTSTACK_H
#define _LISTSTACK_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义数据类型
typedef int typData;
//定义结构体
typedef struct Node {
typData *data; //定义栈的数组
int top; //定义栈顶指针
int capacity; //定义栈的容量
}ListStack, *PListStack;
//初始化栈
void stack_init(PListStack *stack, int capacity);
//判空
int isEmpty(PListStack stack);
//判满
int isFull(PListStack stack);
//入栈
void push(PListStack stack, typData item);
//出栈
typData pop(PListStack stack);
//获取栈大小
int get_stacksize(PListStack stack);
//遍历已出栈元素
void traverse_pop(PListStack stack);
//清空栈
void clear_stack(PListStack stack);
//打印栈内元素
void show(PListStack stack);
#endif
②接口实现文件liststack.c
#include "liststack.h"
//初始化栈
void stack_init(PListStack *stack, int capacity){
*stack = (PListStack)malloc(sizeof(ListStack));//分配栈结构体内存
(*stack)->data = (typData *)malloc(capacity * sizeof(typData));//分配栈数组内存
(*stack)->top = -1;//初始化栈顶指针为-1
(*stack)->capacity = capacity;//设置栈容量
}
//判空
int isEmpty(PListStack stack){
return (stack->top == -1);
}
//判满
int isFull(PListStack stack){
return (stack->top == stack->capacity - 1);
}
//入栈
void push(PListStack stack, typData item){
if(isFull(stack)){
printf("Stack is full, cannot push element.(栈已满,无法继续压入元素!)\n");
return ;
}
stack->top++;//栈指针自增
stack->data[stack->top] = item;//将元素压入栈顶的位置
}
//出栈
typData pop(PListStack stack){
if(isEmpty(stack)){
printf("Stack is empty, cannot pop element.(栈是空的,无法弹出元素!)\n");
return -1; // 返回一个默认值,表示栈为空
}
typData item = stack->data[stack->top];//取出栈顶的元素
stack->top--;
return item;//返回出栈的元素
}
//获取栈大小
int get_stacksize(PListStack stack){
return (stack->top + 1);
}
//遍历已出栈元素
void traverse_pop(PListStack stack){
if (stack->top == -1) {
printf("No popped elements.(没有弹出元素)\n");
return;
}
printf("Popped elements(弹出的元素):");
for(int i = stack->capacity - 1; i > stack->top; i--){
printf("%d ",stack->data[i]);
}
puts("");
}
//清空栈
void clear_stack(PListStack stack){
stack->top = -1;
}
//打印栈内元素
void show(PListStack stack){
printf("Stack elements(栈元素):\n");
for(int i = stack->top; i >= 0; i--){
printf("%-8d\n",stack->data[i]);
}
}
③函数调用文件liststack_main.c
#include "liststack.h"
#include "liststack.c"
int main(int argc, char *argv[]) {
PListStack stack;
int size; // 栈的大小
printf("请输入栈的大小:");
scanf("%d", &size);
stack_init(&stack, size);
typData popped_data;
int choice, value;
while (1) {
printf("\n***************************链表操作菜单****************************\n");
printf("1. 入栈 2. 出栈 3. 栈长度 4. 遍历已出栈元素\n");
printf("5. 清空栈 6. 退出程序\n");
printf("*********************************************************************\n");
printf("请输入操作编号:");
scanf("%d", &choice);
switch (choice) {
case 1:
while(1){
printf("请输入要入栈的元素值(按q结束元素输入)):");
char input[10];
scanf("%s", input);
if (strcmp(input, "q") == 0) {
break; // 退出循环
}
value = atoi(input); // 将字符串转换为整数
push(stack, value);
show(stack);
}
break;
case 2:
printf("出栈操作\n");
popped_data = pop(stack);
if (popped_data != -1) {
printf("出栈元素:%d\n", popped_data);
show(stack);
}
break;
case 3:
printf("栈长度:%d\n", get_stacksize(stack));
break;
case 4:
printf("遍历已出栈元素\n");
traverse_pop(stack);
break;
case 5:
printf("清空栈\n");
clear_stack(stack);
printf("栈已被清空");
show(stack);
break;
case 6:
printf("退出程序\n");
exit(0);
default:
printf("无效的操作编号\n");
}
}
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)