【c语言】栈（通过数组和链表实现）

目录

栈的简介

通过数组实现栈：

通过链表实现栈：

注意事项：

---

栈的简介

栈是一种数据结构，它是一个具有特殊性质的线性表。栈中的元素遵循后进先出（LIFO，Last In First Out）的原则，也就是最后入栈的元素最先被弹出。

在C语言中，栈通常是由系统分配的一段连续内存空间，它用来存储局部变量、函数参数以及函数调用的返回地址等信息。每当一个函数被调用时，系统都会为其分配一个栈帧，用来存储这些信息，然后将其压入栈中。当函数执行完毕后，系统会将栈帧弹出，恢复先前的执行状态。

在C语言中，栈的操作主要包括压栈（push）、弹栈（pop）以及栈顶元素访问等。这些操作可以通过数组实现，也可以通过使用指针来操作栈。

通过数组实现栈：

#include <stdio.h>
#include <stdlib.h>
 
int MAXSIZE = 8;
int *stack;
int top = -1; 
 
int isempty()
{
 
   if(top == -1)
      return 1;
   else
      return 0;
}
   
int isfull()
{
 
   if(top == MAXSIZE - 1)
      return 1;
   else
      return 0;
}
 
int peek()
{
   return stack[top];
}
 
int pop()
{
   int data;
 
   if(!isempty())
   {
      data = stack[top];
      top = top - 1;
      printf("Popping data: %d\n", data);
      return data;
   } 
   else 
   {
      printf("Could not retrieve data, Stack is empty.\n");
      return -1;
   }
}
 
void push(int data)
{
   if(isfull())
   {
      // Increase size of stack by 2x
      MAXSIZE *= 2;
      stack = (int *) realloc(stack, MAXSIZE * sizeof(int));
      printf("Stack size doubled to %d\n", MAXSIZE);
   } 
 
   top = top + 1;
   stack[top] = data;
   printf("Pushing data: %d\n", data);
}
 
int main() {
   // Allocate memory for stack
   stack = (int *) malloc(MAXSIZE * sizeof(int));
   
   // Push items on to the stack 
   push(1);
   push(2);
   push(3);
   push(4);
   push(5);
   push(6);
   push(7);
   push(8);
   push(9);
   push(10);
 
   printf("Stack full: %s\n", isfull()?"true":"false");
   printf("Stack empty: %s\n", isempty()?"true":"false");
 
   printf("Element at top of the stack: %d\n" ,peek());
 
   // Print stack data 
   while(!isempty()) {
      int data = pop();
      //printf("%d\n",data);
   }
 
   printf("Stack full: %s\n", isfull()?"true":"false");
   printf("Stack empty: %s\n", isempty()?"true":"false");
 
   // Free memory allocated for stack
   free(stack);
   
   return 0;
}

这段代码是一个用C语言实现的栈的数据结构示例。其中包含了栈的基本操作，如初始化、判断栈是否为空、判断栈是否已满、获取栈顶元素、弹出栈顶元素以及压入新元素等。

isempty()函数：

这段代码是定义了一个名为isempty的函数，用来判断栈是否为空。函数中判断栈顶指针top的值是否为-1，如果是，则栈为空，返回1；否则，栈不为空，返回0。

isfull()函数：

这段代码是实现判断栈是否已满的函数，函数名为isfull()。在这个函数中，首先通过判断栈顶指针top是否等于栈的最大容量MAXSIZE-1，来确定栈是否已满。如果是，则返回1，表示栈已满；否则，返回0，表示栈未满。这个函数的返回值可以用于在主函数中判断是否可以继续往栈中添加数据。

peek()函数：

这段代码定义了一个函数peek()，用于返回栈顶元素的值，但是并不弹出栈顶元素。具体实现是直接返回存储在数组stack中的top位置的元素。需要注意的是，在调用peek()函数之前需要先确保栈不为空，否则将访问无效内存。

pop()函数：

这段代码实现了从栈中弹出（或删除）一个元素，并返回该元素的值。首先它定义了一个整数变量data，用于存储要删除的元素的值。然后它检查栈是否为空，如果不是，则将栈顶元素的值存储在data变量中，并将栈顶指针top向下移动一位以删除该元素。最后，它打印出被删除元素的值，然后将该值返回。如果栈为空，则打印出一条消息说明无法检索数据，然后返回-1表示出现了错误。

push(int data)函数：

这段代码实现了栈数据结构的 push 操作，即向栈顶添加元素。首先，它检查栈是否已经满了，如果是，则将 MAXSIZE 扩大为原来的两倍，通过 realloc 函数重新分配内存空间，并打印出新的栈的大小。然后将 top 指针指向栈顶元素的下一个位置，将 data 元素添加到这个位置，最后打印出“Pushing data:”和添加的元素值。

通过链表实现栈：

#include <stdio.h>
#include <stdlib.h>
 
// 定义栈的节点结构体
typedef struct Node {
    int data;           // 数据
    struct Node* next;  // 指向下一个节点的指针
} Node;
 
// 定义栈结构体
typedef struct Stack {
    Node* top;  // 指向栈顶节点的指针
    int size;   // 栈的大小
} Stack;
 
// 初始化栈
Stack* init() {
    Stack* stack = (Stack*)malloc(sizeof(Stack)); // 分配内存空间
    stack->top = NULL; // 栈顶初始化为空
    stack->size = 0; // 栈的大小初始化为0
    return stack;
}
 
// 入栈操作
void push(Stack* stack, int data) {
    Node* node = (Node*)malloc(sizeof(Node)); // 分配内存空间
    node->data = data; // 将数据赋值给节点
    node->next = stack->top; // 新节点指向当前栈顶节点
    stack->top = node; // 栈顶指针指向新节点
    stack->size++; // 栈大小加1
}
 
// 出栈操作
int pop(Stack* stack) {
    if (stack->top == NULL) { // 栈为空，无法出栈
        printf("栈为空，无法出栈\n");
        return -1;
    }
    int data = stack->top->data; // 获取栈顶节点的数据
    Node* node = stack->top; // 保存栈顶节点指针
    stack->top = stack->top->next; // 栈顶指针指向下一个节点
    free(node); // 释放栈顶节点的内存空间
    stack->size--; // 栈大小减1
    return data;
}
 
// 获取栈顶元素
int peek(Stack* stack) {
    if (stack->top == NULL) { // 栈为空，无法获取栈顶元素
        printf("栈为空，无法获取栈顶元素\n");
        return -1;
    }
    return stack->top->data; // 返回栈顶节点的数据
}
 
// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->size == 0;
}
 
// 主函数，测试代码
int main() {
    Stack* stack = init(); // 初始化栈
    push(stack, 1); // 入栈
    push(stack, 2); // 入栈
    push(stack, 3); // 入栈
    printf("%d\n", peek(stack)); // 获取栈顶元素
    printf("%d\n", pop(stack)); // 出栈
    printf("%d\n", pop(stack)); // 出栈
    printf("%d\n", pop(stack)); // 出栈
    printf("%d\n", pop(stack)); // 出栈，此时栈已为空，无法再出栈
    return 0;
}

这段代码实现了基于链表的栈结构，包括了栈的初始化、入栈、出栈、获取栈顶元素和判断栈是否为空等操作。

init()函数：

这段代码是用来初始化栈的函数。首先，使用malloc()函数为Stack类型的结构体分配内存空间，然后将分配的空间强制转换为Stack指针类型，以便在栈结构体中使用它。然后将指向栈顶节点的指针top初始化为NULL，表示当前栈为空。栈的大小size被初始化为0，因为栈当前没有任何元素。最后，函数返回栈的指针。

push(Stack* stack, int data)函数：

这段代码实现了栈的入栈操作。函数的第一个参数是指向栈结构体的指针，第二个参数是要入栈的数据。函数首先通过调用 malloc 函数来分配内存空间以创建一个新的节点（Node）。然后将要入栈的数据赋值给该节点的 data 成员变量。接着，将该节点的 next 成员变量指向当前栈顶节点，以便将新节点插入到栈顶。最后，更新栈顶指针和栈的大小，使其指向新的节点并将大小加1，完成入栈操作。

pop(Stack* stack)函数：

这段代码实现了出栈操作。首先判断栈是否为空，若为空则无法进行出栈操作，输出提示信息并返回-1。否则，获取栈顶节点的数据，保存栈顶节点指针，栈顶指针指向下一个节点，释放栈顶节点的内存空间，栈大小减1，最后返回栈顶节点的数据。这个过程中，节点的next指向了下一个节点，保证了栈的后进先出的特性。、

peek(Stack* stack)函数：

这段代码是用来获取栈顶元素的函数。它接受一个指向栈结构体的指针，如果栈为空则打印出错信息并返回 -1，否则返回栈顶节点的数据。它的实现非常简单，只需要判断栈顶指针是否为空，如果不为空则返回栈顶节点的数据。

isEmpty(Stack* stack)函数：

这段代码实现了一个判断栈是否为空的函数。它接受一个指向栈的指针，并返回一个整数值。如果栈的大小为0，即栈为空，函数返回1；否则返回0。该函数的实现非常简单，只需要比较栈的大小和0即可。如果栈的大小为0，就意味着栈中没有元素，即为空。

注意事项：

在学习栈的过程中，我们需要注意理解栈的基本概念和特性，栈是一种先进后出的数据结构，只允许在栈顶进行插入和删除操作。理解栈的这些基本概念和特性是理解和使用栈的基础。还要学会使用栈的基本操作，栈的基本操作包括入栈、出栈、获取栈顶元素、判断栈是否为空等。学会使用这些基本操作，可以更加灵活地使用栈。还有学习栈的实现方式，栈可以用数组或链表实现。了解这两种实现方式的优缺点、适用场景以及如何实现可以帮助更好地理解栈。以及熟练掌握栈的应用场景，栈在实际应用中有很多常见的场景，如函数调用栈、表达式求值、括号匹配等。掌握栈的应用场景，可以更好地应用栈解决实际问题。还要注意栈的内存管理，使用栈时需要注意内存管理，尤其是使用动态内存分配的实现方式时，需要及时释放分配的内存，避免内存泄漏。