栈实现反转#

一、实现字符串反转#

c语言的字符串以NULL结尾，也就是\0

我们先来插入到栈里面，通过索引的方式，将字母一一入栈。索引走到最后并将字母入栈完成后，还得回到原点！

所有元素入栈完成之后，索引重置后如下

接着我们利用Top获取到栈顶的元素，将其写入到字符串里，进行替换！

我们继续上面的操作，就能实现字符串反转！

原理就是利用栈后进先出的特性，让其作为容器存储字母。

1
class stack{
2
    private:
3
        char A[101];
4
        int top;
5
    public:
6
        void Push(int x);
7
        void Pop();
8
        int Top();
9
        bool IsEmpty();
10
}

1
#include<iostream>
2
#include<stack>
3
#include <cstring>
4
using namespace std;
5
void Reverse(char *C,int n){
6
    stack<char> S;
7
    //loop for push
8
    for(int i=0;i<n;i++){
9
        S.push(C[i]);
10
    }
11
    //loop for pop
12
    for(int i=0;i<n;i++){
13
        C[i]=S.top();//从栈里写入到字符串
14
        S.pop();//利用pop函数清除栈顶元素
15
    }
16

17
}
18
int main(){
19
    char C[51];
20
    cout<<"Enter a string";
21
    cin>>C;
22
    Reverse(C,strlen(C));
23
    cout<<"OUTOUT= "<<C;
24
}

二、实现链表的反转#

由于链表只有头节点的内存地址是已知的，并且我们每次操作都得按照头节点来。所以我们不可能像字符串那样定义两个指针，因为末尾节点的地址是未知的！🤔

我们在之前利用迭代(时间复杂度为O(n),空间复杂度为O(1))和递归(时间复杂度为O(n),空间复杂度为O(n))实现了链表的反转，其中会用到一些临时变量，以及递归时会隐式的使用到栈（函数调用就是一种栈）。

我们通过遍历链表来将地址一一压入栈中。

为什么不压数据？？？🤔

要是压入数据的话，压入的数据只是个数字，跟左边的链表就没半毛钱关系了，下次不要问这么纯度的问题！💢

（ps:其实我也问过🤣）

如何用cpp实现？下面简写，因为我要睡觉了😎

1
#include<stack>
2
#include<iostream>
3
struct Node {
4
    int data;           // 数据域（可以是任意类型）
5
    Node* next;         // 指针域，指向下一个节点
6
stack<struct Node*> S;

实现从链表中读数并压栈

1
Node *temp=head;
2
while(temp!=NULL){
3
    S.push(temp);
4
    temp=temp->next;
5
}

这样就能得到上一站图

接着我们覆盖与销毁

1
Node *temp=S.top();
2
head=temp;
3
S.pop();

这样操作之后，head就被我指向了末尾，并清除了栈顶的地址。

接着我们利用循环来改变链表里的节点

1
Node *temp=S.top();
2
head=temp;
3
S.pop();
4
while(!S.empty()){
5
  temp->next=S.top();
6
  S.pop();
7
  temp=temp->next;
8
}
9
temp->next=NULL;//栈空了后对应的节点让其地址连接到NULL

判断条件是看栈有没有被出空，然后修改链表的连接使其反向，删除栈内已经操作的元素，移动指针继续操作下一个元素。

完整函数

1
void Reverse(){
2
  if(head==NULL)return;
3
  Node *temp=head;
4
  while(temp!=NULL){
5
      S.push(temp);
6
      temp=temp->next;
7
  }
8
  Node *temp=S.top();
9
  head=temp;
10
  S.pop();
11
  while(!S.empty()){
12
    temp->next=S.top();
13
    S.pop();
14
    temp=temp->next;
15
  }
16
temp->next=NULL;//栈空了后对应的节点让其地址连接到NULL
17
}

三、总结#

利用栈的特性实现反转，这就是数据结构的魅力所在！

好累好累好累好累

好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累好累