博客

栈


：(何时用栈？当需要“记忆”，即出现某个问题但凭现有条件不能解决，就用栈）

1.判断是否为回文字符串

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    char a[101],s[101];
    int i,len,mid,top=0;
    gets(a);
    len=strlen(a);
    if(len%2==0) mid=len/2;
    else mid=len/2+1;
    for(i=0;i<mid;i++)
    {
        s[++top]=a[i];//这里相当于top用来计数
    }
    for(i=mid;i<=len-1;i++)
    {
        if(a[i]!=s[top])
            break;
        top--;
    }
    if(top==0) printf("yes");
    else printf("no");
}

沿用洛谷P4387验证栈顺序的思路来判断是否为回文字符串
#include<cstdio>
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
stack<char>stk;
int main()
{
    char a[101];
    int i,len,mid;
    gets(a);
    len=strlen(a);
    if(len%2==0) mid=len/2;
    else mid=len/2+1;
    for(i=0;i<mid;i++)
        stk.push(a[i]);
    while(((int)stk.top())==((int)a[mid]))
//比较两个字符串是否相等用strcmp/strncmp，比较两个单字符是否相等，考虑比较ASCII码的值，强制转化为int型
    {
        stk.pop();mid++;
        if(stk.empty())break;//注意这里，为了防止栈空时还进行出栈操作
    }
    if(stk.empty()) cout<<"Yes";
    else cout<<"No";
    while(!q.empty())q.pop();//清空栈 
    return 0;
}

//带头结点L的链表法判断回文字符串
int dc(LinkList L, int n)
{
	int i;
	char s[n / 2 + 1];
	char* p = L->next;
	for (i = 0; i < n / 2; ++i)
	{
		s[i] = p->data;
		p = p->next;
	}
	if (n % 2 != 0) p = p->next;//如果是奇数个，那么中间的直接跳过
	while (i >= 0)
	{
		if (p->data == s[i])
		{
			--i; p = p->next;
		}
		else break;
	}
	if (i == -1) return 1;
	else return 0;
}

2.进制转换

#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    stack<int>stk;
    while(n==0)
    {
        cout<<0;
        return 0;
    }
    while(n)
    {
        stk.push(n%k);
        n/=k;
    }
    while(!stk.empty())
    {
        cout<<stk.top();
        stk.pop();
    }
}

3.后缀表达式（洛谷P1449）

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
stack<int>n;
int main()
{
    char ch;
    int s = 0, x, y;
    do
    {
        ch = getchar();
        switch (ch)
        {
        case'+':x = n.top(); n.pop(); y = n.top(); n.pop(); n.push(x + y); break;
        case'-':x = n.top(); n.pop(); y = n.top(); n.pop(); n.push(y - x); break;
        case'*':x = n.top(); n.pop(); y = n.top(); n.pop(); n.push(x * y); break;
        case'/':x = n.top(); n.pop(); y = n.top(); n.pop(); 
            if (x == 0) return 0;
            else n.push(y / x); break;//排除除数为0的情况
        case'.':n.push(s); s = 0; break;
        default:s = s * 10 + ch - '0'; break;
            //这里不写s*10就不对，注意以字符形式输入数字时，多个数字是多个字符
        }
    } while (ch != '@');
    printf("%d", n.top());
    return 0;
}

//后缀表达式顺序栈法
int op(int a,char Op,int b)
{
	if (Op == '+') return (a + b);
	if (Op == '-') return (a - b);
	if (Op == '*') return (a * b);
	if (Op == '/')
	{
		if (b == 0)
		{
			cout << "ERROR";
			return 0;
		}
		else return (a / b);
	}
}
int com(char exp[])
{
	int a,b,c,i;
	char Op;
	int stack[MAXSIZE], top = -1;
	for(i=0;exp[i]!='\0';i++)
	{
		if (exp[i] >= '0' && exp[i] <= '9')
			stack[++top] = exp[i] - '0';
		else
		{
			Op = exp[i];
			b = stack[top--];
			a = stack[top--];
			c = op(a, Op, b);
			stack[++top] = c;
		}
	}
	return stack[0];
}

4.前缀表达式（大话数据结构）

//判断栈顺序,Mnzn
#include<iostream>
using namespace std;
int main()
{
    string push,pop;
    cin>>push>>pop;
    int i=0,j=0,top=-1,n=push.size();
    for(;i<n;) {
    	while(i<n && top>=0 && push[top]==pop[i])--top,++i;
    	if(j>=n) break;
    	push[++top]=push[j++];
    }
    if(top==-1) cout<<"Yes";
    else cout<<"No";
    return 0;
}

//括号是否匹配
int match(char exp[], int n)
{
	char stack[MAXSIZE];
	int top = -1;
	int i;
	for(i=0;i<n;i++)
	{
		if (exp[i] == '(')
			stack[++top] = '(';
		else if (exp[i] == ')')
		{
			if (top == -1)
				return 0;//1代表匹配0代表不匹配
			else --top;
		}
	}
	if (top == -1)//所有的括号都被处理掉
		return 1；
	else return 0;
}

也可以用switch

5.利用栈实现递归函数的非递归形式（王道考研3.3.7的第三题）

double p(int n, double x)
{
	struct stack
	{
		int n;
		double val;
	}st[maxsize];
	//对于带下标的函数，把函数值和函数的下标一起用结构体来表示
	int top = -1,i;
	double fv1 = 1, fv2 = 2 * x;
	for (i = n; i >= 2; --i)
	{
		st[++top].n = i;
	}
	while (top >= 0)
	{
		st[top].val = 2 * x * fv2 - 2 * (st[top].n - 1) * fv1；
		fv1 = fv2;
		fv2 = st[top].val;//关键地方的代换
		--top;
	}
	if (n == 0)  return fv1;//注意特殊情况，每个n都要考虑到
	return fv2;
}

行编辑程序问题

迷宫求解

队列

1.实际应用（王道考研3.3.7的2和4）

可以作为数据结构的课程设计内容

Queue q,q1,q2;
void manager()
{
	int i=0, j=0;
	while (j < 10)
	{
		if (!QueueEmpty(q1) && i < 4)
		{
			DeQueue(q1, x);
			EnQueue(q, x);
			++i; ++j;
		}
		else if (!QueueEmpty(q2))
		{
			DeQueue(q2, x);
			EnQueue(q, x);
			++j; i = 0;
		}//这两段为了满足四辆客车，一辆货车的运送
		else//当客车或者货车有一种是空
		{
			while (j<10&&i < 4 && !QueueEmpty(q2))
			{//客车空了，货车补
				DeQueue(q2, x);
				EnQueue(q, x);
				++j; ++i;
			}
			i = 0;

		}
		if (QueueEmpty(q1) && QueueEmpty(q1))
			return;
	}
}

2题的交换硬座和软座的顺序，把软座全部移到硬座之前，


用双指针非常妙

两个指针p,q都指向第一个元素,若为H，就存放到栈里，若为S，就以覆盖的形式存放到原数组中   *（q++）=p，这样节省了空间，不用另开辟新的空间