用C语言描述栈的每种操作在顺序栈或链栈上的实现并写出完整代码
时间: 2024-11-09 13:17:24 浏览: 23
C语言 栈的实现,包含顺序栈和链栈,亲测可用
5星 · 资源好评率100%
栈是一种线性的数据结构,常用的操作包括入栈(压栈)、出栈(弹栈)和查看栈顶元素(顶元素)。这里分别解释顺序栈(基于数组)和链栈(基于链表)上这些操作的实现。
**顺序栈(数组实现):**
顺序栈通常通过数组实现,数组的最后一个位置作为栈顶。入栈、出栈和查看栈顶的操作如下:
```c
typedef struct {
int capacity;
int top;
int* stack;
} Stack;
// 初始化一个空栈
void init_stack(Stack* s, int size) {
s->capacity = size;
s->top = -1;
s->stack = (int*)malloc(s->capacity * sizeof(int));
}
// 入栈(压栈)
void push(Stack* s, int value) {
if (s->top == s->capacity - 1) {
printf("Stack overflow.\n");
return;
}
s->top++;
s->stack[s->top] = value;
}
// 出栈(弹栈)
int pop(Stack* s) {
if (s->top == -1) {
printf("Stack underflow.\n");
return -1; // 返回错误值
}
int top_value = s->stack[s->top];
s->top--;
return top_value;
}
// 查看栈顶元素
int peek(Stack* s) {
if (s->top == -1) {
printf("Stack is empty.\n");
return -1; // 返回错误值
}
return s->stack[s->top];
}
```
**链栈(链表实现):**
链栈使用链表节点来存储元素,每个节点包含指向下一个节点的指针和数据。入栈、出栈和查看栈顶的操作如下:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* top;
} Stack;
// 初始化一个空链栈
void init_list_stack(Stack* s) {
s->top = NULL;
}
// 入栈(压栈)
void push(Stack* s, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
}
// 出栈(弹栈)
int pop(Stack* s) {
if (s->top == NULL) {
printf("Stack underflow.\n");
return -1;
}
Node* temp = s->top;
int top_value = temp->data;
s->top = temp->next;
free(temp);
return top_value;
}
// 查看栈顶元素
int peek(Stack* s) {
if (s->top == NULL) {
printf("Stack is empty.\n");
return -1;
}
return s->top->data;
}
```
阅读全文