不同的栈操作类型

2025年3月17日 | 阅读 12 分钟

引言

在计算机科学中，栈是一种基本的数据结构，遵循后进先出（LIFO）原则。它是一种抽象数据类型，包含若干可以进行push和pop作为其两个主要操作的元素。push操作将一个元素添加到栈顶，而pop操作从栈中移除并返回最顶端的元素。此外，还有其他操作，如peek、isEmpty和isFull，分别允许我们检查栈顶元素以及检查栈是否为空或已满。

栈概述

栈是一种线性数据结构，允许在该结构“栈顶”上执行操作。LIFO原则指出，最后添加到栈中的元素也是第一个被取出的元素。

栈可以处理的主要操作包括：

Push（入栈）：将元素添加到栈顶。
Pop（出栈）：移除栈顶元素。
Peek/Top（查看栈顶）：在不移除其他元素的情况下，检索最顶端的元素。
isEmpty（判断栈是否为空）：验证栈是否为空。
isFull（判断栈是否已满）：对于固定大小的栈实现，此函数确定栈是否已满。

栈操作

推送操作

在push操作中，元素被添加到栈顶。它涉及两个主要步骤：

检查栈是否已满：如果栈有固定大小，则在添加元素之前，必须检查栈是否已达到其最大容量。
插入新元素：如果栈未满，则通过增加top指针将新元素向上移动到栈中。

程序

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int stackArray[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    void push(int element) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow\n";
            return;
        }
stackArray[++top] = element;
        std::cout << "Element " << element << " pushed to stack.\n";
    }
};

int main() {
    Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);

    return 0;
}

说明

MAX_SIZE常量使用预处理器指令#define定义，并设置为100。此常量表示栈数组的最大大小。
接下来，定义了一个名为Stack的类。它有两个私有成员变量：top和
为了跟踪当前位于栈顶的元素，我们使用top变量。在Stack类的构造函数中，它被初始化为-1。
stackArray是一个大小为MAX_SIZE的整数数组。它用于存储栈中的元素。
Stack类提供了一个名为push的公共成员函数，用于将元素添加到栈中。它接受一个整数作为参数。
在push函数内部，它首先检查top是否已经达到栈的最大大小(MAX_SIZE - 1)。如果是，它会打印“Stack Overflow”（栈溢出）并退出，表示栈已达到其最大容量，无法再接受更多元素。
如果栈未满，则top会增加，并将元素添加到新top位置的stackArray中。它还会打印一条消息，表明元素已成功推入栈中。
在main函数中，创建了一个名为stack的Stack类对象。然后，调用push函数三次，将元素10、20和30推入栈中。

程序输出

Pop（出栈）操作

pop操作会移除栈中最顶端的元素。它涉及两个主要步骤：

检查栈是否为空：在尝试移除元素之前，必须检查栈是否为空。
移除栈顶元素：如果栈不为空，则通过递减top指针移除最顶端的元素。

程序

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int stackArray[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    void push(int element) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow\n";
            return;
        }
stackArray[++top] = element;
        std::cout << "Element " << element << " pushed to stack.\n";
    }

    int pop() {
        if (top < 0) {
            std::cout << "Stack Underflow\n";
            return -1;
        }
        int poppedElement = stackArray[top--];
        return poppedElement;
    }
};

int main() {
    Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);

    int poppedElement = stack.pop();
    std::cout << "Popped Element: " <<poppedElement<< "\n";

    return 0;
}

说明

程序定义了一个Stack类，它表示一个栈并维护两个私有成员变量：top和
栈中的元素存储在“stackArray”整数数组中，该数组用于包含栈的元素，而top变量用于跟踪当前位于栈顶的元素。
Stack类提供了两个主要方法。
首先，push(int element)函数用于将元素插入栈中。通过将top的当前值与MAX_SIZE - 1进行比较，它确定栈是否已满。
如果栈已满，则该方法将显示“Stack Overflow”（栈溢出）警告并终止。否则，top将递增，并将给定的元素存储在stackArray的相应索引处。此外，还会显示一条消息，表明元素已成功添加到栈中。
其次，pop()函数移除并返回栈顶元素。它通过将top的值与0进行比较来检测栈是否为空。
如果栈为空，则显示“Stack Underflow”（栈下溢）消息，并返回-1。否则，将检索stackArray中当前top索引处的元素，递减top，然后返回该元素。
在main函数中，创建了一个名为stack的Stack类对象。然后，使用push()函数将元素10、20和30添加到栈中。
之后，调用pop()函数从栈中移除栈顶元素，并将返回值存储在poppedElement中。

程序输出

Peek/Top（查看栈顶）操作

peek（或top）操作会在不移除元素的情况下检索栈顶元素。它涉及一个步骤：

检查栈是否为空：在尝试检索栈顶元素之前，确保栈不为空。
返回栈顶元素：如果栈不为空，则返回最顶端的元素。

程序

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int stackArray[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    void push(int element) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow\n";
            return;
        }
stackArray[++top] = element;
        std::cout << "Element " << element << " pushed to stack.\n";
    }

    int peek() {
        if (top < 0) {
            std::cout << "Stack is Empty\n";
            return -1;
        }
        return stackArray[top];
    }
};

int main() {
    Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);

    int topElement = stack.peek();
    std::cout << "Top Element: " <<topElement<< "\n";

    return 0;
}

说明

程序开始定义一个Stack类来表示一个栈。在Stack类中，有两个私有成员变量：top和
栈中的元素存储在“stackArray”整数数组中，该数组用于包含栈的元素，而top变量用于跟踪当前位于栈顶的元素。
Stack类提供了两个主要方法。首先，push(int element)函数用于将元素插入栈中。
通过将top的当前值与MAX_SIZE - 1进行比较，它确定栈是否已满。如果栈已满，“Stack Overflow”（栈溢出）消息将出现，并且方法将退出。
否则，top将递增，并将给定的元素存储在stackArray的相应索引处。此外，还会显示一条消息，确认元素已成功添加到栈中。
第二个实现使用peek()函数获取栈顶元素，而不会损坏栈本身。
top的值与0进行比较，以确定栈是否为空。如果栈为空，则显示“Stack is Empty”（栈为空）消息，并返回-1。否则，将返回stackArray中top索引处的元素。
在main函数中，创建了一个名为stack的Stack类对象。然后，使用push()函数将元素10、20和30添加到栈中。
之后，使用peek()函数从栈中检索栈顶元素，并将返回值存储在topElement中。

程序输出

isEmpty（判断栈是否为空）操作

isEmpty函数确定栈是否为空。它只需要一个操作：

检查top指针：栈实现中的top指针跟踪栈中最顶端的元素。如果top指针设置为-1，则表示栈为空，意味着栈中没有元素。
1. 如果top等于-1，则栈为空。
2. 如果top不等于-1，则栈包含元素，不为空。

isEmpty操作有助于确定是否可以安全地对栈执行其他操作，例如弹出元素或使用peek操作访问栈顶元素。

程序

#include <iostream>
#define MAX_SIZE 100

class Stack {
private:
    int top;
    int stackArray[MAX_SIZE];

public:
    Stack() {
        top = -1;
    }

    void push(int element) {
        if (top >= MAX_SIZE - 1) {
            std::cout << "Stack Overflow\n";
            return;
        }
stackArray[++top] = element;
        std::cout << "Element " << element << " pushed to stack.\n";
    }

    bool isEmpty() {
        return top < 0;
    }
};

int main() {
    Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);

    bool empty = stack.isEmpty();
    std::cout << "Is Stack Empty? " << (empty ? "Yes" : "No") << "\n";

    return 0;
}

说明

程序开始定义一个Stack类来表示一个栈。在Stack类中，有两个私有成员变量：top和
栈中的元素存储在“stackArray”整数数组中，该数组用于包含栈的元素，而top变量用于跟踪当前位于栈顶的元素。
Stack类提供了两个主要函数。首先，push(int element)函数用于将元素插入栈中。
通过将top的当前值与MAX_SIZE - 1进行比较，它确定栈是否已满。如果栈已满，“Stack Overflow”（栈溢出）消息将出现，并且方法将退出。
否则，top将递增，并将给定的元素存储在stackArray的相应索引处。此外，还会显示一条消息，确认元素已成功添加到栈中。
此外，isEmpty()函数用于确定栈是否为空。如果top变量小于0，则返回true，表示栈为空。否则，返回false。
在main函数中，创建了一个名为stack的Stack类对象。然后，使用push()函数将元素10、20和30推入栈中。然后，使用isEmpty()函数来确定栈是否为空。

程序输出

isFull（判断栈是否已满）操作

栈实现中的top指针表示栈最顶端元素的索引。当top指针等于栈的最大大小减1时，表示栈已满，达到其极限。

检查top指针：栈实现中的top指针表示栈最顶端元素的索引。当top指针等于栈的最大大小减1时，表示栈已满，达到其极限。
1. 如果top等于最大大小减1，则栈已满。
2. 如果top不等于最大大小减1，则栈未满，可以容纳更多元素。

isFull操作有助于确定是否可以安全地将更多元素推入栈中而不引起溢出。

程序

#include <iostream>
#define MAX_SIZE 100

class Stack {
  int top;
  int stackArray[MAX_SIZE];

public:
  Stack() {
    top = -1; // Initializing top as -1
  }

  void push(int element) {
    if (isFull()) {
      std::cout << "Stack Overflow\n";
      return;
    }
stackArray[++top] = element;
    std::cout << element << " pushed to stack.\n";
  }

  void pop() {
    if (isEmpty()) {
      std::cout << "Stack Underflow\n";
      return;
    }
    int poppedElement = stackArray[top--];
    std::cout <<poppedElement<< " popped from stack.\n";
  }

  int peek() {
    if (isEmpty()) {
      std::cout << "Stack is empty.\n";
      return -1; // Assuming -1 represents an empty stack
    }
    return stackArray[top];
  }

  bool isEmpty() {
    return (top == -1);
  }

  bool isFull() {
    return (top == MAX_SIZE - 1);
  }
};

int main() {
  Stack stack;

stack.push(10);
stack.push(20);
stack.push(30);

  std::cout << "Top element: " <<stack.peek() << std::endl;

stack.pop();
stack.pop();

  if (stack.isEmpty())
    std::cout << "Stack is empty.\n";
  else
    std::cout << "Stack is not empty.\n";

  if (stack.isFull())
    std::cout << "Stack is full.\n";
  else
    std::cout << "Stack is not full.\n";

  return 0;
}

说明

程序开始定义一个Stack类来表示一个栈。在Stack类中，有两个私有成员变量：top和
栈中的元素存储在“stackArray”整数数组中，该数组用于包含栈的元素，而top变量用于跟踪当前位于栈顶的元素。
Stack类包含一些用于执行栈操作的方法。构造函数Stack()将top变量初始化为-1，以表示一个空栈。
我们使用push(int element)函数来将元素添加到栈中。它首先通过调用isFull()方法来检查栈是否已满。
如果栈已满，则该方法将显示“Stack Overflow”（栈溢出）警告并终止。否则，top变量将递增，并将给定的元素存储在stackArray的相应索引处。会打印一条消息，表明元素已成功添加到栈中。
pop()函数移除栈顶元素。它通过调用isEmpty()来检查栈是否为空。
如果栈为空，则显示“Stack Underflow”（栈下溢）通知并退出该方法。否则，将检索stackArray中当前top索引处的元素并赋给poppedElement。
然后，top变量将递减，以反映元素已从栈中移除。打印一条消息，指示从栈中弹出了哪个元素。
peek()函数在不移除元素的情况下获取栈顶元素。它通过调用isEmpty()来检查栈是否为空。
如果栈为空，则显示“Stack is empty”（栈为空）消息，并返回-1以表示空栈。否则，将返回stackArray中当前top索引处的元素。
isEmpty()函数通过比较top值与-1来检测栈是否为空。如果栈为空，则返回true，否则返回false。
isFull()函数通过将top变量与MAX_SIZE - 1进行比较来检查栈是否已满，其中MAX_SIZE是栈的最大容量。当栈已满时，它返回true，否则返回false。
在main()函数中，创建了一个Stack类的栈实例。使用push()函数，将元素10、20和30添加到栈中。
使用peek()函数弹出并打印栈顶元素，并使用pop()从栈中弹出另外两个元素。
最后，调用isEmpty()和isFull()函数来检查栈的空闲和满状态，并根据结果打印相应的消息。

程序输出

结论

总之，数据结构中的栈操作对于以“后进先出”（LIFO）方式管理数据至关重要。栈是一种线性数据结构，其运行原理是元素只能从顶部添加或移除。栈操作主要包括push、pop、peek和isEmpty。

push函数用于将元素推入栈顶。栈会增加一个元素，并将新元素放置在顶部。另一方面，pop操作从栈的顶部移除元素。从栈中移除一个元素，然后返回被移除的元素。

我们可以使用peek函数在不移除的情况下查看栈顶元素。它提供了一种在不改变栈内容的情况下访问栈顶元素的方法。isEmpty操作确定栈是否为空，并指示是否存在任何元素。

栈在各种计算机科学应用和算法中得到了广泛应用。它们通常在编程语言中用于实现函数调用、表达式求值和管理递归。栈也有助于解决回溯、深度优先搜索和解析等问题。

下一个主题数据结构中的时间复杂度

不同的栈操作类型

引言

栈概述

栈操作

推送操作

Pop（出栈）操作

Peek/Top（查看栈顶）操作

isEmpty（判断栈是否为空）操作

isFull（判断栈是否已满）操作

结论

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

不同的栈操作类型

引言

栈概述

栈操作

推送操作

Pop（出栈）操作

Peek/Top（查看栈顶）操作

isEmpty（判断栈是否为空）操作

isFull（判断栈是否已满）操作

结论

相关帖子

复制带有 next 和 arbit 指针的链表

字典数据结构

归并排序和快速排序的区别

XOR 链表 - 内存高效的双向链表

通用树 (每个节点可以有任意数量的子节点) 层序遍历

第 k 大的连续子数组和

为什么单向链表的删除是 O(1)

数组是最好的数据结构

最长连续子序列

Morris 后序遍历

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器