介绍

堆栈是C++中的线性数据结构。
它充当数据的集合，按特定顺序依次排列。
在C++的堆栈中，两个基本的堆栈操作是push和pop。
此外，堆栈上的所有操作都在一端执行。

此外，堆栈遵循LIFO(后进先出)的方式。
因此，最后插入的最后一个数据元素将被删除或者弹出。
因此，现在让我们更深入地研究该主题，以清楚地了解该主题。

C++中的堆栈工作

可以想象堆栈就像是块一样。
您可以将一个块放在另一个块的顶部，然后可以继续删除最前面插入的那个块。
堆栈也以类似的方式工作。
最新数据存储在堆栈的顶部，并在弹出时返回最顶层的元素。

现在让我们看一下可以在堆栈上执行的基本操作，

• push()
• pop()
• peek()

我们将在下面逐一讨论每个操作。

1.在堆栈上push()

考虑我们前面的块示例，推入是一种操作，其中我们在先前的集合上添加了一个新块。

在堆栈中，push()在先前推送的数据的顶部插入一个数据元素。
让我们看一下推数据的算法。

Procedure PUSH(VALUE)
  If TOP==Size_of_Stack
      Write OVERFLOW
  else
      TOP=TOP+1
      STACK[TOP]=VALUE
END of Procedure

2. Stack中的pop()

类似地，考虑我们前面的示例，pop()是将最上面的块从块堆栈中删除的操作。
因此，pop删除并返回存在于给定Stack顶部的元素。

pop()函数的算法可以通过以下方式给出：

Procedure POP()
  If TOP==-1
      Write UNDERFLOW
  else
      TOP=TOP-1
      RETURN STACK[TOP+1]
END of Procedure

3.堆栈中的peek()

窥视操作与弹出操作相似，因为它从堆栈中返回最顶层的元素。
但是peek()操作不会删除元素，只会返回它。

因此，Stack中的peek()函数的算法由下式给出：

Procedure PEEK()
  If TOP==-1
      Write UNDERFLOW
  else
      Print STACK[TOP]
END of Procedure

堆栈操作的时间复杂度

值得注意的是，在最坏的情况下，任何堆栈操作的时间复杂度都是恒定的，由O(1)给出。

在C++中实现堆栈

#include<iostream>
using namespace std;
#define max 10                

int stack[max],top=-1;           //stack declaration

void push(int num)         //push() inserts n element into the Stack
{
	if(top==max)    //checks is Stack if Full
	{
		cout<<"OVERFLOW!";
	}
	else
	{
		top=top+1;             //top is increased
		stack[top]=num;        //element is inserted
	}
} 
int pop()               //pop() pops out the top-most element from the Stack
{
	if(top==-1)      //Checks if Stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else
	{
		top=top-1;
		return stack[top+1];  //top-most element popped and returned to the main function
	}
}
int peek()
{
	if(top==-1)      //Checks if Stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else
	{
		return stack[top];     //top-most element is returned to main()
	}
}
void show()
{
	int i=0;
	if(top==-1)    //Check if stack is empty
	{
		cout<<"UNDERFLOW!";
	}
	else if(top==max)     //Check if stack is full
	{
		cout<<"OVERFLOW!";
	}
	else
	{
		while(i<=top)    //printing the current stack elements
		{
			cout<<"\t"<<stack[i];
			i++;
		}
		cout<<endl;
	}
}
int main() 
{ 
  int ch,val;
  cout<<"   :::MENU:::";       //Menu for Stack operations
  cout<<"\n1.Push into the Stack\n2.Pop from Stack\n";
  cout<<"3.Peek from Stack\n4.Show the Stack\n5.Exit";
  while(1)    
  {
      printf("\nEnter the choice:");
      scanf("%d",&ch);
       
      switch(ch)
      {
          case 1: cout<<"Enter the value to be pushed: ";
          		cin>>val;
          		push(val);
                  break;
          case 2: cout<<"The popped element is : "<<pop()<<endl;
                  break;
          case 3: cout<<"The top-most element is : "<<peek()<<endl;
          		break;
          case 4: cout<<"Stack : ";
					show();
                  break;
          case 5: exit(0);
           
          default: printf("\nError! Invalid choice!...");
      }
  }
  return 0;
}

• 首先，我们将top初始化为-1表示该堆栈为空。
  还声明了一个整数数组stack，其大小为20
• push()–此函数以后可用于将数据插入或者推入堆栈。
  一个值传递给此函数，该值需要添加到栈顶位置
• pop()–该函数从顶部弹出最新元素，并将其返回到调用该函数的位置
• peek()–窥视栈中存在的最顶层元素，并在函数调用的位置返回该元素。
  请记住，peek不会从堆栈中删除顶部元素，而只是给我们提供了peek的价值
• show()–创建此函数的唯一目的是显示堆栈的元素。

您是否注意到重复检查顶部？

我们这样做是因为，如果堆栈过载或者即使其中不包含任何数据，也无法执行堆栈上的操作，因此需要进行此检查。

例如，在执行弹出操作时，我们必须检查堆栈内部是否存储了任何数据，以避免出错。
我们通过在上面的代码中打印" UNDERFLOW"错误来解决该错误。

应用领域

有没有想过递归函数调用是如何工作的？当一个函数调用自身并暂停直到后者返回某个值时会发生什么？暂停过程使用堆栈进行。

假设我们有一些嵌套函数给出为

f1()
 {
   return f2();
 }
 f2()
 {
   return f3();
 }
 f3()
 {
   return value;
 }

在这种情况下：

• 一旦f1被调用，它将被推入堆栈
• 同样，对函数f2和f3的连续调用也将它们一对一地推送到堆栈中
• 当函数f3返回一个值时，它将弹出堆栈并触发f2函数
• 因此，功能f2和f1连续弹出。