用栈反转一个字符串或反转一个链表

Introduction of Stack

栈是一种数据结构，属于抽象数据结构(ADT)，遵循Last-In-First-Out(LIFO)原则。

基本操作：

1）Push(x)–在栈中插入x

2）Pop()–移除最近插入的元素

3）Top()–返回栈顶的元素

4）Empty()–判断栈是否为空

以上几个操作的时间复杂度均为O(1)。

栈的应用：

–Function calls/recursion

–Undo in an editor

–Balance Parentheses

Implementation of Stack

I. Array implementation

int A[10];
int top = -1;//global
void Push(int x){
    top = top + 1;
    A[top] = x;
}
void Pop(){
    top = top-1;
}
int Top(){
    return A[top]; 
}
bool IsEmpty(){
    if(top ==-1)
        return true;
    else
        return false;
}

II. Linked list implementation

如果Push在链表的末尾，那么每次操作的时间复杂度为O(n)，不符合栈的O(1)operation。所以每次Push都将新元素插入链表的头部。

struct Node{
    int data;
    struct Node* link;
}
struct Node* top = NULL;
void Push(int x){
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->link = top;
    top = temp;
}
void Pop(){
    struct Node* temp;
    if(top == NULL)
        return;
    temp = top;
    top = top->link;
    free(temp);
}

Using stack to reverse

I. Reverse a string

调用C++中自带的stack库函数，能够直接定义一个栈，并且直接调用以上几种操作。

调用语法为：头文件–<stack>,语法 stack <变量数据类型> 栈名称；name.option()为操作

代码

#include<iostream>
#include<stack>
using namespace std;
void Reverse(char *C,int n){
	stack<char> S;
	for(int i=0;i<n;i++){
		S.push(C[i]);
	}
	for(int i=0;i<n;i++){
		C[i] = S.top();
		S.pop();
	}
}
int main(){
	char C[51];
	printf("Enter a string\n");
	gets(C);
	Reverse(C,strlen(C));
	printf("Output: %s",C);
	return 0;
}

输入/出结果

Enter a string
hello!
Output: !olleh

II. Reverse linked list

代码

#include<iostream>
#include<stack>
using namespace std;
struct Node{
    int data;
    struct Node* link;
};
struct Node* head;
void Reverse(){
    stack<struct Node*> S;
	Node* temp = head;
	while(temp != NULL){
        S.push(temp);
        temp = temp->link;
    }
    temp = S.top();
    head = temp;
    S.pop();
    while(!S.empty()){
        temp->link = S.top();
        S.pop();
        temp = temp->link;
    }
    temp->link = NULL;
}
void InsertAtHead(int x){
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->link = head;
    head = temp;
}
void Print(){
    struct Node* temp = head;
    while(temp->link != NULL){
        printf("%d ",temp->data);
        temp = temp->link;
    }
    printf("\n");
}
int main(){
    head = NULL;
    InsertAtHead(5);
    InsertAtHead(4);
    InsertAtHead(3);
    InsertAtHead(2);
    InsertAtHead(1);
    printf("Input: ");
    Print();
    Reverse();
    printf("Output: ");
    Print();
    return 0;
}

输出结果

Input: 1 2 3 4 5
Output: 5 4 3 2 1