提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

数据结构留作业了，正好就水一期，本次是两个关于栈的题目,难度不算很难,leetcode里面的关于栈的题目我不想在这里写，等我开始刷题再去更新。

---

一、共享栈

设有两个栈S1和S2都采用顺序栈方式，并共享一个存储区[0,…,maxsize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，设设计S1和S2有关入栈和出栈的操作算法。
这题说人话就是：

代码：

#include <iostream>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
using namespace std;

#define STDATATYPE int

typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;
//不支持打印

void STInit(ST* ps);
void STPush(ST* ps,STDATATYPE x);
void STDestroy(ST* ps);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
int STTop(ST* ps);
void STInit(ST* ps,int n)
{
	assert(ps);
	ps->a = (STDATATYPE*)malloc(sizeof(STDATATYPE) * n);
	if (ps->a == NULL)
	{
		perror("malloc");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps,STDATATYPE x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		STDATATYPE*tmp = (STDATATYPE*)realloc(ps->a,sizeof(STDATATYPE) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int STTop(ST* ps)
{
	assert(ps);
	return ps->a[(ps->top) - 1];
}

class ShareStack{
public:
	ShareStack(int maxsize)
	{
		STInit(&st,maxsize);
		top1 = -1;
		top2 = maxsize;
		_size = maxsize;
	}
	bool Push(int StackNum,int data)
	{
		
		if(top1 + 1 == top2)
		{
			cout << "栈已经满了" << endl;
			return false;
		}
		if(StackNum == 1)
		{
			st.a[++top1] = data;
		}
		else if(StackNum == 2)
		{
			st.a[--top2] = data;
		}
		else{
			//
			cout << "栈号错误" << endl;
			return false;
		}
		return true;
	}
	bool Pop(int StackNum)
	{
		if(top1 == -1 && top2 == _size)
		{
			return false;
		}
		if(StackNum == 1 && top1 >= 0)
		{
			--top1;
		}
		else if(StackNum == 2 && top2 < _size)
		{
			++top2;
		}
		else
		{			
			return false;
		}
		return true;
	}
	~ShareStack()
	{
		STDestroy(&st);
	}
private:
	ST st;
	int top1,top2;	
	int _size;
};

二、判断回文链表

这题老生常谈，用栈实现就是先获取长度，然后入一半的数据，最后进行匹配即可。
如果长度是奇数的话可以跳过一个数。

#include <iostream>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct Stack
{
	char* a;
	int top;
	int capacity;
}ST;

class Node{
	public:
	struct Node* next;
	char data;
	public:
	Node(char str)
	  :next(nullptr),data(str)
	  {}
};

void STInit(ST* ps);
void STPush(ST* ps,char x);
void STDestroy(ST* ps);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
char STTop(ST* ps);
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (char*)malloc(sizeof(char) * 4);
	if (ps->a == NULL)
	{
		perror("malloc");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPush(ST* ps,char x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		char*tmp = (char*)realloc(ps->a,sizeof(char) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;

}
int STSize(ST* ps)
{
	assert(ps);	
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
char STTop(ST* ps)
{
	assert(ps);
	return ps->a[(ps->top) - 1];
}

bool IsSymmetry(Node* head)
{
	int count = 0;
	Node* h = head,*cur = head;
	while(h != nullptr)
	{
		h = h -> next;
		count++;
	}
	ST st;
	STInit(&st);
	for(int i = 0;i < count / 2;++i)
	{
	    STPush(&st,cur->data);
		cur = cur -> next; 
	}
	if(count & 1) cur = cur -> next;
	for(int i = 0;i < count / 2; ++i)
	{
		char front = STTop(&st);
		if(front != cur->data)
		{
			return false;
		}
		STPop(&st);
		cur = cur -> next; 
	}
	return STSize(&st) == 0;
} 

---

总结

下次依旧随缘。