栈，队列（纸牌游戏，小猫钓鱼）

文章目录

队列：FIFO
- - 实现顺序队列：
- 1.顺序循环队基本操作
- 2.链队
栈
- 1. 顺序栈
- - 栈的元素
  - 初始化操作
  - 入栈操作
  - 判断顺序栈是否为空
  - 栈的长度
  - 出栈
  - 清空一个栈
  - 销毁顺序栈
- 2.链式栈
应用
- 栈1：判断回文字符串
- 栈与队列2.纸牌游戏

队列：FIFO

（排队买奶茶）
特殊的线性结构。
只允许在队首进行删除“出队”以及
在队尾进行插入“入队”。当head == tail时，空队列。遵循先进先出原则。
队列的基本元素：一个数组，两个变量：

struct queue{
	int data[100];//主体，存储内容 
	int head;
	int tail;
};

实现顺序队列：

//实现机制：不断删除第一个（打印），第二个数放到最后面 ，直到最后一个数（首尾相接）

#include
#include
struct queue{
	int data[100];//主体，存储内容 
	int head;
	int tail;
}; 
int main() {
	struct queue q;
	int i;
	q.head = 1;//一定要初始化队首 
	for(q.tail = 1, i = 1; i<=9 ; i++,q.tail++ ) {
		scanf("%d",&(q.data[q.tail]));//入队 
	}
	//实现机制：不断删除第一个（打印），第二个数放到最后面 ，直到最后一个数（首尾相接） 
	while(q.head < q.tail) {
		printf("%dt",q.data[q.head]);
		q.head++;//队首开始遍历输出
		
		q.data[q.tail] = q.data[q.head];//新队首的数添加到队尾
		q.tail++;
		q.head++; 
	}
	return 0;
}

1.顺序循环队基本操作

初始化：front = rear = 0;
入队： base[rear] = x; rear++;
出队：x = base[front]; front++;

解决假溢出：构造头尾相接的循环表，进行求模运算
入队（队尾）： s->base[s->rear] = x;
s->rear = (s->rear + 1) % MAXQSIZE;

删除（队首）： x = s->base[s->front];
s->front = (s->front + 1) % MAXQSIZE;
队空，队满：front == rear ==0,
可用元素标记区别，
或少用一个元素：
队空：front == rear
队满：(rear +1) % MAXQSIZE == front;

typedef struct {
	int *base;//初始化动态分配内存 
	int front; //头指针 ,队头下标 
	int rear;  //尾指针 ，对位下标 
}SqQueue;
//初始化队列 
void InitQueue(SqQueue *Q) {
	Q.base = (SqQueue*)malloc(sizeof(SqQueue));//分配空间 
	if(!Q.base) { //是否分配成功 
		exit;
	} 
	Q.front = Q.rear = 0;//首位指针置空，队列为0 
}

//求队列长度
int QueueLength(SqQueue Q) {
	return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);//防止出现负的情况 
} 

//入队
int InQueue(SqQueue *Q, int e) {
	if((Q.rear + 1) % MAXQSIZE == Q.front) {//判断队满 
		return false;
	}
	Q.base[Q.rear] = e; 
	Q.rear = (Q.rear + 1) % MAXQSIZE; 
	return true;
} 
  
//出队
int DeQueue(SqQueue *Q, int e) {
	if(Q.front == Q.rear) {
		return false;
	} else{
		e = Q.base[Q.front];
		Q.front = (Q.front + 1) % MAXQSIZE;
	}
	return true;
} 

//取出队头元素
int GetHead(SqQueue Q) {
	if(Q.front != Q.rear) {
		return Q.base[Q.front];
	} 
}

2.链队

如果队列元素个数变化大或者长度事先无法估计

struct queue{
	int data[100];//主体，存储内容 
	int head;
	int tail;
};

栈

遵循先进后出的原则。

栈的实现：一个一维数组和一个指向栈顶的变量top

栈：顺序栈（顺序存储）和链式栈（链式存储），本文主要讲顺序栈

基本操作：初始化，进栈，出栈，取栈顶元素等

存储类型：同一般线性表的顺序存储结构完全相同，利用一组1地址连续的存储单元一次存放自栈底到栈顶（表尾）的数据元素，栈底(表头)一般在低地址端。栈的一个最重要的特征就是栈的插入和删除只能在**栈顶(**表尾)进行。

top指向栈顶（最后一个元素）
base指向栈底（第一个元素）
stacksize表示栈的最大容量

栈空：base == top

栈满：top - base = stacksize ,
注意防止上溢，问题无法处理
栈满报错，或分配更大空间。

top–出栈，
下溢一般作为结束条件。栈空还要弹出元素

1. 顺序栈栈的元素

typedef struct stack {
	int *base;
	int *top;
	int stacksize;
}SqStack;

初始化操作

bool InitStack(SqStack *S) { //构造空栈 
	S.base =  (int *)malloc(MAXSIZE * sizeof(int));
	//内存中分配空间
	if(!S.base) {
		exit ;
	} //检查是否分配成功 
	S.top = S.base;//空栈 
	S.stacksize = MAXSIZE;
	return true;
}

入栈操作

//入栈 ,判断咋栈是否满了 
void Push(SqStack *S,int e) { 
	if(S->top - S->base == S->stacksize) {//栈满扩大内存  
		S->base =  (int *)malloc(MAXSIZE * sizeof(int)); 
		S->top = S->base + S->stacksize; 
		S->stacksize *= 2; 
	}   
	*S->top++ = e;//解引用入栈   
}

判断顺序栈是否为空

//栈为空，返回TRUE 
bool StackEmpty(SqStack S) {
	if(S.top == S.base) {
		return true;
	} else {
		return false;
	}
}

栈的长度

int StackLength(SqStack S) {
	return  S.top - S.base;
}

出栈

//出栈,判断是否栈空 
int Pop(SqStack *S,int e) {
	if(S->base == S->top) {
		return 0;
	}
	S->top--;
	*e = *S->top;
}

清空一个栈

bool ClearStack (SqStack S) {
	if(S.base) { //栈底 
		S.top = S.base;
	}
	return true;
}

销毁顺序栈

void DeleteStack(SqStack *S) {
	if(S->base) {
		free(S->base) ;
		S->stacksizec = 0;
		S->base = S->top = NULL;
	} 
}

2.链式栈

运算受限的单链表，只能在链表头部进行
为方便起见，方向又栈顶到栈底

#include
#include
#include
//定义 
typedef struct StackNode{
	int data;
	struct StackNode *next;
}StackNode, *LinkStack;

//链栈入栈 
void Push(LinkStack *S, int e) {
	StackNode p;//创建新节点 
	p->data = e;

	p->next = S; 
	S = p; 
} 

//链式出栈,保存数据，消除栈顶 
void Pop(LinkStack *S,int e) {
	StackNode p;
	if(S == NULL) {
		break;
	} else {
		e = S->data;
		p = S;
		S = S->next;
		free(p);
	}
} 

//取栈顶元素
void GetTop(LinkStack S) {
	if(S != NULL) {
		return S->data;
	}
} 

//判断链表是否为空 
bool InitStack(LinkStack *S) {
	if(S == NULL) { 
		return true;
	} else {
		return false;
	}
}

应用栈1：判断回文字符串

#include
#include
#include

int main() {
	char a[101], s[101];
	gets(a);
	int len = strlen(a), top = 0, m;
	int i = 0, mid = len/2 - 1;//这里要mid/2-1，方便后面判断奇偶   
	//如果是奇数 abcba(长度为5) 那么从 b(len/2-1 == 2-1)就是以a[1]作为中间
	//如果是偶数 abccba(长度为6) 那么从 c(len/2-1 == 3-1)就是以a[2]作为中间	
	for(i = 0; i <= mid; i++) { 
		s[++top] = a[i];
	}
	if(len % 2 == 0) {//偶数 
		m = mid + 1; // 从a[3]开始 和前边的一一比对 
	} else { 
		m = mid + 2;  //奇数，从a[3] 开始和前边比对 
	}
	for(i = m ;i < len;i++) { 
		if(a[i] != s[top]) {  //有不相等的字符 
			break; 
		}
		top--; //从中间开始向前变量 
	}
	if(top == 0) {  //如果可以遍历到最后一位 
		printf("YES!n"); 
	} else { 
		printf("NO!n"); 
	} 
	return 0;
}

栈与队列2.纸牌游戏

游戏制度：
该游戏俗称弥竹竿，玩法是玩家双方按顺序出手中的牌导桌面上，遇到有和桌面上相等的牌后将该牌以及前面相同的数以及中甲夹的数统统放到遇到的人排后面，谁的牌先出完，对方胜利
知识点：
队列，栈，桶排序的存储，
出现问题：
C中.和->的用法区别

#include
#include

struct queue {
	int data[1000];
	int head;
	int tail;
};
//实现队列

struct stack {
	int data[10];
	int top; 
};
//实现栈，存储10张牌 

int main() {
	struct queue q1, q2;//q1小哼，q2小哈，队 
	struct stack s;//栈 ,桌子上的牌 
	q1.head = 1, q1.tail = 1;
	q2.head = 1, q2.tail = 1;//初始化队列为0，两人手中都还没有牌 
	s.top = 0;
	//桌子上没有牌 
	int i, t, flag = 0, book[10];
	for(i =1;i <= 9; i++) {
		book[i] = 0;
	}
	//初始化用来标记的数组，标记哪些牌已经在桌上 
	for(i = 1;i <= 6; i++) {
		scanf("%d",&q1.data[q1.tail]);
		q1.tail++;
		}
	//6张牌放入小哼的手上
	for(i = 1;i <= 6; i++) {
		scanf("%d",&q2.data[q2.tail]);
		q2.tail++;
	}
	//6张牌放入小哈手里
	while(q1.head < q1.tail && q2.head < q2.tail) {
	t = q1.data[q1.head];
	//小哼先出 	
	if(book[t] == 0) { //桌上没有牌面为t的牌 ,小哼没有赢 
		q1.head++;//小哼已经打出一张牌，将此牌出队 
		s.top++;
		s.data[s.top] = t; //打出的牌放到桌子上，入栈 
		book[t] = 1;//标记桌子上已经有牌面为t的牌 
	}
	else {
		q1.head++;//还是要先出牌 
		q1.data[q1.tail] = t;//赢牌了，将刚打出的归队 ，放到队尾 
		q1.tail++;
		while(s.data[s.top] != t) {//赢得牌依次放到队尾 
			book[s.data[s.top]] = 0;//取消标记
			q1.data[q1.tail] = s.data[s.top];
			q1.tail++; //放到队尾 
			s.top--; //栈顶向下走 
		}
		book[s.data[s.top]] = 0;
		q1.data[q1.tail] = s.data[s.top];
		q1.tail++;
		s.top--;
	}
	if(q1.head == q1.tail ) {
		break;
	}
	//小哼手中的牌打完，游戏结束 
	
	t = q2.data[q2.head];//小哈出一张牌 
	if(book[t] == 0) {//桌面没有牌面为t的牌 
		q2.head++; //该牌出队 
		s.top++; //分配栈的空间 
		s.data[s.top] = t;//牌入栈 
		book[t] = 1;//标记桌面上已经有的牌【类与桶排序】 
	} else { //桌上有相同大小的牌 
		q2.head++;
		q2.data[q2.tail] = t;
		q2.tail++;
		while(s.data[s.top] != t) {//桌上的牌依次放入栈 
			book[s.data[s.top]] = 0;//取消标记
			q2.data[q2.tail] = s.data[s.top];//从栈中取出依次放到队尾
			q2.tail++;
			s.top--; 
		}
		book[s.data[s.top]] = 0;
		q2.data[q2.tail] = s.data[s.top];
		q2.tail++;
		s.top--;
	}
}
	if(q2.head == q2.tail) {
		printf("小哼赢了！n");
		printf("小哼当前的牌是：n");
		for(i = q1.head;i <= q1.tail - 1;i++) {
			printf(" %d",q1.data[i]);
		} 
		if(s.top > 0) { //桌上有牌输出中上的牌 
			printf("n 桌上的牌是：n");
			for(i = 1; i <= s.top;i++) {
				printf(" %d",s.data[i]);
			} 
		} else {
			printf("桌上没有牌了！n");
		}
	} else {
		printf("小哈赢！n");
		printf("小哈当前手里的牌是：n");
		for(i = q2.head;i <= q2.tail - 1;i++) {
		printf(" %d",q2.data[i]); 
		} 
		if(s.top > 0) {
			printf("n桌上的牌是:n");
			for(i = 1;i <= s.top; i++) {
				printf(" %d",s.data[i]);
			}
		} else {
			printf("桌上没有牌了！n");
		}
	}
	return 0;
}

栈，队列（纸牌游戏，小猫钓鱼）

C/C++/C#相关栏目本月热门文章