《数据结构与算法》——栈

luciferzf

栈
1.栈是一种特殊的链表，与普通链表相比，栈只能先进后出，也就是栈只能对表的尾部进行操作。eg.  1->2->3->4，我们只能对4进行操作，如压入一个新的元素5到4的后面变成
1->2->3->4->5或者弹出4变成1->2->3.这种特定的操作方法有利于在一些情境下对链表的维护和操作
2.指针相减是指针指向的元素相减
3.栈的压入是向top指针当前指向的位置（top指针指向的位置一般为空）赋值，然后top指针移动到下一个位置
4.栈的弹出和删除不同，栈的弹出是用top指针的移动实现的，并不改变内存，删除需要释放内存

附上用栈实现二进制转换为十进制的代码：

#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<iostream>
using namespace std;

class stack
{
public:
        char *top,*base;
        int stack_size;
}s;

void Initial()
{
        s.base = new char[1000];
        s.top = s.base;
}


int Two_to_ten()
{
        int ans=0,i=0;
        while (s.base != s.top)
        {
                s.base--;
                int x = *s.base - '0';
                ans += x*pow(2, i++);
        }
        return ans;
}

void Push(char e)
{
        *s.base = e;
        s.base++;
        s.stack_size++;
}

void Pop()
{
        s.stack_size--;
        s.base--;
        
}


int main()
{
        char c;
        Initial();
        cout << "输入二进制字符串：";
        cin >> c;
        for (int i = 1; c != '.'; i++)
        {
                Push(c);
                cin >> c;
        }
        cout << "栈容量为：" << s.stack_size << endl;
        int ans;
        ans = Two_to_ten();
        cout << "十进制数为：" << ans << endl;
        
}