【Mark】栈

程序员文章站 2022-03-10 19:55:14

...

栈的组成：一个指针，一个数组
逻辑结构：线性
物理结构：顺序存储或链式存储
特点：操作受限（位置）
LIFO 后进先出
举个栗子：
判断回文，利用栈，很方便：

#include<iostream>
#include<cstring>
using namespace std;

int main()
{
	char a[124], s[124];
	int i, len, mid, next, top;
	
	gets(a);
	len = strlen(a);
	cout << "len: " << len << endl;
	mid = len / 2 - 1;
	
	top = 0;	//栈的初始化
	//将mid之前的字符依次入栈
	for(int i = 0; i <= mid; i++) {
		s[++top] = a[i];
		cout << "s[top]: " << s[top] << endl;
	}
	
	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标
	if(len % 2 == 0)
		next = mid + 1;
	else
		next = mid + 2;
		
	//开始匹配
	for(i = next; i <= len - 1; i++) {
		if(a[i] != s[top])
			break;
		top--;
	cout << "top: " << top << endl;
	}
	
	//若top为0，则说明栈内所有字符都被一一匹配了
	if(top == 0)
		cout << "Yes";
	else
		cout << "No";
		
	getchar();
	getchar();
	return 0;
}