队列和堆栈 KMP算法

66 阅读 0 评论 44 点赞

我是靠谱客的博主热心茉莉，最近开发中收集的这篇文章主要介绍队列和堆栈 KMP算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

队列和堆栈

队列：是一种先进先出的线性表利用他的性质可以做一些O(n)的简化，从队头出队，队尾进队；
堆栈：是一种后进先出的线性表，在栈顶进行操作，在程序设计时如果需要按照保存数据时的相反顺序来使用数据，用栈来实现；
一般用数组来实现对队列和堆栈的操作。
下面进行最简单的数组模拟堆栈（不是完全用数组实现）（可以用数组完全模拟实现）

//进行队列和堆栈的操作

stack<char>st1,st2   //首先 声明一下字符数组的类型
queue<char>q

//队列

while(n--) //这个堆栈的数量 
{
	char t;
	cin >>t;
	q.push(t); 
}

while(!q.empty())
{
	cout <<q.front()<<' ';  //输出队列的第一个元
	q.pop();            //
}

堆栈

while(n--) //这个堆栈的数量 
{
	char t;
	cin >>t;
	st.push(t); 
}

while(!st.empty())
{
	cout <<st.top()<<' '; //输出栈顶元素
	st.pop();
}

运算符

与 & ：只有x,y 都是1的时候，运算结果才是1，其余情况都是0；
，（1&1 = 1，1&0 = 0）、
或 | ： x,y中只要有一个是1，结果就是1，其余情况是0； 1|1 = 1，0 | 0= 0；
非！：！x 如果是x是0 ，！x=1 ，x是1 结果是0；
异或 ^ : x^y ,相同是0, 不同是1； 1 ^1 = 0 ,0 ^ 0=0 ,0 ^ 1=1;
3^5= 0000 0011 ^0000 0101 = 0000 0110 =6
（找筷子等就一个落单的问题）
输入
9
2 2 1 3 3 3 2 3 1
输出
2

#include<iostream>
#include<stdio.h> 
using namespace std;
int main()
{
	int n,s=0;
	cin >> n;
	while (n--)
	{
		int m;
		cin >>m;
		s^=m;		//可以说是整体的思想 
		cout <<s; //成对的数都变为0 ，最后就是落单的 
	}
	return 0;
 }

反码和补码

int t=5在计算机中是32为二进制
有符号整型
1： 0000 …001
-1: 1000…001
-5 的二进制数是 100000…00101
反码是 011111.11010；
补码是 :
如果是正数;正数的补码等于反码
如果是负数，补码是其反码的基础加一；

左移和右移

表示：>>(右移），<<(左移）； n>>k &1(这种操作是可以看n的二进制数的第k位是几） k =0,1,2…

 #include<iostream>
//查看m的二进数中一的个数
using namespace std;

int lowbit(int x)
{
	return x&-x;  //x&-x = x&(~x+1) 返回最后一个  1； 
}                 //也可以最后返回lowbit () 看一下最后一个 1 的个位数；
int main()
{
	int n;
	cin >>n;
	while(n--)
	{
		int x;
		cin >>x;
		int res=0;
		while(x)
		x-=lowbit(x),res ++;  
		cout <<res; //结果是二进制数中一的个数 
	}
	return 0;
 }