-
括号匹配问题
其中题意是：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
其中我是用栈的思想：“后进先出”的特征。将有关的左括号全部入栈，一个左括号必定遇到的是和自己匹配的右括号，否则不满足括号匹配问题；
下面加入有一个字符串：s="{()}";将步骤用图来表示：
这个题不难，但是有两个点要注意一下，字符串只为左括号和只为右括号的情况，这两个情况考虑到，这个要用到栈，所以写这个代码要先把栈的相关操作实现一下，我直接把核心代码贴出来：
2.用队列实现栈
-
题目的意思是：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作(入栈，出栈，获取栈顶元素，判空等)；
首先这个题目要用到两个队列的先入先出规则，构成栈的后入先出的特性；
核心代码：
//栈结构
typedef struct{
Queue* q1;
Queue* q2;
} MyStack;
/** Initialize your data structure here. */
MyStack* myStackCreate() {
MyStack* p=(MyStack*)malloc(sizeof(MyStack));
if(NULL==p)
{
assert(0);
return NULL;
}
//初始化队列
p->q1=(Queue*)malloc(sizeof(Queue));
p->q2=(Queue*)malloc(sizeof(Queue));
QueueInit(p->q1);
QueueInit(p->q2);
return p;
}
//q1入栈，站顶元素，q2:出栈
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
assert(obj);
if(!QueueEmpty(obj->q1))
{
QueuePush(obj->q1, x);
}
else
{
QueuePush(obj->q2, x);
}
}
bool myStackEmpty(MyStack* obj) {
if(QueueEmpty(obj->q1)&&QueueEmpty(obj->q2))
return true;
return false;
}
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
//出栈
int top;
assert(obj);
if(QueueEmpty(obj->q1))
{ //q1为空
// for(int i=0;i<(QueueSize(&obj->q2)-1);i++)
// {
while(QueueSize(obj->q2)>1)
{
//q2入队列
QueuePush(obj->q1,QueueFront(obj->q2));
//q1队头出队列
QueuePop(obj->q2);
}
// }
top=QueueFront(obj->q2);//获取队头元素
QueuePop(obj->q2);
}
else
{ //q1不为空
for(int i=(QueueSize(obj->q1)-1);i>0;i--)
{
// while(QueueSize(&obj->q1)>1)
//{
//q2入队列
QueuePush(obj->q2,QueueFront(obj->q1));
//q1队头出队列
QueuePop(obj->q1);
//}
}
top=QueueFront(obj->q1);//获取队头元素
QueuePop(obj->q1);
}
return top;
}
/** Get the top element. */
int myStackTop(MyStack* obj) {
//获取栈顶元素
if(QueueEmpty(obj->q2))
{
//q2为空
return QueueBack(obj->q1);
}
//q1为空
return QueueBack(obj->q2);
}
/** Returns whether the stack is empty. */
//bool myStackEmpty(MyStack* obj) {
//if(QueueEmpty(obj->q1)&&QueueEmpty(obj->q2))
// return true;
//return false;
//}
void myStackFree(MyStack* obj) {
QueueDestroy(obj->q1);
QueueDestroy(obj->q2);
free(obj);
obj=NULL;
}
3.栈实现队列
和上面的题类似，用两个栈实现队列的一些基本操作（入队，出队，获取元素，判空）；
基本思想是：入队的时候在入队的栈中入，出队的时候也让栈顶出，如果出队的栈为空，那直接将队尾的元素导入到出队的栈中，刚好栈底是最后导入的，它先出去，就这样用两个栈实现了队列的先入先出的特性；代码实现：
typedef struct {
Stack* q1; //入队列
Stack* q2; //出队列
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue* p=(MyQueue*)malloc(sizeof(MyQueue));
if(NULL==p)
{
assert(0);
return NULL;
}
StackInit(p->q1);
StackInit(p->q2);
return p;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
//入队列,q1入队列
StackPush(obj->q1, x);
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
//出队列，q2出队列
//判空
int top=0;
if(!StackEmpty(obj->q2))
{
top=StackTop(obj->q2);
StackPop(obj->q2);
}
else
{
while(StackSize(obj->q1))
{
//将q1的元素全部移到q2中
StackPush(obj->q2, StackTop(obj->q1));
StackPop(obj->q1);
}
top=StackTop(obj->q2);
StackPop(obj->q2);
}
return top;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
//队头元素
if(StackEmpty(obj->q2))
{
while(StackSize(obj->q1))
{
//将q1的元素全部移到q2中
StackPush(obj->q2, StackTop(obj->q1));
StackPop(obj->q1);
}
}
return StackTop(obj->q2);
//return StackTop(&obj->q1);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return (StackEmpty(obj->q1)&&StackEmpty(obj->q2));
}
void myQueueFree(MyQueue* obj) {
StackDestroy(obj->q1);
StackDestroy(obj->q2);
free(obj);
}
4.循环队列
循环队列是为了解决正常队列随着不断地入队和出队的操作，出现了空间浪费的情况(假溢出)；
循环队列使用数组实现，在实现循环队列的时候要注意几个点，插入的时候，队列是否满；出队的时候队列是否空；获取队尾元素的时候，指针的位置（头和尾部）；
代码实现：
typedef struct {
int* array;
int front;
int back;
int capticpy;
int count;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue s;
MyCircularQueue* p=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
p->array=(int*)malloc(sizeof(int)*k);
if(NULL==p->array)
{
assert(0);
return NULL;
}
p->front=p->back=p->count=0;
p->capticpy=k;
return p;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->count==0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->count==obj->capticpy;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//插入
if(myCircularQueueIsFull(obj))
{
return false;
}
else
{ //back在队尾的时候
if(obj->back==obj->capticpy)
{
obj->back=0;
}
obj->array[obj->back]=value;
obj->back++;
obj->count++;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//删除元素
if(myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
//obj->front++;
obj->count--;
if(obj->front==obj->capticpy)
{
obj->front=0;
}
else
{
obj->front++;
}
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
//队列不为空
return obj->array[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
//obj->back-1+obj->
return obj->array[(obj->back-1+obj->capticpy)%obj->capticpy];
}
//bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//return obj->count==0;
//}
//bool myCircularQueueIsFull(MyCircularQueue* obj) {
//return obj->count==obj->capticpy;
//}
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
free(obj->array);
obj->count=obj->capticpy=0;
free(obj);
}