1 栈的定义
栈是限定在表尾进行插入和删除操作的线性表。
2 栈的特点
1）栈是特殊的线性表，线性表也具有前驱后继性；
2）栈的插入和删除操作只能在表尾即栈顶进行；
3）后进先出。
3 栈的实现及关键点
3.1 顺序栈
3.1.1 关键点
1）顺序栈用数组实现，可以将栈底和索引为0的数组空间对齐以降低插入删除操作的空间复杂度；
2）保持栈顶指针top和数组索引一致可降低操作复杂度，空栈的条件是-1 == top，满栈的条件为 栈长-1 == top。
3.1.2 实现
#ifndef SQUENCESTACK_H
#define SQUENCESTACK_H typedef int ElemType; class SquenceStack
{
private:
ElemType* m_pData;
int m_stackSize; //栈长
int m_top; //栈顶指针 public:
SquenceStack(int stackSize);
~SquenceStack();
void ClearStack() { m_top = -; } //清空栈
bool Push(ElemType elem); //压栈
bool Pop(ElemType* pElem); //弹栈
bool VisitStack() const; //顺序遍历栈
bool EmptyStack() const { return - == m_top; } //判断是否为空栈
}; #endif
#include "pch.h"
#include "SquenceStack.h"
#include <iostream> SquenceStack::SquenceStack(int stackSize)
{
m_stackSize = stackSize;
m_top = -;
m_pData = new ElemType[stackSize];
} SquenceStack::~SquenceStack()
{
delete[] m_pData;
} bool SquenceStack::Push(ElemType elem) //压栈
{
if (m_stackSize - == m_top) //满栈
return false; ++m_top;
m_pData[m_top] = elem; return true;
} bool SquenceStack::Pop(ElemType* pElem) //弹栈
{
if (EmptyStack()) //空栈
return false; *pElem = m_pData[m_top];
--m_top; return true;
} bool SquenceStack::VisitStack() const //顺序遍历栈
{
if (EmptyStack())
{
std::cout << "The stack is Empty." << std::endl;
return false;
} std::cout << "the element of stack: ";
for (int i = ; i <= m_top; ++i)
std::cout << m_pData[i] << ' ';
std::cout << std::endl; return true;
}
测试代码：
#include "pch.h"
#include "SquenceStack.h"
#include <iostream> using namespace std; int main()
{
SquenceStack stack();
stack.VisitStack();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.VisitStack();
ElemType elem;
stack.Pop(&elem);
stack.Pop(&elem);
stack.VisitStack(); return ;
}
测试结果：
3.2 两栈共享空间
3.2.1 适用条件
当两个栈的空间需求有相反关系时，也就是一个栈增长的同时另一个栈在缩短。（增长收缩的快慢应该相同）
3.2.2 实现与关键点
用一个数组来存储两个栈。数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标0处；另一个栈的栈底为数组的末端，即下标为数组长度n-1处。
那么栈1为空时，top1等于-1；栈2为空时，top2等于n；栈满的条件为top1 + 1 == top2。
3.3 链栈
3.3.1 关键点
1）单链表的头指针是必须的，而栈的栈顶指针也是必须的，自然的，可以将头指针和栈顶指针合二为一；
2）链栈为空的条件为nullptr == top，由于只在栈顶进行操作，所以在链表中为了统一操作的哨兵结点失去了作用。
3.3.2 实现
略。
4 栈的应用场景
4.1 四则运算表达式
规则：通过两个栈来实现，其中一个保存操作数的栈，另一个保存运算符的栈。当我们从左到右遍历表达式，当遇到数字，我们就直接压如操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后计算，再把计算完的结果压入操作数栈，继续比较；其中左括号直接进栈，遇到右括号时运算到匹配到左括号为止。
该篇博客是自己的学习博客，水平有限，如果有哪里理解不对的地方，希望大家可以指正！