栈知识总结

Julia999

栈---线性结构
从数据结构上看，栈和队列也是线性表，其特别之处在于他们的基本操作是线性表操作的子集，即他们是操作受限的线性表
栈：打个简单的比方：空栈就是一个空的水杯，如果你要往里面加水，只能从杯口加入（从栈顶加入），如果你要倒水也只能从杯口倒出（从栈顶删除），那么杯子的杯底就是栈的栈底
对应的来看，栈的插入和删除操作只能在表尾进行。
栈的特点：先进后出（想想水杯）


栈又可以分为顺序栈和链栈

顺序栈
顺序栈是指利用顺序存储的栈（同时设指针top指向栈顶元素在栈中的位置，以base指针指示栈底元素在顺序表中的位置）
所以当base和top相等时，表示为空栈

（1）base为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base的值为NULL时，则表明栈结构不存在。top为栈顶指针，其初始值指向栈底。
每当插入新的栈元素时，指针top增1，删除栈顶元素时，指针top减1。因此，栈空时，top和base相等，都指向栈底，栈非空时，top始终指向栈顶元素的上一个位置。


操作：
（1）初始化
顺序栈的初始化操作就是为顺序栈动态分配一个预定大小的数组空间。
a.为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底
b.栈顶指针top初始为base，表示栈为空
c.stacksize置为栈的最大容量MAXSIZE

（2）入栈
入栈操作是指在栈顶插入一个新的元素
a.判断栈是否已满，若满则返回false
b.将新的元素压入栈顶，栈顶指针加1
（3）出栈
将栈顶元素删除
a.判断栈是否为空，如果为空，返回false
b.栈顶指针减1，栈顶元素出栈
（4）取栈顶元素
当栈为非空时，此操作返回当前栈顶的元素的值，栈顶指针保持不变


链栈
顺序栈的操作受到容量的限制，所以我们要学习链栈
链栈是用链式存储结构实现的栈
tips：由于栈的主要操作是在栈顶上插入和删除，所以以链表的头部作为栈顶是最方便的，并且不需要像单链表那样附加一个头节点
操作：
（1）初始化
初始化就是构造一个空栈，因为没必要设头节点，所以直接将栈顶指针置为空即可。
（2）入栈
不需要判断栈是否满，只需要为入栈元素动态分配一个节点空间
a.为入栈元素e分配空间，用指针p指向
b.将新节点数据域置e
c.将新节点插入栈顶
d.修改栈顶指针为p
（3）出栈
需要注意的是，出栈后需要释放栈顶元素的内存空间
a.判断栈是否为空，是则返回false
b.将栈顶元素赋给e
c.临时保存栈顶元素的空间以便释放
d.修改栈顶指针，指向新的栈顶元素
e.释放原栈顶元素的空间
（4）取栈顶元素
返回栈顶元素的值，栈顶指针保持不变


栈与递归
栈有一个重要的应用是在程序设计语言中实现递归

顺序栈：

#if 0

#include<iostream>
using namespace std;

#define ElemType int
#define Maxsize 100

//栈的数据结构
typedef struct stack
{
        ElemType *base; //栈底指针
        ElemType *top;  //栈顶指针
        int stacksize;  //栈可用的最大容量
}Stack;

//初始化函数
void initStack(Stack &s)
{
        s.base = new ElemType[Maxsize];
        if (s.base == NULL)
        {
                cout << "内存分配失败！" << endl;
                return;
        }
        s.top = s.base;
        s.stacksize = Maxsize;
}

//入栈
void pushStack(Stack &s,ElemType a)
{
        //判断栈是否已满
        if (s.top - s.base == s.stacksize)
        {
                cout << "栈已满！" << endl;
                return;
        }
        *(s.top) = a;
        s.top++;
}

void PopStack(Stack &s)
{
        //判断栈是否已满
        if (s.top - s.base == s.stacksize)
        {
                cout << "栈已满!" << endl;
                exit(0);
        }
        //栈空
        if (s.top == s.base)
        {
                cout << "栈空！" << endl;
                exit(0);
        }
        s.top--;
}


void GetTopElem(Stack s,ElemType &e)
{
        //栈空
        if (s.top == s.base)
        {
                cout << "栈空！" << endl;
                exit(0);
        }
        e = *(--s.top);
}

void display(Stack s)
{
        //栈为空
        if (s.top == s.base)
        {
                cout << "栈为空！" << endl;
                exit(0);
        }
        while (s.top != s.base)
        {
                cout << *(--s.top) << "\t";
        }
        cout << endl;
}

//创建一个操作菜单
void menu()
{
        cout << "*****************顺序栈的操作*****************" << endl;
        cout << "**********************************************" << endl;
        cout << "*         1.入栈           2.出栈            *" << endl;
        cout << "*         3.取栈           4.显示            *" << endl;
        cout << "*                  5.退出                    *" << endl;
        cout << "**********************************************" << endl;

        Stack s;
        initStack(s);

        int choice;
        ElemType a;
        ElemType e;

        while (1)
        {
                cout << "请输入你的操作：";
                cin >> choice;

                if (choice == 5)
                        break;
                switch (choice)
                {
                case 1:
                        cout << "请输入需要入栈的元素:";
                        cin >> a;
                        pushStack(s, a);
                        break;
                case 2:
                        PopStack(s);
                        break;
                case 3:
                        GetTopElem(s,e);
                        cout << "栈顶元素是：" << e << endl;
                        break;
                case 4:
                        display(s);
                        break;
                default:cout << "输入有误！" << endl;
                }
        }
}
int main()
{
        menu();
        system("pause");
        return 0;
}

#endif 

由于链栈的操作跟链表很相似，所以顺便来温习一下链表：

#if 0
#include<iostream>
using namespace std;

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

//1.创建表 链表的实质就是结构体和结构体连在一起
//创建表就是创建结构体变量 用指针去表示--->指针成为变量--->动态内存
//如何去表示一个表： 用一个节点去表示整个链表
struct Node* creatList()
{
        struct Node *head = new struct Node;
        //变量规则：需要初始化才能使用
        //data为什么没有初始化-->>有表头的链表
        //差异化处理

        head->next = NULL;
        return head;
}

//创建节点，为插入做准备
struct Node* creatNode(int data)
{
        //结构体指针-->结构体变量
        struct Node* node = new struct Node;
        //给结构体变量初始化
        node->data = data;
        node->next = NULL;
        //返回创建节点
        return node;
}

//插入节点
//1.表头插入
//函数的参数设计是有含义的：插入哪个链表？插入新节点的数据？
void insertListByHead(struct Node *headNode, int a)
{
        //插之前：首先要有新的节点
        struct Node* nextNode = creatNode(a);  //封装了一个创建节点的函数

        nextNode->next = headNode->next;
        headNode->next = nextNode;
}

//2.表尾插入
//找到尾节点在哪里
void insertListByTail(struct Node* headNode, int a)
{
        struct Node *newNode = creatNode(a);

        struct Node* backNode = headNode;
        while (backNode->next)
        {
                backNode = backNode->next;
        }

        backNode->next = newNode;
        newNode->next = NULL;
}

void printList(struct Node* headNode)
{
        //因为是有表头的，所以要从第2个节点开始打印
        //怎么打印 要移动 动起来
        struct Node* p = new struct Node;
        p = headNode->next;
        while (p)
        {
                cout << p->data << "\t";
                p = p->next;
        }
        cout << endl;
}

int main()
{
        struct Node *List = creatList();
        insertListByHead(List, 1);
        insertListByHead(List, 2);
        insertListByHead(List, 3);

        insertListByTail(List, 4);
        insertListByTail(List, 5);


        printList(List);


        system("pause");
        return 0;
}
#endif 

链栈：

#if 0

#include<iostream>
using namespace std;

//节点结构体
struct Node
{
        int data;
        struct Node *next;

};

//创建节点
struct Node* creatNode(int data)
{
        struct Node* newNode = new Node;
        newNode->data = data;
        newNode->next = NULL;

        return newNode;
}


//既然是一个链栈，那我们可以写一个链栈的结构体
struct Stack
{
        struct Node * StackTop;   //用栈顶指针表示整个链栈
        int size;                 //数据结构的万金(栈的大小）
};


//一样的，首先我们需要创建栈
struct Stack* creatStack()
{
        //指针-->变量
        struct Stack *myStack = new Stack;
        //初始化变量
        myStack->StackTop = NULL;
        myStack->size = 0;
        //返回变量
        return myStack;
}

//入栈
void push(struct Stack *mystack, int data)
{
        //入栈->链表表头插入的操作
        struct Node *newNode = creatNode(data);

        //要注意的是，下面的插入的时候没有了头节点
        newNode->next = mystack->StackTop;
        mystack->StackTop = newNode;
        mystack->size++;
}

//获取栈顶元素
void top(struct Stack*mystack, int &e)
{
        if (mystack->size == 0)
        {
                cout << "栈空！" << endl;
                exit(0);
        }
        e = mystack->StackTop->data;
}


//出栈
void pop(struct Stack *mystack)
{
        if (mystack->size == 0)
        {
                cout << "栈已空！" << endl;
                exit(0);
        }
        //在删除的时候特别需要注意的是，如果直接就删除了，那么就没法找到下面一个了
        //所以我们需要把要删除的下一个节点保存起来再删除节点，再将指针往后移
        //步骤：保存->删除->重置->长度-1
        struct Node *nextNode = mystack->StackTop->next;
        delete(mystack->StackTop);
        mystack->StackTop = nextNode;
        mystack->size--;
}

//判断栈是否为空
int empty(struct Stack mystack)
{
        if (mystack.size == 0)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

void display(struct Stack *mystack)
{
        struct Node *p = mystack->StackTop;
        while (p->next)
        {
                cout << p->data << "\t";
                p = p->next;
        }
        cout << p->data;
        cout << endl;
}

//创建一个操作菜单
void menu()
{
        cout << "******************链栈的操作******************" << endl;
        cout << "**********************************************" << endl;
        cout << "*         1.入栈           2.出栈            *" << endl;
        cout << "*         3.取栈           4.显示            *" << endl;
        cout << "*                  5.退出                    *" << endl;
        cout << "**********************************************" << endl;

        struct Stack *mystack = creatStack();

        int choice;
        int a;//入栈元素
        int e; //取栈顶元素

        while (1)
        {
                cout << "请输入你的操作：";
                cin >> choice;

                if (choice == 5)
                        break;
                switch (choice)
                {
                case 1:
                        cout << "请输入需要入栈的元素:";
                        cin >> a;
                        push(mystack, a);
                        break;
                case 2:
                        pop(mystack);
                        break;
                case 3:
                        top(mystack, e);
                        cout << "栈顶元素是：" << e << endl;
                        break;
                case 4:
                        display(mystack);
                        break;
                default:cout << "输入有误！" << endl;
                }
        }
}
int main()
{
        menu();

        system("pause");
        return 0;
}
#endif

_2_

对不起，我还没学C语言