Linux从头学：所有编程语言中的栈操作，底层原理都在这里

原创

ithorizon 7个月前 (10-13) 阅读数 17 #Linux

Linux从头学：所有编程语言中的栈操作，底层原理都在这里

栈是一种基本的数据结构，几乎在所有的编程语言中都有实现。它拥护两种首要的操作：压栈（push）和出栈（pop）。本文将深入探讨栈操作的底层原理，并展示在多种编程语言中的实现做法。

1. 栈的基本概念

栈是一种后进先出（Last In First Out, LIFO）的数据结构。这意味着最后进入栈中的元素将是第一个被移除的元素。栈通常被用来存储临时数据，例如函数调用时的参数、局部变量等。

2. 栈的底层原理

栈的底层实现通常使用数组或链表。以下是两种实现做法的简要说明：

2.1 数组实现

使用数组实现栈时，我们通常使用一个固定大小的数组，并维护一个指向栈顶元素的指针。当压栈时，指针向上移动；当出栈时，指针向下移动。以下是使用数组实现栈的伪代码：


class StackArray {
    private int[] stack;
    private int top;
    private int maxSize;
    public StackArray(int size) {
        stack = new int[size];
        top = -1;
        maxSize = size;
    }
    public void push(int item) {
        if (top < maxSize - 1) {
            stack[++top] = item;
        } else {
            throw new StackOverflowException();
        }
    }
    public int pop() {
        if (top >= 0) {
            return stack[top--];
        } else {
            throw new StackUnderflowException();
        }
    }
    public int peek() {
        if (top >= 0) {
            return stack[top];
        } else {
            throw new StackUnderflowException();
        }
    }
    public boolean isEmpty() {
        return top == -1;
    }
}

2.2 链表实现

使用链表实现栈时，每个元素都是一个节点，包含数据和指向下一个节点的指针。栈顶元素是链表的头部。以下是使用链表实现栈的伪代码：


class StackLinkedList {
    private Node top;
    private class Node {
        int data;
        Node next;
    }
    public void push(int item) {
        Node newNode = new Node();
        newNode.data = item;
        newNode.next = top;
        top = newNode;
    }
    public int pop() {
        if (top != null) {
            int data = top.data;
            top = top.next;
            return data;
        } else {
            throw new StackUnderflowException();
        }
    }
    public int peek() {
        if (top != null) {
            return top.data;
        } else {
            throw new StackUnderflowException();
        }
    }
    public boolean isEmpty() {
        return top == null;
    }
}

3. 不同编程语言中的栈操作

以下是一些常见编程语言中栈操作的示例：

3.1 C语言

C语言提供了标准库函数`malloc`和`free`来动态分配和释放内存，这让实现栈变得相对易懂。以下是一个使用C语言实现的栈的示例：


#include 
#include 
typedef struct Stack {
    int *array;
    int top;
    int maxSize;
} Stack;
Stack* createStack(int size) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->array = (int*)malloc(sizeof(int) * size);
    stack->top = -1;
    stack->maxSize = size;
    return stack;
}
void push(Stack *stack, int item) {
    if (stack->top < stack->maxSize - 1) {
        stack->array[++stack->top] = item;
    } else {
        printf("Stack overflow ");
    }
}
int pop(Stack *stack) {
    if (stack->top >= 0) {
        return stack->array[stack->top--];
    } else {
        printf("Stack underflow ");
        return -1;
    }
}
void freeStack(Stack *stack) {
    free(stack->array);
    free(stack);
}
int main() {
    Stack *stack = createStack(10);
    push(stack, 5);
    push(stack, 10);
    printf("Top element: %d ", pop(stack));
    freeStack(stack);
    return 0;
}