在本文中，我们将了解堆栈数据结构的工作原理和需求。

在编程时，我们经常处理大量不均匀的原始数据。
这就需要数据结构来存储数据并使用户能够有效地对数据进行操作。

堆栈数据结构入门

堆栈是一种线性数据结构，遵循特定的顺序进行数据的插入和操作。
Stack使用"先进先出(LIFO)"方法输入和输出数据。

堆栈以预定义的顺序(即LIFO)其中占据特定数据类型的元素。

叠放

如上图所示，堆栈中的最后一个元素是第一个从堆栈中弹出的元素。

数据项的插入和删除从堆栈的同一端进行。

让我们尝试将堆栈与现实场景联系起来。

考虑一堆书。
如果您观察的话，最后放置的书将是我们所阅读的第一本书。
而且，一本新书只能放在书堆的顶部。
因此，描述了堆栈的工作。

堆栈上执行的操作

堆栈数据结构主要处理对数据的以下操作：

• push()：此函数将数据元素添加到堆栈中。

• pop()：它从堆栈中删除顶部元素。

• top()：返回最上面的元素，即堆栈顶部的元素。

• isEmpty()：检查堆栈是否为空，即下溢情况。

• isFull()：检查堆栈是否已满，即溢出条件。

堆栈数据结构的工作

堆栈数据结构遵循LIFO模式，用于其中插入和操作元素。

注意：我们设置了一个名为" top"的指针元素，以保留堆栈中最顶层的元素。
这将有助于以有效的方式执行插入和删除操作。

PUSH(插入)操作：

• 最初，它检查堆栈是否已满，即检查溢出条件。

• 如果发现堆栈已满，它将退出并显示一条溢出消息。

• 如果发现堆栈中有可容纳元素的空间，则将顶部计数器加1，然后将数据项添加到堆栈中。

POP(删除)操作：

• 最初，它检查堆栈是否为空，即检查下溢情况。

• 如果发现堆栈为空，它将与一条下溢消息一起存在。

• 如果堆栈不为空，则显示顶部指针元素所指向的元素，然后将顶部指针减1。

堆栈数据结构的实现

可以使用以下两种方式之一来实现堆栈：

• 链表
• 数组

我们已经写了一篇有关C++中Stack的综合文章。
在演示中，我将使用C++语言的Array创建一个简单的堆栈实现。

例：

# include<iostream>
using namespace std;

class stack_data
{
  public:
  int top;
  int data[5];  
  stack_data()
  {
      top = -1;
  }

  void push_element(int a);
  int pop_element();
  void isEmpty();
  void isFull();
  void display();
};

void stack_data::push_element(int a)
{
  if(top >= 5)
  {
      cout << "Overflow\n";
  }
  else
  {
      data[++top] = a;
      
  }
}

int stack_data::pop_element()
{
  if(top < 0)
  {
      cout << "Underflow\n";
      return 0;
  }
  else
  {
      int pop = data[top--];
      return pop;
  }
}

void stack_data::isEmpty()
{
  if(top < 0)
  {
      cout << "Stack Underflow\n";
  }
  else
  {
      cout << "Stack can occupy elements.\n";
  }
}

void stack_data::isFull()
{
  if(top >= 5)
  {
      cout << "Overflow\n";
  }
  else
  {
      cout << "Stack is not full.\n";
  }
}

void stack_data::display()
{
  for(int i=0;i<5;i++)
  {
      cout<<data[i]<<endl;
  }
}

int main() {

  stack_data obj;
  obj.isFull();
  obj.push_element(40);
  obj.push_element(99);
  obj.push_element(66);
  obj.push_element(40);
  obj.push_element(11);
  
  cout<<"Stack after insertion of elements:\n";
  obj.display();

  cout<<"Element popped from the stack:\n";
  cout<<obj.pop_element()<<endl;
  
  
}

输出：

Stack is not full.
Stack after insertion of elements:
40
99
66
40
11
Element popped from the stack:
11

堆栈功能

• 堆栈遵循"后进先出"的方式来处理元素的插入和删除。

• 数据项的插入和删除仅从"单端"发生。

• 本质上，栈被认为是"动态的"，即它是"动态的数据结构"。

• 堆栈不占用数据项的"固定大小"。

• 堆栈的大小会随着每次push()和pop()操作而不断变化。

堆栈的应用

• 在编程中，堆栈可用于反转数组或者字符串的元素。

• 在需要回溯的情况下(例如N皇后问题等)，堆栈可能很有用。

• 在编辑器中，Stack可以高效地执行撤消和重做功能。

• 二叉树的前缀/前缀/后缀转换。

堆栈操作的时间复杂度

• 推送操作，即push()：O(1)
• 弹出操作，即pop()：O(1)

push()和pop()操作的时间复杂度保持为O(1)，因为数据项的插入和删除仅发生在堆栈的一端，这是要执行的单步处理。