2021-4-9 【堆栈】【】【】

堆栈的定义

何谓堆栈

堆栈（简称栈）是一种最常用的数据结构，是一种只能在一端进行插入或删除数据操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶当前位置是动态的，栈顶当前位置由一个称为栈顶指针的位置指示器表示。表的另一端称为栈底。在栈中没有数据元素时，称为空栈。栈的插入操作通常为进栈或入栈。栈的删除操作通常称为退栈或出栈。

栈的主要特点是“后进先出”，即后面入栈的元素先弹出。每次进栈的数据元素都放在原当前栈顶元素之上，成为新的栈顶元素，每次出栈的数据都是原当前栈顶元素。

栈的基本操作

常用的栈操作有以下几个：
初始化栈——init()
入栈——push()
出栈——pop()
取栈顶元素——gettop()
判断栈是否为空——epmty()
显示栈元素——display()
释放栈——setnull()

建立堆栈的准备工作

初始化设置

#include<stdlib.h>
#include<stdio.h>
typedef int ElemType;
typedef struct Stack *link;
typedef struct Stack Snode;

struct Stack
{
   
	ElemType data;
	struct Stack *next;
};

建立主函数

为了简便起见，下面只给出主函数的基本框架，具体功能的实现请参见后面的完整代码。

int main(){
   
	int i,x;
	link head1;
	head1=init();
	....
}

初始化栈

link init()
{
   
	link p;
	p=NULL;
	return p;
}

入栈

link push(link Head,ElemType x)
{
   
	link p;
	p=(link)malloc(sizeof(Snode));
	if(p==NULL)
	{
   
		printf("\nMemory Error\n");
		return Head;
	}
	p->data=x;
	p->next=Head;
	return p;
}

出栈

link pop(link Head)
{
   
	link p;
	p=Head;
	if(p==NULL)
		printf("\nStack is Empty!\n");
	else
	{
   
		p=p->next;
		free(Head);
	}
		return p;
}

取栈顶元素

ElemType gettop(link Head)
{
   
	if(Head==NULL)
	{
   
		printf("\nStack is Empty\n");
		return -1;
	}
	else
		return Head->data;
}

判断栈是否为空

int empty(link Head)
{
   
	if(Head==NULL)
		return 1;
	else
		return 0;
}

显示栈元素

void display(link Head)
{
   
	link p;
	p=Head;
	if(p==NULL)
		printf("\nStack is empty\n");
	else
		do
		{
   
			printf("%d",p->data);
			p=p->next;
		}while(p!=NULL);
}

释放栈

link setnull(link Head)
{
   
	link p;
	p=Head;
	while(p!=NULL)
	{
   
		p=p->next;
		free(Head);
		Head=p;
	}
	return Head;
}

指针仿真堆栈

/* 堆栈演示！*/
#include<iostream>
using namespace std;
typedef struct Stack *link;
typedef struct Stack Snode;

struct Stack
{
   
	int data;
	struct Stack *next;
};

link init()//初始化栈
{
   
	link p;
	p=NULL;
	return p;
}

link push(link Head,ElemType x)//入栈
{
   
	link p;
	p=(link)malloc(sizeof(Snode));
	if(p==NULL)
	{
   
		printf("\nMemory Error\n");
		return Head;
	}
	p->data=x;
	p->next=Head;
	return p;
}

link pop(link Head)//出栈
{
   
	link p;
	p=Head;
	if(p==NULL)
		printf("\nStack is Empty!\n");
	else
	{
   
		p=p->next;
		free(Head);
	}
		return p;
}

link setnull(link Head)//释放栈
{
   
	link p;
	p=Head;
	while(p!=NULL)
	{
   
		p=p->next;
		free(Head);
		Head=p;
	}
	return Head;
}

int lenth(link Head)//获得栈内元素个数
{
   
	int len=0;
	link p;
	p=Head;
	while(p!=NULL)
	{
   
		len++;
		p=p->next;
	}
	return len;
}

int gettop(link Head)//获取栈顶元素
{
   
	if(Head==NULL)
	{
   
		printf("\nStack is Empty\n");
		return -1;
	}
	else
		return Head->data;
}

int empty(link Head)//判断栈是否为空
{
   
	if(Head==NULL)
		return 1;
	else
		return 0;
}

void display(link Head)//显示栈内元素
{
   
	link p;
	p=Head;
	if(p==NULL)
		printf("\nStack is empty\n");
	else
		do
		{
   
			printf("%d",p->data);
			p=p->next;
		}while(p!=NULL);
}

int main()
{
   
	int i,x;
	link head1;
	head1=init();
	while(i!=6)
	{
   
		system("cls");
		cout<<"\n 1.Input a stack data";
		cout<<"\n 2.Output a stack data";
		cout<<"\n 3.Empty or Not";
		cout<<"\n 4.Display a top of stack";
		cout<<"\n 5.Display the lenth of stack";
		cout<<"\n 6.Exit and Free Stack\n";
		cout"\n Stack is: ";
		display(head1);
		cout<<"\n";
		
		cin>>i;
		switch(i)
		{
   
			case 1:while(1)
					{
   
						system("cls");
						cout<<"\n -.Input a stack data";
						cout<<"\n -.Output a stack data";
						cout<<"\n -.Empty or Not";
						cout<<"\n -.Display a top of stack";
						cout<<"\n -.Display the lenth of stack";
						cout<<"\n -.Exit and Free Stack\n";
						cout"\n Stack is: ";
						display(head1);
						cout<<"\n";
						cout<<"\ninput a number: until enter -1:\n";
						cin>>x;
						if(x==-1)
							break;
						head1=push(head1,x);
					}
					break;
			case 2:head1=pop(head1);
					break;
			case 3:if(empty(head1))
						cout<<"\nStack is empty\n";
					else
						cout<<"\nStack is not empty\n";
					break;
			case 4:cout<<"\n The top is "<<gettop(head1)<<endl;
					break;
			case 5:cout<<"\n The length of stack is "<<length(head1)<<endl;
					break;
		}
	}
	system("cls");
	head1=setnull(head1);
	display(head1);
	getchar();
	return 0;
}
					

数组仿真堆栈

不仅用链表可以仿真堆栈，还可以用数组仿真堆栈。堆栈数组声明如下：

int stack[MaxSize];
int top=-1;

其中MaxSize 是该堆栈的最大容量，top表示当前堆栈顶端的索引值，初始值设为-1表示堆栈为空。

数组仿真堆栈代码实现：

//简单数组模拟栈
#include<iostream>
using namespace std;
#define MAXN 1000

int stack[MAXN];
int top=-1;

int pop()
{
   
	int tmp;
	if(top<0)
	{
   
		cout<<"\nThe stack is empty!\n";
		return -1;
	}
	temp=stack[top--];
	return temp;
}

void push(int value)
{
   
	if(top>=MAXN)
		cout<<"\nThe stack is full!\n";
	else
		stack[++top]=value;
}

void display()
{
   
	for(int tmp=top;tmp>=0;--tmp)
		cout<<stack[tmp]<<" ";
	cout<<"\n";
}

int main()
{
   
	int ins;
	while(1)
	{
   
		cout<<"Please enter a value,(0=exit,-1=pop)\n";
		cin>>ins;
		if(ins==0)
			exit(0);
		else if(ins!=-1)
			push(ins);
		else if(ins==-1)
			pop();
			system("cls");
			display();
	}
	return 0;
}

值得一提的是，用字符串作字符栈也是一种很好的方法。此时的压栈操作，只是将相应字符加在串首（尾），而出栈操作则是删除串的第（最后）一个字符，完全不用考虑栈顶指针的问题。