网站开发建设企业_画册设计是什么_seo推广费用_静态网页制作

栈的基本概念

• 栈是一种 后进先出（LIFO, Last In First Out） 的数据结构。
• 栈的操作集中在栈顶（top）：
  • Push（压栈）：向栈中添加元素，放置在栈顶。
  • Pop（出栈）：移除并返回栈顶元素。
  • ReadTop/Peek：查看栈顶元素但不移除。
  • IsEmpty：检查栈是否为空。
  • IsFull：检查栈是否已满。

在实现栈时，可以通过 数组 或 链表 来模拟栈的结构。这里我们通过 数组实现栈。

栈的实现结构

首先，需要定义一个栈的结构体：

typedef struct {int data[MAX]; // 使用数组存储栈的元素int top;       // 栈顶指针，指向栈顶的元素索引
} Stack;

• data[MAX]：数组用来存储栈中的元素，MAX 是栈的容量。
• top：记录当前栈顶元素的位置。如果栈为空，top 的值为 -1。

栈操作的详细实现

1. 初始化栈

初始化栈时，将栈顶指针设置为 -1，表示栈为空。

void initStack(Stack *s) {s->top = -1; // 初始化栈顶指针
}

解释：

• s->top = -1;：栈为空时，top 被设置为 -1，这是栈的初始状态。

2. Push（压栈）

功能：

• 将元素压入栈顶。
• 如果栈未满（top < MAX - 1），将元素插入到栈顶，并将 top 向上移动一位。
• 如果栈已满（top == MAX - 1），输出错误信息，不能再压入新元素。

void push(Stack *s, int element) {if (s->top == MAX - 1) { // 检查栈是否已满printf("Stack is full. Cannot push element %d.\n", element);} else {s->top++;                // 栈顶指针上移s->data[s->top] = element; // 将元素放到栈顶printf("Element %d pushed to stack.\n", element);}
}

工作原理：

1. 首先检查栈是否已满：s->top == MAX - 1。
2. 如果栈未满：
   • 将 s->top 的值增加 1，表示栈顶上移一位。
   • 将新元素赋值给 data[s->top]，即放入栈顶。
3. 如果栈已满，输出错误信息。

示例：

Stack s;
initStack(&s);push(&s, 10); // 压入元素 10
push(&s, 20); // 压入元素 20
push(&s, 30); // 压入元素 30
push(&s, 40); // 压入元素 40
push(&s, 50); // 压入元素 50
push(&s, 60); // 栈满，不能压入

输出：

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Element 40 pushed to stack.
Element 50 pushed to stack.
Stack is full. Cannot push element 60.

3. Pop（出栈）

功能：

• 从栈顶移除元素并返回该元素。
• 如果栈为空（top == -1），输出错误信息，不能执行出栈操作。

int pop(Stack *s) {if (s->top == -1) { // 检查栈是否为空printf("Stack is empty. Cannot pop element.\n");return -1; // 返回 -1 表示失败} else {int poppedElement = s->data[s->top]; // 获取栈顶元素s->top--; // 栈顶指针下移printf("Element %d popped from stack.\n", poppedElement);return poppedElement;}
}

工作原理：

1. 首先检查栈是否为空：s->top == -1。
2. 如果栈非空：
   • 获取栈顶元素：data[s->top]。
   • 将 s->top 减 1，表示栈顶指针下移，移除栈顶元素。
3. 如果栈为空，输出错误信息。

示例：

Stack s;
initStack(&s);push(&s, 10);
push(&s, 20);
push(&s, 30);pop(&s); // 移除 30
pop(&s); // 移除 20
pop(&s); // 移除 10
pop(&s); // 栈为空，不能移除

输出：

Element 30 popped from stack.
Element 20 popped from stack.
Element 10 popped from stack.
Stack is empty. Cannot pop element.

4. ReadTop（查看栈顶元素）

功能：

• 返回栈顶元素但不移除它。
• 如果栈为空，输出错误信息并返回 -1。

int readTop(Stack *s) {if (s->top == -1) { // 检查栈是否为空printf("Stack is empty. No top element.\n");return -1;} else {printf("Top element is %d.\n", s->data[s->top]);return s->data[s->top];}
}

工作原理：

1. 检查栈是否为空：s->top == -1。
2. 如果栈非空，直接返回栈顶元素 data[s->top]。

示例：

Stack s;
initStack(&s);push(&s, 10);
push(&s, 20);readTop(&s); // 查看栈顶元素 20

输出：

Element 10 pushed to stack.
Element 20 pushed to stack.
Top element is 20.

5. IsEmpty（栈是否为空）

功能：

• 检查栈是否为空。如果栈为空，返回 1；否则返回 0。

int isEmpty(Stack *s) {return s->top == -1;
}

示例：

Stack s;
initStack(&s);printf("Is stack empty? %d\n", isEmpty(&s)); // 输出 1 (True)
push(&s, 10);
printf("Is stack empty? %d\n", isEmpty(&s)); // 输出 0 (False)

输出：

Is stack empty? 1
Element 10 pushed to stack.
Is stack empty? 0

6. IsFull（栈是否已满）

功能：

• 检查栈是否已满。如果栈已满，返回 1；否则返回 0。

int isFull(Stack *s) {return s->top == MAX - 1;
}

示例：

Stack s;
initStack(&s);push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
push(&s, 50);printf("Is stack full? %d\n", isFull(&s)); // 输出 1 (True)

输出：

Element 10 pushed to stack.
Element 20 pushed to stack.
Element 30 pushed to stack.
Element 40 pushed to stack.
Element 50 pushed to stack.
Is stack full? 1

---

完整代码：实现所有栈操作

#include <stdio.h>
#define MAX 5typedef struct {int data[MAX];int top;
} Stack;void initStack(Stack *s) {s->top = -1;
}void push(Stack *s, int element) {if (s->top == MAX - 1) {printf("Stack is full. Cannot push element %d.\n", element);} else {s->top++;s->data[s->top] = element;printf("Element %d pushed to stack.\n", element);}
}int pop(Stack *s) {if (s->top == -1) {printf("Stack is empty. Cannot pop element.\n");return -1;} else {int poppedElement = s->data[s->top];s->top--;printf("Element %d popped from stack.\n", poppedElement);return poppedElement;}
}int readTop(Stack *s) {if (s->top == -1) {printf("Stack is empty. No top element.\n");return -1;} else {printf("Top element is %d.\n", s->data[s->top]);return s->data[s->top];}
}int isEmpty(Stack *s) {return s->top == -1;
}int isFull(Stack *s) {return s->top == MAX - 1;
}int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);readTop(&s);pop(&s);printf("Is stack empty? %d\n", isEmpty(&s));push(&s, 30);push(&s, 40);push(&s, 50);push(&s, 60);printf("Is stack full? %d\n", isFull(&s));return 0;
}

运行输出

Element 10 pushed to stack.
Element 20 pushed to stack.
Top element is 20.
Element 20 popped from stack.
Is stack empty? 0
Element 30 pushed to stack.
Element 40 pushed to stack.
Element 50 pushed to stack.
Stack is full. Cannot push element 60.
Is stack full? 1