数据结构中的栈操作

2025年2月7日 | 10分钟阅读

栈是数据结构中的一个关键概念。它们基于“后进先出”（LIFO）原则进行操作，这意味着最后添加的元素是第一个被移除的。这似乎是一个简单的概念，但在我们的日常生活和数字世界中却有着广泛的应用。

想象一下自助餐厅里的餐盘堆。干净的盘子叠放在一起，到了取餐时，最上面的盘子会先被拿走。这个简单的例子说明了栈在现实生活中的工作方式。然而，栈的用途远不止整理餐具。

在数字领域，栈在计算机系统、编程语言和算法中起着至关重要的作用。它们被广泛用于内存管理、处理函数调用，甚至在文本编辑器中实现撤销/重做功能。许多算法，如表达式求值、回溯和图遍历，都严重依赖于栈的高效实现。

本文旨在提供对栈操作、实际应用和不同实现技术的全面理解。我们将探讨 push、pop 和 peek 等基本操作，并讨论它们的时间复杂度。此外，我们将深入研究现实世界的例子和代码片段，以巩固您对栈的掌握。

什么是栈？

它们遵循“后进先出”（LIFO）原则，这意味着最后添加的元素是第一个被移除的。
栈有一个顶部指针，指向最上面的元素。所有的插入和删除都发生在这个顶部位置。
主要操作是 push（添加元素）、pop（移除顶部元素）和 peek（在不移除的情况下查看顶部元素）。
栈就像一叠盘子。当你添加一个新盘子时，它会放在盘子堆的顶部。当你需要一个盘子时，你拿走顶部那个。
在计算中，栈用于内存管理、函数调用、表达式求值、回溯算法等。
栈可以使用数组或链表实现。数组实现简单但大小固定，而链表可以动态增长。
常见应用包括文本编辑器的撤销/重做操作、浏览器历史记录导航、括号匹配和递归实现。
栈在顶部进行插入和删除操作效率很高，时间复杂度为 O(1)。

栈上的操作

提供了一些可用的操作，以便我们可以操作栈。

push() 插入一个元素到栈中
pop() 从栈中移除一个元素
top() 返回栈的顶部元素。
isEmpty() 如果栈为空则返回 true，否则返回 false。
size() 返回栈的大小。

push()

它会堆叠一个新的项目。栈溢出是指栈已满。

push() 算法

begin
 if stack is full
    return
 endif
else  
 increment top
 stack[top] assign value
end else
end procedure

pop()

它从栈中取出一个东西。这些东西按照它们被推入的相反顺序被弹出。如果栈为空，这种情况称为下溢。

pop() 算法

begin
 if stack is empty
    return
 endif
else
 store value of stack[top]
 decrement top
 return value
end else
end procedure

top()

它返回栈的顶部元素。

top() 算法

begin 
  return stack[top]
end procedure

isEmpty()

如果栈为空，则返回 true，否则返回 false。

isEmpty() 算法

begin
 if top < 1
    return true
 else
    return false
end procedure

关于栈的实践知识

日常生活中有很多栈的例子。以食堂里盘子叠放在一起的简单图示为例。由于最上面的盘子最先被取出，因此堆叠在最底部的盘子停留的时间最长。因此，很明显它遵循 LIFO/FILO 顺序。

复杂性分析

Operations  	Complexity
push() 	           O(1)
pop()              O(1)
isEmpty()          O(1)
size()	           O(1)

寄存器栈

它只能容纳有限数量的数据
实现在计算机的内存单元或寄存器内
高度/容量受限于寄存器的固定大小
用于处理程序执行期间的小型临时数据
通常用于算术、指令执行、基本函数调用等底层操作

内存栈

设计用于处理主内存中的大量数据
不受寄存器大小限制，容量可以大得多
可以利用可用内存空间的很大一部分
适用于管理需要更多栈空间的较大数据集或复杂操作

调用栈

用于管理编程语言中函数调用的特定类型的栈
每个函数调用的状态（局部变量、返回地址等）被压入调用栈
函数返回时，其状态会从栈中弹出
对于实现递归和嵌套函数调用至关重要

表达式栈

在编译器和解释器中用于解析和求值表达式
操作数被压入栈，运算符触发栈上的操作
遵循特定的优先级规则和运算顺序
常用于将中缀表达式转换为后缀/前缀表达式

撤销/重做栈

在文本编辑器、图形软件和其他交互式应用程序中使用
每个编辑操作（输入、删除、格式化等）都被压入栈
撤销操作会弹出栈中的最后一个操作，从而有效地将其撤销
重做操作会将先前已撤销的操作重新压入栈

浏览器导航栈

Web 浏览器维护独立的栈用于后退和前进导航
每个访问过的 URL 都会被推送到相应的栈中
后退按钮从后退栈中弹出 URL，前进按钮从前进栈中弹出
允许通过浏览历史记录进行高效导航

应用

寄存器栈用于处理单元内的低级操作
内存栈用于在编程语言中实现函数调用栈
内存栈对于递归至关重要，用于存储每次递归调用的状态
编译器和解释器使用内存栈进行表达式、作用域、控制流的解析
需要更多内存和栈空间的更高级场景

可以使用两种方法之一来实现栈

使用数组
链表

使用数组实现栈

// C program for array implementation of stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a stack
struct Stack {
	int top;
	unsigned capacity;
	int* array;
};

// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
	struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
	stack->capacity = capacity;
	stack->top = -1;
	stack->array = (int*)malloc(stack->capacity * sizeof(int));
	return stack;
}

// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
	return stack->top == stack->capacity - 1;
}

// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
	return stack->top == -1;
}

// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
	if (isFull(stack))
		return;
	stack->array[++stack->top] = item;
	printf("%d pushed to stack\n", item);
}

// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top--];
}

// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top];
}

// Driver program to test above functions
int main()
{
	struct Stack* stack = createStack(100);
	push(stack, 10);
	push(stack, 20);
	push(stack, 30);
	printf("%d popped from stack\n", pop(stack));
	return 0;
}

输出

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10
...........................................................
Process executed in 3.22 seconds
Press any key to continue.

使用数组实现栈的优点

易于实现
由于不使用指针，因此可以节省内存。

使用数组实现栈的缺点

由于它不是动态的，因此不能根据需要进行更改。（然而，在动态大小数组的情况下，例如 C++ 中的 vector、Python 中的 list 和 Java 中的 ArrayList，也可以通过数组实现来扩展和收缩栈。）
需要提前确定栈的总大小。

使用链表实现栈

// C program for linked list implementation of stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a stack
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;
	printf("%d pushed to stack\n", data);
}

int pop(struct StackNode** root)
{
	if (isEmpty(*root))
		return INT_MIN;
	struct StackNode* temp = *root;
	*root = (*root)->next;
	int popped = temp->data;
	free(temp);

	return popped;
}

int peek(struct StackNode* root)
{
	if (isEmpty(root))
		return INT_MIN;
	return root->data;
}

int main()
{
	struct StackNode* root = NULL;

	push(&root, 10);
	push(&root, 20);
	push(&root, 30);
	printf("%d popped from stack\n", pop(&root));
	printf("Top element is %d\n", peek(root));

	return 0;
}

输出

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
Elements present in stack : 20 10
...........................................................
Process executed in 3.22 seconds
Press any key to continue.

使用链表实现栈的优点

根据运行时需求，链表实现的栈可以扩展和收缩。
许多虚拟机，包括 JVM，都使用它。

使用链表实现栈的缺点

由于使用了指针，需要更多内存。
在栈中，无法进行随机访问。

使用单链表实现栈

所有单链表活动都应根据栈操作 LIFO（后进先出）进行，并借助该理解，我们将使用单链表创建栈。

push()

初始化一个节点
通过添加数据来更新节点的值，例如 node->data = data。
现在将顶部指针更新为当前节点，并将该节点连接到链表的顶部。

pop()

首先检查连接的链表中是否有任何节点；如果没有，则返回
如果没有，创建一个指向顶部节点的临时引用，并将其向前移动一步，然后释放临时节点。

peek()

检查是否存在任何节点，如果没有，则返回。
如果不为空，则返回链表顶部节点的值。

display()

用顶部指针初始化一个临时节点。
现在开始遍历 temp，直到遇到 NULL。
同时打印临时节点的值。

示例

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
}*top;
 
/*
Initialize an empty stack
*/
void initialize() {
    top = NULL;
} 
 
/*
Checks if Stack is empty or not
*/
int isEmpty() {
    if (top == NULL) 
        return 1;
    else
        return 0;
}
 
/*
Returns the top element of Stack
*/
int peek() {
    return top->data;
}
 
/* Count stack elements */
int getStackSize(struct node *head){
    /* Input Validation */
    if (head == NULL) { 
       printf("Error : Invalid stack pointer !!!\n");       
       return;  
    }
      
    int length = 0;
    while(head != NULL){
        head = head->next;
        length++;
    }
    return length;
}
 
/* 
Push an Element in Stack 
*/
void push(int num) {
    struct node *temp;
    temp =(struct node *)malloc(1*sizeof(struct node));
    temp->data = num;
     
    if (top == NULL) {
        top = temp;
        top->next = NULL;
    } else {
        temp->next = top;
        top = temp;
    }
}
 
/*
Pop Operation: Removes Top Element of the Stack
*/
void pop() {
    struct node *temp;
    if (isEmpty(top)) {
        printf("\nStack is Empty\n");
        return;
    } else {
        temp = top;
        top = top->next;
        printf("Removed  Element : %d\n", temp->data);   
        free(temp); 
    }
}
 
/*
 Prints the linked list representation of a stack  
*/
void printStack(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
  printf("\n");
}
 
void main() {
   /* Initialize Stack */
   initialize();
   /* Push Elements in stack */
   push(1);
   push(2);
   push(3);
   push(4);
   /* Prints Size of Stack */
   printf("Stack Size : %d\n", getStackSize(top));
   /* Printing top element of Stack */
   printf("\nTop Element : %d\n", peek());
   /* Printing Stack */
   printf("Stack as linked List\n");
   printStack(top);
   /* Removing elements from stack */
   pop();
   pop();
   pop();
   pop();
   pop();
   printStack(top);
    
   return;
}

输出

Stack Size : 4
Top Element : 4
Stack as linked List
4-->3-->2-->1
Removed  Element : 4
Removed  Element : 3
Removed  Element : 2
Removed  Element : 1
Stack is Empty
....................
Process executed in 4.43 seconds
Press any key to continue

Python 栈操作程序

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        """
        Adds an item to the top of the Stack.
        """
        self. Stack.append(item)
        print(f"{item} pushed to stack")

    def pop(self):
        """
        Removes and returns the top item from the Stack.
        Returns None if the Stack is empty.
        """
        if not self.stack:
            print("Stack is empty")
            return None
        item = self. Stack.pop()
        print(f"{item} popped from stack")
        return item

    def peek(self):
        """
        Returns the top item from the Stack without removing it.
        Returns None if the Stack is empty.
        """
        if not self.stack:
            print("Stack is empty")
            return None
        return self.stack[-1]

    def is_empty(self):
        """
        Returns True if the Stack is empty, False otherwise.
        """
        return len(self.stack) == 0

    def size(self):
        """
        Returns the number of items in the Stack.
        """
        return len(self.stack)

    def __str__(self):
        """
        Returns a string representation of the Stack.
        """
        return str(self.stack)

# Example usage
if __name__ == "__main__":
    stack = Stack()

    print("Pushing items to the stack")
    stack.push(1)
    stack.push(2)
    stack.push(3)

    print("\nStack:", stack)

    print("\nPopping items from the stack")
    stack.pop()
    stack.pop()

    print("\nTop item:", stack.peek())

    print("\nIs the stack empty?", stack.is_empty())

    print("\nSize of the stack:", stack.size())

输出

结论

栈是一种基本的数据结构，遵循后进先出（LIFO）原则，使其在各种应用中具有价值。从管理函数调用和内存分配到实现撤销/重做功能和求值表达式，栈都起着至关重要的作用。本文介绍了 push、pop 和 peek 等基本操作及其时间复杂度。我们探索了使用数组和链表实现栈的不同技术，每种技术都有其优缺点。现实世界的例子，如浏览器历史记录导航、文本编辑器操作和回溯算法，突出了栈的实际应用。无论是处理餐具还是复杂的算法，栈的 LIFO 特性使其成为计算和解决问题中不可或缺的工具。

下一主题自平衡二叉搜索树

数据结构中的栈操作

什么是栈？

栈上的操作

push()

pop()

top()

isEmpty()

关于栈的实践知识

复杂性分析

寄存器栈

内存栈

调用栈

表达式栈

撤销/重做栈

浏览器导航栈

应用

可以使用两种方法之一来实现栈

使用数组实现栈

使用数组实现栈的优点

使用数组实现栈的缺点

使用链表实现栈

使用链表实现栈的优点

使用链表实现栈的缺点

使用单链表实现栈

push()

pop()

peek()

display()

Python 栈操作程序

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的栈操作

什么是栈？

栈上的操作

push()

pop()

top()

isEmpty()

关于栈的实践知识

复杂性分析

寄存器栈

内存栈

调用栈

表达式栈

撤销/重做栈

浏览器导航栈

应用

可以使用两种方法之一来实现栈

使用数组实现栈

使用数组实现栈的优点

使用数组实现栈的缺点

使用链表实现栈

使用链表实现栈的优点

使用链表实现栈的缺点

使用单链表实现栈

push()

pop()

peek()

display()

Python 栈操作程序

结论

相关帖子

N 元树中给定节点的兄弟数量

MO 算法

连接同一层的节点

链表中的旋转操作

单向链表上的快速排序

DSA 中的超级鸡蛋掉落问题

栈中入栈和出栈的区别

N 元树的序列化和反序列化

在平衡 BST 中查找和为给定对