【数据结构与算法（七）】——栈和队列

这是第七天，每天的开始都问自己昨天做了什么，今天要做什么的一种心情

栈和队列

1、栈（数据结构）：FILO，后进先出
2、队列：LILO，先进先出
这里顺便复习以下《汇编语言（王爽）》中的函数调用栈

函数调用栈

1、几个常用的寄存器：

①ESP：栈指针寄存器，其内存中存放的是一个指针，永远指向系统栈最上面的一个栈帧的顶部。push和pop指令会改变esp的值
②EBP：基址指针寄存器，其内存放着一个指针，永远指向系统栈最上面的一个栈帧的底部。

③EIP：指令寄存器，其内存放着一个指针，永远指向下一跳待执行的指令的地址。CPU根据EIP所致的位置取出指令和操作数后，送入算数逻辑单元出运算。

2、函数调用的大致步骤：

①参数入栈：将参数从右向左一次压入系统栈中
②返回地址入栈：将当前代码区调用指令的下一跳命令地址压入栈，让函数返回时能够继续执行
③代码区跳转：处理器从当前代码区跳转到被调用函数的入口处
④栈帧调换：保存当前栈帧状态值，以备后面恢复本栈帧时使用，此时EBP入栈==>将当前栈帧切换到新栈帧（将ESP值装入EBP，更新栈帧底部）==>给新栈帧分配空间（把ESP减去所需空间的大小，抬高栈顶）

3、看个具体的例子

【主要还是看上面的分析】自己分析起来也是半吊子都不到，但是很重要的一点是要记住每次调用函数都要

push ebp；
mov ebp，esp
sub esp,[需要的空间大小]
……
……
mov esp,ebp
pop ebp
ret【回到调用出，pop EIP，之后跳转】

题目

用两个栈实现队列

用两个栈实现队列。队列声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

//模板类
template<typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const &T node);
    T deleteHead();

private:
    stack<T> stack1;
    stack<T> stack2;
};

思路：

1、一个队列包含了两个栈stack1和stack2，所以这道题的意思是要求我们操作两个“先进后出”的栈实现一个“先进先出”的队列
2、直接看图：用两个栈模拟一个队列的操作

当stack2不为空时，在stack2中的栈顶的元素是最先进入队列的元素，可以pop。当stack2为空时，我们把stack1中的元素逐个pop之后push进入stack2.由于先进入队列的元素被压倒stack1的底端，经过弹出和压入操作之后就处于stack2的顶端，又可以弹出。

template<typename T> void CQueue::appendTail(const &T node)
{
    stack1.push(node);
}

template<typename T> T deleteHead()
{
    if (stack2.size() <= 0) {
        while (stack1.size() > 0) {
            T& data = stack1.top;
            stack1.pop();
            stack2.push(data);
        }
    }
    //上面将数从1搬到2之后，2还是为空，说明1中没有数，两个stack都是空的
    if (stack2.size() == 0)
        throw new exception("queue is empty");

    T head = stack2.top();
    stack2.pop();

    return head;
}

用两个队列实现栈

template <typename T> class CStack
{
public:
    CStack(void)；
    ~CStack(void)；
    void appendTail(const T& node);
    T deleteHead();
private:
    queue<T> q1;
    queue<T> q2;
};

template<typename T> void CStack<T>::appendTail(const T& node)//在栈尾部添加数据
{
    if (!q1.empty())//不为空的执行push操作
        q1.push(node);
    else 
        q2.push(node);
}

template<typename T> T CStack<T>::deleteHead()
{
    int ret = 0;
    if (q1.empty() && q2.empty())
        throw new exception("stack is empty");

    if (q1.empty())
    {
        int i = q2.size();
        while (i > 1)//将q2队列中的数据pop到只剩一个
        {
            q1.push(q2.front());
            q2.pop();
            --i;
        }
        ret = q2.front();
        q2.pop();
    }
    else
    {
        int i = q1.size();
        while (i > 1)
        {
            q2.push(q1.front());
            q1.pop();
            --i;
        }
        ret = q1.front();
        q1.pop();
    }
    return ret;
}