数据结构——栈

一、用数组实现栈的功能

#include<iostream>//用数组实现栈的功能
using namespace std;
#define MAX_SIZE 101//定义此栈最大空间为101
int A[MAX_SIZE];
int top = -1;//定义全局变量top表示栈顶，当栈为空时，top=-1
void Push(int x) {//压栈操作
	if (top == MAX_SIZE - 1) {
		cout << "Error:Stack overflow";
		return;
	}
	else {
		A[++top] = x;//等价于top++ A[top]=x;
	}
}
void Pop() {//弹栈操作
	if (top == -1) {
		cout << "Error:No element to pop";
		return;
	}
	else {
		top--;
	}
}
int Top() {//输出栈顶的值
	return A[top];
}
void Print() {//打印整个栈
	for (int i = 0; i <= top; i++) {
		cout << A[i] << " ";
	}
	cout << endl;
}
int main() {
	Push(1);
	Push(3);
	Print();
	Push(10);
	Pop();
	Print();
	Push(9);
	Print();
	cout << Top();
	return 0;
}

二、用链表实现栈的功能

#include<iostream>
using namespace std;
struct Node {
	int data;
	Node* link;
};
Node* top = NULL;//定义栈顶为全局变量
int num = -1;
void Push(int x) {
	Node* temp = new Node;//开辟一个新的节点
	temp->data = x;//将新的节点的数据端改成x
	temp->link = top;//将新的节点的地址端改成top
	top = temp;//更新top
	num++;
}
void Pop() {
	Node* temp = new Node;
	if (top == NULL)return;
	else {
		temp = top;
		top = top->link;
		delete temp;
		num--;
	}
}
int Top() {
	return top->data;
}
void Print() {
	int a[10];
	int i = 0;
	Node* temp = top;
	while (temp != NULL) {//用数组存放链表data，然后将数组逆序输出
		a[i]=temp->data;
		temp = temp->link;
		i++;
	}
	for (int j = num; j >= 0; j--) {
		cout << a[j] << " ";
	}
	cout << endl;
}
int main() {
	Push(1);
	Push(3);
	Print();
	Push(10);
	Pop();
	Print();
	Push(9);
	Print();
	cout << Top();
}

三、用栈反转一个字符串

#include<iostream>
#include<stack>
using namespace std;
void Reverse(char a[], int n) {
	stack<int> S;//建立一个名为S的栈
	for (int i = 0; i < n; i++) {
		S.push(a[i]);
	}
	for (int i = 0; i < n; i++) {
		a[i] = S.top();
		S.pop();
	}
}
int main() {
	char a[20];
	int n;
	cout << "请输入字符串：";
	cin >> a;
	n = strlen(a);
	Reverse(a,n);
	cout << "反转后的字符串："<<a;
}