栈

• 栈
• • 顺序存储结构实现栈
  • 链接存储结构实现栈
  • 实际应用
  • • 迷宫求解
    • 表达式求值

栈

只能在一边进出，先进的后出。

进出的一端叫做栈顶，另一端叫做栈底。

栈可以使用顺序存储结构，也能使用链式存储结构。

注意：栈只能在一端进行操作，这是栈的关键特征，也就是说栈不允许在中间进行查找、插入、删除等操作，(但是在实际应用中我们可以打破它)。

这里掌握初始化、入栈、出栈、取栈顶元素操作即可。

顺序存储结构实现栈

#include<iostream>
using namespace std;

#define MAX_SIZE 128
typedef int DataType;

//栈的结构有多重方式定义，不用局限于这一种
/*
	例如:
		定义两个int型，并且直接开辟好数组空间
		定义一个指针，一个int top
*/
typedef struct _Stack
{
	DataType* top;	//栈顶指针
	DataType* base;//栈底指针
	//其实没有必要定义一个来标记元素的个数。
	//两个指针指向同一个数组，他们两个相减得到是中间元素的个数。
	//否则两个地址相减没有意义
}Stack;

//栈的初始化
bool initStack(Stack& S)
{
	//先用栈底指针来拿到这个刚开辟好空间的数组
	S.base = new int[MAX_SIZE];//指针来定位这个数组
	if (!S.base)
	{
		return false;
	}
	S.top = S.base;
	return true;
}

//入栈
bool pushStack(Stack& S, DataType data)
{
	if (!S.base)
	{
		return false;
	}
	if (S.top - S.base == MAX_SIZE)
	{
		//栈满
		return false;
	}

	//栈中还有空位置
	*(S.top) = data;
	S.top++;
	return true;
}

//出栈-栈顶元素出栈
DataType popStack(Stack& S)
{
	//不为空
	if (S.top != S.base)
	{
		return *(--S .top);
	}
	else
	{
		return -1;
	}
}
//返回栈顶元素         
DataType getTop(Stack& S)
{
	if (S.top - S.base == 0)
	{
		return -1;
	}
	return *(S.top-1);
}
int main(void)
{
	Stack S;
	initStack(S);	
	int n = 0;
	int m = 0;
	cin >> n;
	m = n;
	while (n)
	{	
		pushStack(S, n);
		n--;
	}
	cout << "____" << endl;
	cout << getTop(S) << endl;
	cout << "____" << endl;
	while (m)
	{
		cout << popStack(S) << endl;
		m--;
	}
	return	0;
}

入栈操作图示:

链接存储结构实现栈

#include<iostream>
using namespace std;

//数据类型
typedef int DataType;
//最大存储数量
#define  MAX_SZIE 128
//结点结构
typedef struct _Snode
{
	DataType data;
	struct _Snode* next;
}Snode;

//栈(头)结构
typedef struct _Stack
{
	int count;
	Snode* base;
	Snode* top;
}Stack;

//初始化
bool initStack(Stack* S)
{
	if (!S)
	{
		return false;
	}
	S->base = S->top = NULL;
	S->count = 0;
	return true;
}

//入栈
bool pushStack(Stack* S, Snode* node)
{
	if (!S || !node)
	{
		return false;
	}

	//第一次插入元素
	if (S->count == 0)
	{
		S->base = S->top = node;
		S->top->next = NULL;
		S->count++;
	}
	else
	{
		S->top->next = node;
		S->top = node;
		S->count++;
	}
	return false;
}
//出栈
bool popStack(Stack* S)
{
	if (!S || S->count == 0)
	{
		return false;
	}
	Snode* tempnode = S->base;

	while (tempnode->next != S->top && S->count != 1)
	{
		tempnode = tempnode->next;
	}
	if (S->count == 1)//如果栈中只剩下一个结点可以删除
	{
		S->base = NULL;
	}
	//现在tempnode是top的前一个结点
	delete S->top;
	S->top = tempnode;//如果是最后一个结点的话base和top都被置空了
	S->top->next = NULL;
	
	S->count--;
	return true;
}
//拿到栈顶元素
bool getTop(Stack* S,DataType* m_data)
{
	if (!S || S->count == 0)
	{
		return S;
	}
	*m_data = S->top->data;
	return false;
}
//判断栈是否为空
bool isEmpty(Stack* S)
{
	if (S->count == 0)
	{
		return true;
	}
	return false;
}
int main(void)
{
	Stack* S = new Stack;
	initStack(S);

	int n = 5;
	int m = n;
	while (n)
	{
		Snode* tempnode = new Snode;
		tempnode->data = n;
		pushStack(S, tempnode);
		n--;
	}

	while (m >0)
	{ 
		m--;
	}

	cout << S->top->data << " ";
	popStack(S);

	cout << S->top->data << " ";
	popStack(S);

	cout << S->top->data << " ";
	popStack(S);
	
	cout << S->top->data << " ";
	popStack(S);

	cout << S->top->data << " ";
	popStack(S);

	if (!isEmpty(S))
	{
		cout << S->top->data << " ";
	}


	int temp = 0;
	getTop(S, &temp);
	cout << temp << endl;

	delete S;
	return	0; 
}

补充:要修改指针指向地址，可以传递二级指针。

一级指针修改值。

实际应用

迷宫求解

链接——【栈】实现迷宫求解(C++)(详解)

表达式求值

链接——【数据结构】栈(C++)