纸上得来终觉浅，可以这里看一眼----＞栈和队列（下）_C

括号匹配问题
用两个队列实现栈
用两个栈实现队列
设计循环队列

在上一篇博客里面，我们讲了栈和队列的性质以及栈和队列的模拟实现，那么这两个数据结构的特殊性质有什么应用场景呢？或者更直接一点，面试的时候什么样的OJ题用这两个数据结构处理呢?

那么这篇博客的重点就是面试里一些对栈和队列性质应用考察的OJ题，来帮助读者更好的理解和应用这两个特殊的数据结构，正文开始。

力扣20：有效的括号

力扣

题目的介绍如下：

这道题目就是一道利用栈先进后出性质的经典例题！具体的解题思想如下：

如果是左括号，那么把相应的元素入栈，如果是右括号则取栈顶的元素进行匹配。如果不匹配就返回false,每次匹配完我们都要把栈顶的元素出栈。

根据这样的思想，我们把它转化成代码试一试！注意，由于C语言本身并没有栈这个数据结构，所以我们就把先前写好的栈的代码拷贝到OJ平台上！

typedef char STDataType;
typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);//栈初始化
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//插入
void StackPop(ST* ps);//删除数据
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);//栈的长度
bool StackEmpty(ST* ps);//栈非空的判断
void StackInit(ST* ps)//栈初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//插入
{
	assert(ps);
	ps->a[ps->top] = x;
	ps->top++;
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
}
void StackPop(ST* ps)//删除数据
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)//栈的长度
{
	return ps->top;
}
bool StackEmpty(ST* ps)//栈非空的判断
{
	assert(ps);
	return ps->top == 0;
}
void StackDestory(ST* ps)//销毁栈
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        switch(*s)
        {
            case '(':
            case '{':
            case '[':
            {
                StackPush(&st,*s);
                ++s;
                break;
            }
            case ')':
            case '}':
            case ']':
            {   
                char tmp=StackTop(&st);
                   StackPop(&st);
                if((*s==')'&&tmp!='(')
                || (*s==']'&&tmp!='[')
                ||(*s=='}'&&tmp!='{'))
                {
                    StackDestory(&st);
                    return false;
                }
                else
                {
                    ++s;
                }
                break;
            }
        }
        
    }
    StackDestory(&st);
    return  true;
}

这里就体现出我们在实现代码的时候对存储的数据类型进行typedef的重要性！这里我们所需要的元素是char，所以只要改typedef语句里的类型即可使用！

我们把代码提交，发现并没有通过！到底是哪里出错了呢？分析错误原因也是一个很重要的能力，首先我们第一步是根据测试用例来走读代码，走读分析不来就只能用大招---->把代码拷贝到vs上进行调试！

所以正确的方式应该是：当循环结束的时候，如果不匹配，那么必定是左括号多余（如果中途括号不匹配，直接return false），那么这时候栈就是非空的，返回的是false，而如果栈是空的，那么括号匹配，返回的是true，所以最后我们只需讲empty函数的结果返回即可！

代码改造如下：

typedef char STDataType;
typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);//栈初始化
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//插入
void StackPop(ST* ps);//删除数据
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);//栈的长度
bool StackEmpty(ST* ps);//栈非空的判断
void StackInit(ST* ps)//栈初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//插入
{
	assert(ps);
	ps->a[ps->top] = x;
	ps->top++;
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
}
void StackPop(ST* ps)//删除数据
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)//栈的长度
{
	return ps->top;
}
bool StackEmpty(ST* ps)//栈非空的判断
{
	assert(ps);
	return ps->top == 0;
}
void StackDestory(ST* ps)//销毁栈
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        switch(*s)
        {
            case '(':
            case '{':
            case '[':
            {
                StackPush(&st,*s);
                ++s;
                break;
            }
            case ')':
            case '}':
            case ']':
            {   
                char tmp=StackTop(&st);
                   StackPop(&st);
                if((*s==')'&&tmp!='(')
                || (*s==']'&&tmp!='[')
                ||(*s=='}'&&tmp!='{'))
                {
                    StackDestory(&st);
                    return false;
                }
                else
                {
                    ++s;
                }
                break;
            }
        }
        
    }
   bool ret=StackEmpty(&s);
    StackDestory(&st);
    return ret;
    
}

这次我们总能通过了吧，再次提交代码：

奇怪，为什么还是过不去呢?这里就体现了我们先前加了断言的好处，这里的报错信息明确的之处了top>0断言失败，结合测试用例我们知道，输入只有一个右括号的时候，栈里面没有元素却仍然调用了出栈 *** 作，因此导致断言失败！所以如果字符串还没遍历完成，栈已经空了，那么直接return false! 所以最终的AC代码如下：

typedef char STDataType;
typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);//栈初始化
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//插入
void StackPop(ST* ps);//删除数据
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);//栈的长度
bool StackEmpty(ST* ps);//栈非空的判断
void StackInit(ST* ps)//栈初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->capacity = 4;
	ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//插入
{
	assert(ps);
	ps->a[ps->top] = x;
	ps->top++;
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
}
void StackPop(ST* ps)//删除数据
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)//栈的长度
{
	return ps->top;
}
bool StackEmpty(ST* ps)//栈非空的判断
{
	assert(ps);
	return ps->top == 0;
}
void StackDestory(ST* ps)//销毁栈
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
}
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        switch(*s)
        {
            case '(':
            case '{':
            case '[':
            {
                StackPush(&st,*s);
                ++s;
                break;
            }
            case ')':
            case '}':
            case ']':
            {   if(StackEmpty(&st))
                 {   
                    StackDestory(&st);
                     return false;
                 }                
                char tmp=StackTop(&st);
                   StackPop(&st);
                if((*s==')'&&tmp!='(')
                || (*s==']'&&tmp!='[')
                ||(*s=='}'&&tmp!='{'))
                {
                    StackDestory(&st);
                    return false;
                }
                else
                {
                    ++s;
                }
                break;
            }
        }
        
    }
    bool ret=StackEmpty(&st);
    StackDestory(&st);
    return ret;
}

注意：OJ题不会检查内存泄露的问题，但在实际的开发环境里，内存泄露问题的后果是十分严重的！所以在返回结果之前，我们调用Destroy函数回收内存，这点非常重要！

通过这道OJ题，相信你对栈的了解会更加深刻，那么接下来面试官又向你提出了一个问题：如何用两个队列实现栈？没错，就是用两个队列实现栈，对应的题目如下：

用两个队列实现栈：

https://leetcode-cn.com/problems/implement-stack-using-queues/

那么这道题目就很好的考察了你对栈和队列性质的理解以及对代码的控制能力。那么我们的具体执行的思路如下：

队列先进先出，栈是先进后出，那么我们有两个队列q1,q2,入数据就是指定一个队列进行入数据，那么出数据应该怎么出呢？同理取栈顶元素应该怎么取呢？通过如下的图片我们来分析：

那么AC代码如下：

//链表实现队列
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;//队头指针
	QNode* tail;//队尾指针
}Queue;
//队列初始化
void QueueInit(Queue* pq);
//队列释放
void QueueDestroy(Queue* pq);
//队列插入数据
void QueuePush(Queue* pq, QDataType x);
//队列出数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
//队列大小
size_t QueueSize(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//删除数据(队头出数据)
void QueuePop(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
//队列释放
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
//队尾插入数据
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (NULL == newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{  
		newnode->val = x;
		newnode->next = NULL;
		if (NULL == pq->tail )
		{   
			assert(NULL==pq->head);
			pq->head = pq->tail = newnode;
		}
		else
		{
			pq->tail->next = newnode;
			pq->tail = newnode;
		}
	}
}
//队头和队尾都可以取数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->val;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	assert(pq->tail);
	return pq->tail->val;
}
//队列大小
size_t QueueSize(Queue* pq)
{
	assert(pq);
	size_t size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}
//队头出节点
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
typedef struct {
  Queue q1;
  Queue q2;
} MyStack;


MyStack* myStackCreate() {
   MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
   assert(obj);
   QueueInit(&obj->q1);
   QueueInit(&obj->q2);
   return obj;
}

void myStackPush(MyStack* obj, int x) {
    //每次都只往非空的队列入数据
   if(!QueueEmpty(&obj->q1))
      QueuePush(&obj->q1,x);
    else
      QueuePush(&obj->q2,x);  
}
int myStackPop(MyStack* obj) {
    //使用EmptyQ,NoneEmptyWQ来标识空队列和非空队列
   //默认q1为空，q2非空 
    Queue* EmptyQ=&obj->q1;
    Queue* NoneEmptyQ=&obj->q2;
    //假设错误，重置一下
   if(!QueueEmpty(&obj->q1))
   {
       NoneEmptyQ=&obj->q1;
       EmptyQ=&obj->q2;
   }
   //讲NoneEmptyQ的数据入到EmptyQ里去
   while(QueueSize(NoneEmptyQ)>1)
   {
       QueuePush(EmptyQ,QueueFront(NoneEmptyQ));
       QueuePop(NoneEmptyQ);
   }
   //取数据
   int top=QueueFront(NoneEmptyQ);
   //删除
   QueuePop(NoneEmptyQ);
   return top;
}

int myStackTop(MyStack* obj) {
    //队列可以取队尾的数据，所以直接返回非空的队尾即可
    if(!QueueEmpty(&obj->q1))
       return QueueBack(&obj->q1);
    return QueueBack(&obj->q2);   
}

bool myStackEmpty(MyStack* obj) {
  return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
   QueueDestroy(&obj->q1);
   QueueDestroy(&obj->q2);
   free(obj);
}

注意最后一个Free函数也有细节，我们把这个栈的结构画出来

所以我们在释放obj之前，我们要先对释放里面的两个队列，最后才能释放obj!

讲完了用队列实现栈，接下来不妨来看看怎么用栈实现队列

用栈实现队列：

https://leetcode-cn.com/problems/implement-queue-using-stacks/

那么相对于使用队列来实现栈，用栈来实现队列则相对简单的多，我们只需要在一个栈里入数据，这个栈记为pushst，另外一个负责出数据的叫做popst，删除或者是取队头的数据只需要把pushst的数据入到popst里去，然后对popst调用pop或top即可！

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	size_t top;//栈顶指针
	size_t capacity;//容量
}Stack;
//初始化
void StackInit(Stack* ps);
//释放
void StackDestroy(Stack* ps);
//插入
void StackPush(Stack* ps, STDataType x);
//删除
void StackPop(Stack* ps);
//取栈顶数据
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//获取栈元素的个数
size_t StackSize(Stack* ps);
//初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
//释放
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
//插入
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		size_t newCapacity = ps->capacity == 0 ? 2 : ps->capacity * 2;
		STDataType* tmp= (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	ps->a[ps->top++] = x;
}
//删除
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
	
}
//取栈顶数据
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
//获取栈元素的个数
size_t StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

typedef struct {
  Stack pushst;
  Stack popst;
} MyQueue;


MyQueue* myQueueCreate() {
   MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
   assert(obj);
   StackInit(&obj->pushst);
   StackInit(&obj->popst);
   return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    //往pushst入数据
  StackPush(&obj->pushst,x);
}

int myQueuePop(MyQueue* obj) {
    //如果popst没有数据，那么就要把pushst的数据入到popst中去
  if(StackEmpty(&obj->popst))
  {
      while(!StackEmpty(&obj->pushst))
      {
          StackPush(&obj->popst,StackTop(&obj->pushst));
          StackPop(&obj->pushst);
      }
      int top=StackTop(&obj->popst);
      StackPop(&obj->popst);
      return top;
  }
  //走到这里,popst不是空，直接返回popst栈顶的数据
      int top=StackTop(&obj->popst);
      StackPop(&obj->popst);
      return top;
}

int myQueuePeek(MyQueue* obj) {
    //和pop一样的思想，只是不用删除元素
  if(StackEmpty(&obj->popst))
  {
      while(!StackEmpty(&obj->pushst))
      {
          StackPush(&obj->popst,StackTop(&obj->pushst));
          StackPop(&obj->pushst);
      }
      int top=StackTop(&obj->popst);
      return top;
  }
      int top=StackTop(&obj->popst);
      return top;
}

bool myQueueEmpty(MyQueue* obj) {
    //两个都是空才为空
  return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}

void myQueueFree(MyQueue* obj) {
  StackDestroy(&obj->pushst);
  StackDestroy(&obj->popst);
  free(obj);
}

完成了这两道题，接下来我们再看一个特殊的队列：循环队列，这个队列的特殊之处在于，队列开辟的空间是固定的，也就是说接下来的所有的数据都只能利用这有限个的空间。就好比说教室的座位一样，一间教室的座位的数量都是固定的，只能轮流者给上课的班级的同学使用一样！

假设现在有一个可存放k个数据的循环队列，front指向队头，rear指向队尾元素的下一个位置，当front==rear的时候，那么循环队列就是空的，那么队列什么时候满的时候front和rear的关系又是怎么样的呢？

设计循环队列

那么实现循环队列可以使用数组的方式也可以用链表的方式实现，但是因为链表查找前一个节点不太方便，所以这里我们使用数shi

typedef struct {
  int* a;
  int front;
  int rear;
  int k
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    //返回的地址必须是malloc的
  MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  assert(obj);
  //申请长度为k+1的数组
  obj->a=(int*)malloc(sizeof(int)*(k+1));
  assert(obj->a);
  //front指向当前元素，rear指向当前元素的下一个
  obj->front=obj->rear=0;
  obj->k=k;
  return obj;
}
//前向声明告诉编译器有这个函数
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //满队列不入数据
   if(myCircularQueueIsFull(obj)) 
      return false;
      //刚好到多申请的节点，放数据rear置0
     if(obj->rear==obj->k)
     {   obj->a[obj->rear]=value;
         obj->rear=0;
     }
     else
     { //放数据
        obj->a[obj->rear++]=value;
     }      
     return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
 if(myCircularQueueIsEmpty(obj))
    return false;
    if(obj->front==obj->k)
    {
        obj->front=0;
    }
    else
    {
       obj->front++;
    }  
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
   if(myCircularQueueIsEmpty(obj))
      return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
  if(myCircularQueueIsEmpty(obj))
    return -1;
  if(obj->rear==0)
    return obj->a[obj->k];
    return obj->a[obj->rear-1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  return obj->front==obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
   if(obj->rear==obj->k && obj->front==0)
     return true;
 return obj->rear+1==obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
  free(obj->a);
  free(obj);
}

实现了循环队列，我们再来看一道选择题：

那么这道题很多都是字母很抽象，我们可以举一个具体的值来分析，假设N=5

但是如果rear>front的时候，rear+n-front太大，所以最终我们对N取模，这样第一种情况就和第二种情况相同！所以最终的答案就是（rear-front+N）%N

结语：

本篇博客旨在通过OJ题目加深读者对栈和队列性质有一个更好的理解，希望不足之处还望指出.

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/676037.html

纸上得来终觉浅，可以这里看一眼----＞栈和队列（下）

发表评论

评论列表（0条）