数据结构与算法----栈

栈

  栈的应用十分的普遍，比如我们按浏览器的后退键，就会逆序加载我们浏览过的网页；一些应用软件中的撤销操作也是应用了栈的方式。

栈( stack )是限定仅在表尾进行插入和删除操作的线性表。

  结合上图，我们对栈及其的操作进一步解释。允许插入和删除的一端称为栈顶 ( top)，另一端称为栈底 ( bottom) ，不含任何数据元素的栈称为空栈。栈是后进先出 ( Last In First Out) 的线性表，简称 LlFO 结构。栈的插入操作，叫作进栈，也称压栈、入栈。栈的删除操作，叫作出栈，也有的叫作弹栈。

栈的顺序存储结构

  栈是线性表的特例，因此栈也可以用数组来实现。我们把数组下标为0的一端作为栈底。我们来看下它的代码定义：

#define MAXSIZE 30
class Stack
{
public:
    Stack();
    ~Stack();
    bool push(int val);//进栈
    void traverse();//历遍
    bool pop(int& val);//出栈
    bool is_empty();//判断是否为空
    bool is_full();//判断是否为满
private:
    int top;//栈顶
    int data[MAXSIZE];//栈底为data[0]
};

栈的操作的具体代码实现：

 注意：top的初始值为-1，当存在有一个数据元素时，top=0。当进栈时要先将top++，再赋值。

#include "Stack.h"
#include<iostream>

using namespace std;

Stack::Stack():top(-1)//注意初始化top=-1
{
}


Stack::~Stack()
{
}

bool Stack::push(int val)//进栈
{
    if (is_full())return false;
    top++;
    data[top] = val;
    return true;
}
bool Stack::pop(int& val)//出栈
{
    if (is_empty())return false;
    val = data[top--];
    return false;
}
void  Stack::traverse()//历遍
{
    int p = top;
    while (-1!=p)
    {
        cout << data[p--] << " ";
    }
    cout << endl;
}
bool  Stack::is_full()//判断是否为满
{
    return MAXSIZE - 1 == top ? true : false;
}
bool Stack::is_empty()//判断是否为空
{
    return  - 1 == top ? true : false;
}

练习时间：

#include<iostream>
#include "Stack.h"
using namespace std;

int main()
{
    Stack s;
    int val;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    s.traverse();
    s.pop(val);
    cout << "出栈的值为：" << val << endl;
    s.traverse();
    system("pause");
    return 0;
}

栈的链式存储结构

  栈的链式存储结构，简称为链栈。为了节约内存空间，我们把链表的头指针和栈的栈顶合二为一。

先建立结点的类。

class Node
{
public:
    Node();
    ~Node();
    friend class Stack;
private:
    int data;
    Node* pNext;
};

再构建链栈：

#include "Node.h"
class Stack
{
public:
    Stack();
    ~Stack();
    void push(int val);//进栈
    void traverse();//历遍
    bool pop(int& val);//出栈
    bool empty();//判断是否为空
    void clear();//清空
private:
    Node *pTop;//栈顶
    Node *pBottom;//栈底
};

栈操作的代码实现：

#include "Stack.h"
#include "Node.h"
#include<iostream>
using namespace std;
Stack::Stack()
{
    pTop = new Node;
    pBottom = pTop;
    pTop->pNext = NULL;

}


Stack::~Stack()
{
}
void Stack::push(int val)
{
    Node * pNew = new Node;
    pNew->data = val;
    pNew->pNext = pTop;
    pTop= pNew;
}
void Stack::traverse()
{
    Node* p = pTop;
    while (p != pBottom)
    {
        cout << p->data << endl;
        p = p->pNext;
    }
}
bool Stack::pop(int& val)
{
    if (empty())return false;
    Node* r = pTop;
    val = r->data;
    pTop = pTop->pNext;
    delete r;
    return true;
}
bool Stack::empty()
{
    return pTop == pBottom ? true : false;
}
void Stack::clear()
{
    if (empty())return;
    Node *p = pTop;
    Node *q = NULL;
    while (p != pBottom)
    {
        q = p->pNext;
        delete p;
        p = q;
    }
    pTop = pBottom;
}

练习时间：

#include<iostream>
#include "Stack.h"
#include "Node.h"
using namespace std;

int main()
{
    Stack s;
    int val;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    s.traverse();
    s.pop(val);
    cout << "出栈的值为：" << val << endl;
    s.traverse();
    system("pause");
    return 0;
}

栈的作用

  简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

栈的应用举例：

1. 数制转换；
2. 括号匹配的检验；
3. 行编辑程序；
4. 中缀转后缀表达式求值；
5. 迷宫求解
6. 大整数相加；