欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数据结构与算法(七)】——栈和队列

程序员文章站 2022-03-13 10:37:17
...

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

栈和队列

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;
}