栈：一种收限定的线性表，既将线性表的插入和删除固定在表的一端进行。
允许进行插入删除操作的一端称为栈顶，栈顶是动态变化的，有一个指针来指示栈顶的位置。
值得注意的是，栈里的操作就像电梯一样，每次新进来的元素都会称为新的栈顶，先进后出，后进先出。
重要掌握顺序栈
顺序存储结构的栈，占据连续的内存，必须附设一个位置指针来动态的指示栈顶元素的位置，top=-1指空栈。
出栈：pop
进栈：push
判栈空：empty
获得栈顶元素：getTop
基本实现代码（C++）：
#include<iostream>
using namespace std;
#ifndef Node.h
//结点结构体
struct Node{
?? ?int data;//数据域
?? ?Node *next;//指针域
};
//栈
struct Stack{
?? ?Node *pTop;//顶部指针
?? ?Node *pBottom;//底部指针
};
void Init(Stack *pS);//初始化
void CreatStack(Stack *pS);//建栈
void Travers(Stack *pS);//遍历栈
void Push(Stack *pS,int val);//压栈
bool Pop(Stack *pS);//出栈，把栈顶的节点删掉
bool getTop(Stack *pS, int &val);//获取栈顶元素，但不删除栈顶结点
bool isEmpty(Stack *pS);//判栈空
int getSize(Stack *pS);//获取栈的长度
int main(int argc, const char * argv[]){
?? ?Stack s;//声明对象，等价于struct Stack s
?? ?int val, choose, len;//储存值，choose用户的选择
?? ?bool finished = false;
?? ?while (!finished)
?? ?{
?? ??? ?cout << "1.初始化栈：" << endl;
?? ??? ?cout << "2.建栈（以-1结束输入）：" << endl;
?? ??? ?cout << "3.遍历栈：" << endl;
?? ??? ?cout << "4.压栈：" << endl;
?? ??? ?cout << "5.出栈：" << endl;
?? ??? ?cout << "6.获取栈顶元素：" << endl;
?? ??? ?cout << "7.判断栈空：" << endl;
?? ??? ?cout << "8.获取栈的长度：" << endl;
?? ??? ?cout << "9.退出：" << endl;
?? ??? ?cout << "请输入你的选择1-9：" << endl;
?? ??? ?cin >> choose;
?? ??? ?switch (choose){
?? ??? ?case 1:
?? ??? ??? ?Init(&s);//初始化栈
?? ??? ??? ?break;
?? ??? ?case2:
?? ??? ??? ?CreatStack(&s);
?? ??? ??? ?break;
?? ??? ?case3:
?? ??? ??? ?cout << "栈中的元素：" << endl;
?? ??? ??? ?Travers(&s);//遍历栈
?? ??? ??? ?break;
?? ??? ?case4:
?? ??? ??? ?cout << "请输入要押入栈的元素：" << endl;
?? ??? ??? ?cin >> val;
?? ??? ??? ?Push(&s, val);
?? ??? ??? ?break;
?? ??? ?case5:
?? ??? ??? ?if (Pop(&s))//出栈
?? ??? ??? ??? ?cout << "出栈成功" << endl;
?? ??? ??? ?else
?? ??? ??? ??? ?cout << "弹出失败" << endl;
?? ??? ??? ?break;
?? ??? ?case6:
?? ??? ??? ?if (getTop(&s, val))//获取栈顶元素
?? ??? ??? ??? ?cout << "栈顶元素为：" << val << endl;
?? ??? ??? ?else
?? ??? ??? ??? ?cout << "栈为空" << endl;
?? ??? ??? ?break;
?? ??? ?case7:
?? ??? ??? ?if (isEmpty(&s))//判断栈空
?? ??? ??? ?cout << "栈为空" << endl;
?? ??? ??? ?else
?? ??? ??? ??? ?cout << "栈不空" << endl;
?? ??? ??? ?break;
?? ??? ?case8:
?? ??? ??? ?len = getSize(&s);
?? ??? ??? ?cout << "栈的长度为：" << len << endl;
?? ??? ??? ?break;
?? ??? ?case9:
?? ??? ??? ?finished = true;
?? ??? ??? ?break;
?? ??? ?default:
?? ??? ??? ?cout << "输入选择错误，请重新输入：" << endl;
?? ??? ?}
?? ?}
?? ?return 0;
}
//初始化
void Init(Stack *pS)
{
?? ?pS->pTop = new Node();
?? ?if (NULL == pS->pTop){
?? ??? ?cerr << "动态内存分配失败" << endl;
?? ??? ?exit(1);
?? ?}
?? ?pS->pBottom = pS->pTop;//顶部指针底部指针指向同一个位置
?? ?pS->pTop->next = NULL;
}
//建栈
void CreatStack(Stack *pS){
?? ?int val;
?? ?cout << "请输入各个元素值" << endl;
?? ?while (cin >> val&&val != -1)
?? ??? ?Push(pS, val);
}
//压栈
void Push(Stack *pS, int val){
?? ?Node *newNode = new Node();//新建结点
?? ?if (NULL == newNode){
?? ??? ?cerr << "动态内存分配失败" << endl;
?? ??? ?exit(1);
?? ?}
?? ?newNode->data = val;
?? ?newNode->next = pS->pTop;
?? ?pS->pTop = newNode;//顶端指针上移
}
//遍历栈
void Travers(Stack *pS){
?? ?Node *p = pS->pTop;
?? ?while (p != pS->pBottom){
?? ??? ?cout << p->next << "";
?? ??? ?p = p->next;
?? ?}
?? ?cout << endl;
}
//判断栈空
bool isEmpty(Stack *pS)
{
?? ?if (pS->pTop == pS->pBottom)//栈顶是否和栈底指针相同来判断栈是否为空
?? ??? ?return true;
?? ?else
?? ??? ?return false;
}
//出栈：把栈顶的节点删掉
bool Pop(Stack *pS)
{ ? if (isEmpty(pS))
?? ??? ?return false;
?? ?Node *r = pS->pTop;//暂存顶指针
?? ?pS->pTop = r->next;//栈顶指针下移
?? ?delete r;
?? ?r = NULL;
?? ?return true;
}
//获取栈顶元素
bool getTop(Stack *pS, int &val){
?? ?if (isEmpty(pS))
?? ??? ?return false;//栈为空，返回0
?? ?else?
?? ?val = pS->pTop->data;//栈不空，返回栈顶元素值
?? ?return true;
}
//获取栈长度
int getSize(Stack *pS)
{
?? ?int len = 0;
?? ?Node *p = pS->pTop;
?? ?while (p != pS->pBottom)
?? ?{
?? ??? ?len++;
?? ??? ?p = p->next;
?? ?}
?? ?return len;
}
#endif
?
结果如下图：
写了一晚上，一边理解一边对照着ChanJose大大写的，啊，加油哇！！！