@TOC
栈
只能在一边进出，先进的后出。
进出的一端叫做栈顶，另一端叫做栈底。
栈可以使用顺序存储结构，也能使用链式存储结构。
注意：栈只能在一端进行操作，这是栈的关键特征，也就是说栈不允许在中间进行查找、插入、删除等操作，(但是在实际应用中我们可以打破它)。
这里掌握初始化、入栈、出栈、取栈顶元素操作即可。
顺序存储结构实现栈
#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++)
