2024-12-03T13:52:59

栈是如何操作的

什么是栈

栈是一种后进先出的数据结构，可以理解为一个弹夹。新的元素总是从一端加入，已有的元素总是从同一端移除。栈的操作一般包括压入(push)和弹出(pop)。

栈的应用

栈有着广泛的应用，其中一些比较典型的应用包括：

表达式求值
平衡符号
程序调用和返回
网络协议处理
浏览器的历史记录
...

栈的实现

栈的底层实现方式有以下几种：

数组实现

数组实现是最简单也是最直观的实现方式。栈的实现不需要考虑数组如何增长或缩小，只需关注栈顶元素的位置和元素的值。

例如，我们可以使用一个数组来表示一个栈：

``` class Stack { private: int top; int capacity; int* array; public: Stack(int size) { top = -1; capacity = size; array = new int[size]; } ~Stack() { delete [] array; } void push(int x) { if (top == capacity-1) { cout << \"Stack overflow\"; return; } array[++top] = x; cout << x << \" pushed into stack\ \"; } int pop() { if (top == -1) { cout << \"Stack underflow\"; return -1; } int x = array[top--]; return x; } int peek() { if (top == -1) { cout << \"Empty stack\"; return -1; } return array[top]; } bool isEmpty() { return (top == -1); } }; ```

在这个数组实现中，我们限制了栈的大小。当栈满时，我们输出\"Stack overflow\"。当栈为空时，我们输出\"Stack underflow\"。

链表实现

链表实现是另一种常见的栈实现方式。这个实现方式可以用不固定的内存来存储栈数据，并且不会出现栈溢出的情况。

以下是链表实现的代码示例：

``` struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode)); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; cout << data << \" pushed into stack\ \"; } int pop(struct StackNode** root) { if (isEmpty(*root)) { cout << \"Stack underflow\"; return -1; } struct StackNode* temp = *root; *root = (*root)->next; int x = temp->data; free(temp); return x; } int peek(struct StackNode* root) { if (isEmpty(root)) { cout << \"Empty stack\"; return -1; } return root->data; } ```

这个链表实现中，我们使用动态内存分配来一次一个个节点地建立管道。在弹出元素时，我们存储头节点的值，并将其从管道中删除。