数据结构顺序栈和链栈
时间: 2023-12-04 10:37:12 浏览: 95
顺序栈和链栈都是栈的两种实现方式,它们的主要区别在于底层数据结构不同。
顺序栈使用数组作为底层数据结构,实现简单,但容量固定,需要预先分配一定的空间。当栈满时,需要进行扩容操作,这会导致时间复杂度为 O(n) 的开销。
链栈使用链表作为底层数据结构,可以动态地分配内存空间,不会浪费空间。但是相比于顺序栈,链栈需要额外的指针域来存储链表节点的地址,因此实现稍微复杂一些。
相关问题
数据结构,用c实现,根据输入的栈中元素个数n和各元素值建立一个顺序栈和链栈,并输出栈中各元素值。将数据元素e入栈,并输出入栈后的顺序栈和链栈中各元素值。将顺序栈和链栈中的栈顶元素出栈,并输出出栈元素的值和出栈后顺序栈和链栈中各元素值。
以下是用C语言实现栈的建立、遍历、进栈和出栈的代码,包括顺序栈和链栈:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 定义顺序栈的最大长度
// 定义顺序栈结构体
typedef struct {
int data[MAXSIZE]; // 存储栈中元素的数组
int top; // 栈顶指针
} SqStack;
// 定义链栈结构体
typedef struct LNode {
int data; // 存储栈中元素的值
struct LNode *next; // 指向下一个节点的指针
} *LinkStack;
// 初始化顺序栈
void InitStack(SqStack *S) {
S->top = -1; // 初始化栈顶指针为-1
}
// 判断顺序栈是否为空
int StackEmpty(SqStack S) {
if (S.top == -1) {
return 1; // 栈为空
} else {
return 0; // 栈不为空
}
}
// 进栈操作
int StackPush(SqStack *S, int x) {
if (S->top == MAXSIZE - 1) {
return 0; // 栈满,无法进栈
} else {
S->top++; // 栈顶指针加1
S->data[S->top] = x; // 将元素x入栈
return 1; // 进栈成功
}
}
// 出栈操作
int StackPop(SqStack *S, int *x) {
if (S->top == -1) {
return 0; // 栈空,无法出栈
} else {
*x = S->data[S->top]; // 将栈顶元素赋值给x
S->top--; // 栈顶指针减1
return 1; // 出栈成功
}
}
// 初始化链栈
void InitLinkStack(LinkStack *S) {
*S = NULL; // 初始化链栈为空
}
// 判断链栈是否为空
int LinkStackEmpty(LinkStack S) {
if (S == NULL) {
return 1; // 栈为空
} else {
return 0; // 栈不为空
}
}
// 进栈操作
int LinkStackPush(LinkStack *S, int x) {
LinkStack p = (LinkStack)malloc(sizeof(struct LNode)); // 创建新节点
p->data = x; // 将元素x入栈
p->next = *S; // 将新节点插入到链栈的栈顶
*S = p; // 修改链栈的栈顶指针
return 1; // 进栈成功
}
// 出栈操作
int LinkStackPop(LinkStack *S, int *x) {
if (*S == NULL) {
return 0; // 栈空,无法出栈
} else {
LinkStack p = *S; // 指向链栈的栈顶节点
*x = p->data; // 将栈顶元素赋值给x
*S = p->next; // 修改链栈的栈顶指针
free(p); // 释放原栈顶节点的空间
return 1; // 出栈成功
}
}
int main() {
int n, x, i;
SqStack S1;
LinkStack S2;
InitStack(&S1); // 初始化顺序栈
InitLinkStack(&S2); // 初始化链栈
// 输入要建立栈的元素个数n
printf("请输入要建立栈的元素个数:\n");
scanf("%d", &n);
// 建立顺序栈
printf("请输入要建立的顺序栈的元素值:\n");
for (i = 0; i < n; i++) {
scanf("%d", &x);
StackPush(&S1, x); // 进栈操作
}
// 输出顺序栈中各元素值
printf("顺序栈中各元素值为:\n");
while (!StackEmpty(S1)) {
StackPop(&S1, &x); // 出栈操作
printf("%d ", x);
}
printf("\n");
// 建立链栈
printf("请输入要建立的链栈的元素值:\n");
for (i = 0; i < n; i++) {
scanf("%d", &x);
LinkStackPush(&S2, x); // 进栈操作
}
// 输出链栈中各元素值
printf("链栈中各元素值为:\n");
while (!LinkStackEmpty(S2)) {
LinkStackPop(&S2, &x); // 出栈操作
printf("%d ", x);
}
printf("\n");
// 将元素e入栈,并输出入栈后的顺序栈和链栈中各元素值
printf("请输入要入栈的元素值:\n");
scanf("%d", &x);
StackPush(&S1, x); // 进栈操作
LinkStackPush(&S2, x); // 进栈操作
printf("入栈后顺序栈中各元素值为:\n");
for (i = S1.top; i >= 0; i--) {
printf("%d ", S1.data[i]);
}
printf("\n");
printf("入栈后链栈中各元素值为:\n");
LinkStack p = S2;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
// 将顺序栈和链栈中的栈顶元素出栈,并输出出栈元素的值和出栈后顺序栈和链栈中各元素值
StackPop(&S1, &x); // 出栈操作
printf("顺序栈出栈元素的值为:%d\n", x);
printf("出栈后顺序栈中各元素值为:\n");
for (i = S1.top; i >= 0; i--) {
printf("%d ", S1.data[i]);
}
printf("\n");
LinkStackPop(&S2, &x); // 出栈操作
printf("链栈出栈元素的值为:%d\n", x);
printf("出栈后链栈中各元素值为:\n");
p = S2;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return 0;
}
```
数据结构 定义栈的存储结构(顺序栈或者链栈均可)算法代码 c语言
栈是一种线性数据结构,它遵循“先进后出”(Last In First Out, LIFO)的原则,常用于函数调用、表达式求值等场景。这里有两种常见的栈实现方式,分别是顺序栈和链栈。
**顺序栈(基于数组)**:
在C语言中,可以使用数组来实现顺序栈。数组栈的特点是空间连续,插入和删除操作的时间复杂度为O(1),但如果接近栈顶,需要移动大量元素才能继续添加或移除元素。
```c
typedef struct {
int* stack; // 存储数据的数组
int top; // 栈顶指针
int size; // 栈的最大容量
} Stack;
// 初始化栈
void init(Stack* s, int capacity) {
s->stack = (int*)malloc(capacity * sizeof(int));
s->top = -1;
s->size = capacity;
}
// 入栈
void push(Stack* s, int value) {
if (s- 1) {
s->stack[++s->top] = value;
} else {
printf("Stack overflow\n");
}
}
// 出栈
int pop(Stack* s) {
if (s->top >= 0) {
return s->stack[s->top--];
} else {
printf("Stack underflow\n");
return -1; // 返回特殊值表示空栈
}
}
```
**链栈(基于链表)**:
链栈则利用链表节点,每个节点包含数据和指向下一个节点的指针,操作更灵活,不需要预先分配固定大小的空间,但是插入和删除操作的时间复杂度通常为O(1)。
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* top;
Node* bottom;
} LinkStack;
// 初始化链栈
void link_init(LinkStack* s) {
s->top = s->bottom = NULL;
}
// 入栈
void link_push(LinkStack* s, int value) {
Node* newNode = malloc(sizeof(Node));
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
if (!s->bottom)
s->bottom = newNode;
}
// 出栈
int link_pop(LinkStack* s) {
if (s->top) {
int data = s->top->data;
Node* temp = s->top;
s->top = s->top->next;
free(temp);
if (!s->top)
s->bottom = NULL;
return data;
} else {
printf("Stack empty\n");
return -1;
}
}
```
阅读全文