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

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指针的移动实现的，并不改变内存，删除需要释放内存

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

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<math.h>
   
4. #include<iostream>
   
5. using namespace std;
   
6. 
   
7. class stack
   
8. {
   
9. public:
   
10.         char *top,*base;
    
11.         int stack_size;
    
12. }s;
    
13. 
    
14. void Initial()
    
15. {
    
16.         s.base = new char[1000];
    
17.         s.top = s.base;
    
18. }
    
19. 
    
20. 
    
21. int Two_to_ten()
    
22. {
    
23.         int ans=0,i=0;
    
24.         while (s.base != s.top)
    
25.         {
    
26.                 s.base--;
    
27.                 int x = *s.base - '0';
    
28.                 ans += x*pow(2, i++);
    
29.         }
    
30.         return ans;
    
31. }
    
32. 
    
33. void Push(char e)
    
34. {
    
35.         *s.base = e;
    
36.         s.base++;
    
37.         s.stack_size++;
    
38. }
    
39. 
    
40. void Pop()
    
41. {
    
42.         s.stack_size--;
    
43.         s.base--;
    
44.        
    
45. }
    
46. 
    
47. 
    
48. int main()
    
49. {
    
50.         char c;
    
51.         Initial();
    
52.         cout << "输入二进制字符串：";
    
53.         cin >> c;
    
54.         for (int i = 1; c != '.'; i++)
    
55.         {
    
56.                 Push(c);
    
57.                 cin >> c;
    
58.         }
    
59.         cout << "栈容量为：" << s.stack_size << endl;
    
60.         int ans;
    
61.         ans = Two_to_ten();
    
62.         cout << "十进制数为：" << ans << endl;
    
63.        
    
64. }

复制代码