C语言栈与队列面试题详解_C 语言

//创建栈结构  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);  //判空  bool StackEmpty(ST* ps);  //访问栈顶数据  STDataType StackTop(ST* ps);  //有效元素个数  int StackSize(ST* ps);     //定义：  //初始化栈  void StackInit(ST* ps)  {  	assert(ps);  	ps->a = NULL;  	ps->top = 0;  	ps->capacity = 0;  }  //销毁栈  void StackDestory(ST* ps)  {  	assert(ps);  	free(ps->a);  	ps->a = NULL;  	ps->capacity = ps->top = 0;  }  //压栈  void StackPush(ST* ps, STDataType x)  {  	assert(ps);  	//如果栈满了，考虑扩容  	if (ps->top == ps->capacity)  	{  		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量  		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));  		if (ps->a == NULL)  		{  			printf("realloc fail\n");  			exit(-1);  		}  		ps->capacity = newcapacity; //更新容量  	}  	ps->a[ps->top] = x;//将数据压进去  	ps->top++;//栈顶上移  }  //出栈  void StackPop(ST* ps)  {  	assert(ps);  	assert(ps->top > 0);  	ps->top--;  }  //判空  bool StackEmpty(ST* ps)  {  	assert(ps);  	return ps->top == 0; //如果top为0，那么就为真，即返回  }  //访问栈顶数据  STDataType StackTop(ST* ps)  {  	assert(ps);  	assert(ps->top > 0);  	return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素  }  //有效元素个数  int StackSize(ST* ps)  {  	assert(ps);  	return ps->top;  }     //创建好了栈开始实现  bool isValid(char* s) {      ST st;//先创建一个栈      StackInit(&st);//初始化栈      while (*s)      {          if (*s == '[' || *s == '(' || *s == '{')          {              StackPush(&st, *s); //如果是左括号就入栈              ++s;          }          else          {              if (StackEmpty(&st))              {                  return false; //此处说明前面根本没有左括号，导致栈为空，直接返回false              }              char top = StackTop(&st); //获取栈顶元素              StackPop(&st); //出栈顶元素，接下来进行匹配              if ((*s == ']' && top != '[')                  || (*s == ')' && top != '(')                  || (*s == '}' && top != '{'))              {                  StackDestory(&st); //返回前先销毁，防止内存泄漏                  return false; //如果不匹配，直接返回false              }              else              {                  //此时匹配，继续比较，直到遍历结束                  ++s;              }          }      }      //栈为空，说明所有左括号都匹配      bool ret = StackEmpty(&st);      StackDestory(&st); //返回前先销毁，防止内存泄漏      return ret;  }

//创建队列结构  typedef int QDataType; //方便后续更改存储数据类型，本文以int为例   //创建队列节点  typedef struct QueueNode  {  	QDataType data; //存储数据  	struct QueueNode* next; //记录下一个节点  }QNode;  //保存队头和队尾  typedef struct Queue  {  	QNode* head; //头指针  	QNode* tail; //尾指针  }Queue;  //初始化队列  void QueueInit(Queue* pq);  //销毁队列  void QueueDestory(Queue* pq);  //入队列  void QueuePush(Queue* pq, QDataType x);  //出队列  void QueuePop(Queue* pq);  //判空  bool QueueEmpty(Queue* pq);  //获取有效元素个数  size_t QueueSize(Queue* pq);  //获取队头元素  QDataType QueueFront(Queue* pq);  //获取队尾元素  QDataType QueueBack(Queue* pq);     //定义：  //初始化队列  void QueueInit(Queue* pq)  {  	assert(pq);  	pq->head = pq->tail = NULL;  }  //销毁队列  void QueueDestory(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));  	//暴力检测newnode，因为malloc的都要检测  	assert(newnode);  	newnode->next = NULL;  	newnode->data = x;  	//如果一开始没有数据，为空的情况  	if (pq->tail == NULL)  	{  		assert(pq->head == NULL);  		pq->head = pq->tail = newnode;  	}  	else  	{  		pq->tail->next = newnode;  		pq->tail = newnode;  	}  }  //出队列  void QueuePop(Queue* pq)  {  	assert(pq);  	assert(pq->head && pq->tail); //tail和head均不能为空  	//特殊：当删到head=tail的位置时  	if (pq->head->next == NULL)  	{  		free(pq->head);  		pq->head = pq->tail = NULL;  	}  	//一般情况  	else  	{  		//保存head的下一个节点  		QNode* next = pq->head->next;  		free(pq->head);  		pq->head = next;  	}  }  //判空  bool QueueEmpty(Queue* pq)  {  	assert(pq);  	return pq->head == NULL;  }  //获取有效元素个数  size_t QueueSize(Queue* pq)  {  	assert(pq);  	QNode* cur = pq->head;  	size_t size = 0;  	while (cur)  	{  		size++;  		cur = cur->next;  	}  	return size;  }  //获取队头元素  QDataType QueueFront(Queue* pq)  {  	assert(pq);  	assert(pq->head); //头部不能为空  	return pq->head->data;  }  //获取队尾元素  QDataType QueueBack(Queue* pq)  {  	assert(pq);  	assert(pq->tail); //尾部不能为空  	return pq->tail->data;  }     /**************创建好队列结构，开始正文模拟实现栈**************/  typedef struct {  	Queue q1; //队列q1  	Queue q2; //队列q2  } MyStack;        MyStack* myStackCreate() {  	MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); //申请一个MyStack类型的栈  	assert(pst);  	QueueInit(&pst->q1);//初始化队列1  	QueueInit(&pst->q2);//初始化队列2  	return pst;  }     void myStackPush(MyStack* obj, int x) {  	assert(obj);  	if (!QueueEmpty(&obj->q1))  	{  		QueuePush(&obj->q1, x);//如果q1不为空，就往q1插入数据  	}  	else  	{  		QueuePush(&obj->q2, x);//这儿不需要知道q2是否为空，直接push  	}  }     int myStackPop(MyStack* obj) {  	assert(obj);  	Queue* emptyQ = &obj->q1; //默认q1为空  	Queue* nonEmtpyQ = &obj->q2;//默认q2不为空  	if (!QueueEmpty(&obj->q1))  	{  		emptyQ = &obj->q2; //若假设错误，则q2为空  		nonEmtpyQ = &obj->q1;//此时q1就为空  	}  	while (QueueSize(nonEmtpyQ) > 1)  	{  		QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的队列数据导到空的队列，直到只剩一个  		QueuePop(nonEmtpyQ); //此时把非空的队头数据给删掉，方便后续导入数据  	}  	int top = QueueFront(nonEmtpyQ); //记录此时的栈顶数据  	QueuePop(nonEmtpyQ); //删除栈顶数据，使该队列置空  	return top;  }     int myStackTop(MyStack* obj) {  	assert(obj);  	if (!QueueEmpty(&obj->q1))  	{  		return QueueBack(&obj->q1);//如果q1不为空，返回  	}  	else  	{  		return QueueBack(&obj->q2);  	}  }     bool myStackEmpty(MyStack* obj) {  	assert(obj);  	//两个队列均为空，则为空  	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);  }     void myStackFree(MyStack* obj) {  	assert(obj);  	QueueDestory(&obj->q1); //释放q1  	QueueDestory(&obj->q2); //释放q2  	free(obj);  }

//创建栈结构  typedef int 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);  //判空  bool StackEmpty(ST* ps);  //访问栈顶数据  STDataType StackTop(ST* ps);  //有效元素个数  int StackSize(ST* ps);     //初始化栈  void StackInit(ST* ps)  {      assert(ps);      ps->a = NULL;      ps->top = 0;      ps->capacity = 0;  }  //销毁栈  void StackDestory(ST* ps)  {      assert(ps);      free(ps->a);      ps->a = NULL;      ps->capacity = ps->top = 0;  }  //压栈  void StackPush(ST* ps, STDataType x)  {      assert(ps);      //如果栈满了，考虑扩容      if (ps->top == ps->capacity)      {          int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; //检测容量          ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));          if (ps->a == NULL)          {              printf("realloc fail\n");              exit(-1);          }          ps->capacity = newcapacity; //更新容量      }      ps->a[ps->top] = x;//将数据压进去      ps->top++;//栈顶上移  }  //出栈  void StackPop(ST* ps)  {      assert(ps);      assert(ps->top > 0);      ps->top--;  }  //判空  bool StackEmpty(ST* ps)  {      assert(ps);      return ps->top == 0; //如果top为0，那么就为真，即返回  }  //访问栈顶数据  STDataType StackTop(ST* ps)  {      assert(ps);      assert(ps->top > 0);      return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素  }  //有效元素个数  int StackSize(ST* ps)  {      assert(ps);      return ps->top;  }     /************创建好栈结构，开始正文************/  typedef struct {      ST pushST; //插入数据的栈      ST popST; //删除数据的栈  } MyQueue;        MyQueue* myQueueCreate() {      MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申请队列类型      assert(obj);      StackInit(&obj->pushST);//初始化pushST      StackInit(&obj->popST);//初始化popST      return obj;  }     void myQueuePush(MyQueue* obj, int x) {      assert(obj);      StackPush(&obj->pushST, x);//不管有没有数据，都插入  }     int myQueuePop(MyQueue* obj) {      assert(obj);      if (StackEmpty(&obj->popST)) //如果popST数据为空，要从pushST里导入数据才能删除      {          while (!StackEmpty(&obj->pushST)) //pushST数据不为空，就一直向popST里导入数据          {              StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里              StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉，方便后续继续导          }      }      int front = StackTop(&obj->popST); //记录popST栈顶元素      StackPop(&obj->popST);//删除popST栈顶元素，实现队列先进先出      return front; //返回栈顶数据  }     //取队头数据  int myQueuePeek(MyQueue* obj) {      assert(obj);      //如果popST数据为空，要从pushST里导入数据才能取到队头数据      if (StackEmpty(&obj->popST))      {          while (!StackEmpty(&obj->pushST)) //pushST数据不为空，就一直向popST里导入数据          {              StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST栈顶数据导到popST里              StackPop(&obj->pushST);//导完后把pushST栈顶元素删掉，方便后续继续导          }      }      return StackTop(&obj->popST);//直接返回栈顶元素  }     bool myQueueEmpty(MyQueue* obj) {      return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);  }     void myQueueFree(MyQueue* obj) {      assert(obj);      StackDestory(&obj->pushST);      StackDestory(&obj->popST);      free(obj);  }

typedef struct {      int* a; //用数组模拟环形队列      int front;//队头      int tail; //队尾      int k; //表示存的数据长度为k  } MyCircularQueue;     bool myCircularQueueIsFull(MyCircularQueue* obj); //前置声明  bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置声明     MyCircularQueue* myCircularQueueCreate(int k) {      MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建环形链表结构      assert(obj);      obj->a = (int*)malloc(sizeof(int) * (k + 1));//多开一个空间，便于后续区分空或满      obj->front = obj->tail = 0;      obj->k = k; //队列存储有效数据长度为k      return obj;  }     bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {      if (myCircularQueueIsFull(obj))      {          return false; //队列已满，不能插入数据      }      obj->a[obj->tail] = value; //赋值      if (obj->tail == obj->k)      {          obj->tail = 0; //当tail走到尾端      }      else      {          obj->tail++;      }      return true;  }     bool myCircularQueueDeQueue(MyCircularQueue* obj) {      if (myCircularQueueIsEmpty(obj))      {          return false; //队列为空，不能删除      }      if (obj->front == obj->k)      {          obj->front = 0; //当front走到尾端      }      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->tail == 0)      {          return obj->a[obj->k]; //tail为0，队尾在长度的最后一个位置      }      else      {          return obj->a[obj->tail - 1];      }  }     bool myCircularQueueIsEmpty(MyCircularQueue* obj) {      return obj->front == obj->tail; //front==tail时为空  }     bool myCircularQueueIsFull(MyCircularQueue* obj) {      if (obj->tail == obj->k && obj->front == 0)      {          return true; //当tail尾端，front在头端时也是满      }      else      {          return obj->tail + 1 == obj->front; //一般情况，当tail的下一个位置为front时为满      }  }     void myCircularQueueFree(MyCircularQueue* obj) {      free(obj->a);      free(obj);  }