链栈和顺序栈的创建,入栈,出栈,取栈顶元素,遍历,C语言,可进行输入
时间: 2023-06-16 15:08:04 浏览: 57
链栈和顺序栈是栈的两种实现方式,它们的基本操作包括创建、入栈、出栈、取栈顶元素和遍历。
1. 顺序栈
顺序栈是基于数组实现的栈,它的创建、入栈、出栈、取栈顶元素和遍历操作如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 栈的最大容量
typedef struct {
int data[MAXSIZE]; // 数据元素
int top; // 栈顶指针
} SqStack;
// 初始化栈
void InitStack(SqStack *S) {
S->top = -1;
}
// 判断栈是否为空
int IsEmpty(SqStack *S) {
return (S->top == -1);
}
// 判断栈是否已满
int IsFull(SqStack *S) {
return (S->top == MAXSIZE - 1);
}
// 入栈
int Push(SqStack *S, int x) {
if (IsFull(S)) {
return 0; // 栈已满,入栈失败
} else {
S->top++;
S->data[S->top] = x;
return 1; // 入栈成功
}
}
// 出栈
int Pop(SqStack *S) {
if (IsEmpty(S)) {
return 0; // 栈已空,出栈失败
} else {
int x = S->data[S->top];
S->top--;
return x; // 返回出栈元素
}
}
// 取栈顶元素
int GetTop(SqStack *S) {
if (IsEmpty(S)) {
return 0; // 栈已空,无栈顶元素
} else {
return S->data[S->top];
}
}
// 遍历栈
void TraverseStack(SqStack *S) {
if (IsEmpty(S)) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = S->top; i >= 0; i--) {
printf("%d ", S->data[i]);
}
printf("\n");
}
}
int main() {
SqStack S;
InitStack(&S);
int x;
printf("Enter elements to push into stack (enter 0 to stop):\n");
while (1) {
scanf("%d", &x);
if (x == 0) {
break;
}
Push(&S, x);
}
TraverseStack(&S);
printf("Pop elements from stack (enter 0 to stop):\n");
while (1) {
scanf("%d", &x);
if (x == 0) {
break;
}
if (Pop(&S)) {
printf("Pop element: %d\n", x);
} else {
printf("Stack is empty.\n");
break;
}
}
printf("Top element of stack: %d\n", GetTop(&S));
return 0;
}
```
2. 链栈
链栈是基于链表实现的栈,它的创建、入栈、出栈、取栈顶元素和遍历操作如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} LinkNode, *LinkStack;
// 初始化栈
void InitStack(LinkStack *S) {
*S = NULL;
}
// 判断栈是否为空
int IsEmpty(LinkStack S) {
return (S == NULL);
}
// 入栈
void Push(LinkStack *S, int x) {
LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
p->data = x;
p->next = *S;
*S = p;
}
// 出栈
int Pop(LinkStack *S) {
if (IsEmpty(*S)) {
return 0; // 栈已空,出栈失败
} else {
LinkNode *p = *S;
int x = p->data;
*S = p->next;
free(p);
return x; // 返回出栈元素
}
}
// 取栈顶元素
int GetTop(LinkStack S) {
if (IsEmpty(S)) {
return 0; // 栈已空,无栈顶元素
} else {
return S->data;
}
}
// 遍历栈
void TraverseStack(LinkStack S) {
if (IsEmpty(S)) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
LinkNode *p = S;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int main() {
LinkStack S;
InitStack(&S);
int x;
printf("Enter elements to push into stack (enter 0 to stop):\n");
while (1) {
scanf("%d", &x);
if (x == 0) {
break;
}
Push(&S, x);
}
TraverseStack(S);
printf("Pop elements from stack (enter 0 to stop):\n");
while (1) {
scanf("%d", &x);
if (x == 0) {
break;
}
if (Pop(&S)) {
printf("Pop element: %d\n", x);
} else {
printf("Stack is empty.\n");
break;
}
}
printf("Top element of stack: %d\n", GetTop(S));
return 0;
}
```