数据结构-->用队列实现栈（OJ_01）

各位老友，欢迎造访本期博客！！

前段时间，我们已经学习了，怎样实现栈区，队列！

今天，正是我们将前段时间学习的知识，进行迁移！！

奥！银河啊！！这句“知识的迁移”勾起了，我的高中物理课···

OJ_01 :>

1.请仅使用两个队列实现一个后进先出的栈，并支持普通的栈的全部四种操作（push, pop, top, destroy）

请看以下代码

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
  QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
  QNode* tail;
  int size;
}Queue;

//队列初始化
void QInitial(Queue* pq);

//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq);

//出队列
void QPop(Queue* pq);

//队列头部元素
QDataType QFront(Queue* pq);

//队列尾部元素
QDataType QBack(Queue* pq);

//队列元素个数
QDataType QSize(Queue* pq);

//布尔判空
void QEmpty(Queue* pq);

//队列初始化
void QInitial(Queue* pq)
{
	assert(pq);
  QEmpty(pq);
  pq ->head = pq ->tail = NULL;
  pq ->size = 0;
}

//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
  QEmpty(pq);
  Queue* cur = pq ->head;
  
  while(cur)
  {
  	Queue* next = pq ->head ->next;
    free(pq);
    pq ->head = next;
  }
  pq ->head = NULL;
}

//入队列
void QPush(Queue* pq)
{
	Queue* newnode = (Queue*)malloc(sizeof(Queue));
  if(newnode == NULL)
  {
    perror("malloc::fail");
    return ;
  }
  newnode ->data = x;
  newnode ->next = NULL;
  
  if(pq ->head = NULL)
  {
  	assert(pq ->tail == NULL);
    pq ->head = pq ->tail = NULL;
  }
  else
  {
  	pq ->tail ->next = newnode;
    pq ->tail = newnode;
  }
  
  pq ->size++;
}

//出队列
void QPop(Queue* pq)
{
	assert(pq);
  QEmpty(pq);
  if(pq ->head ->next == NULL)
  {
  	free(pq ->head);
    pq ->head = NULL;
  }
  else
  {
  	Queue* next = pq ->head ->next;
    free(pq ->head);
    pq ->head = next;
  }
  pq ->size--;
}

//队列头部元素
QDataType QFront(Queue* pq)
{
	assert(pq);
  QEmpty(pq);
  return pq ->head ->data;
}

//队列尾部元素
QDataType QBack(Queue* pq)
{
	assert(pq);
  QEmpty(pq);
  return pq ->tail ->data;
}

//队列元素个数
QDataType QSize(Queue* pq)
{
	assert(pq);
  return pq ->size;
}
//布尔判空
void QEmpty(Queue* pq)
{
	assert(pq);
  return pq ->size == 0;
}

//开始实现用队列实现栈

//匿名结构体
typedef struct
{
	Queue q1;
  Queue q2;
}MYStack;

//创建栈
MYStack* mystackCreate()
{
	MyStack* pst = (MYStack*)malloc(sizeof(MYStack));
  if(pst == NULL)
  {
  	perror("malloc::fail");
    return NULL;
  }
  QInitial(&pst ->q1);
  QInitial(&pst ->q2);
  
  return pst;
}

//入栈
void mystackPush(MYStack* obj, int x)
{
	if(!QEmpty(&obj ->q1))
  {
  		QPush(&obj ->q1, x);
  }
  else
  {
  	QPush(&obj ->q2, x);
  }
}

//出栈并且返回栈顶元素
int mystackPop(MYStack* obj)
{
	MYStack* emptyQ = &obj ->q1;
  MYStack* nonemptyQ = &obj ->q2;
  if(QEmpty(&obj ->q1))
  {
  	emptyQ = &obj ->q2;
    nonemptyQ = &obj ->q1;
  }
  
  //倒数据--->这部分才是核心
  while(QSzie(nonemptyQ) > 1)
  {
  	QPush(emptyQ, QFront(nonemptyQ));
    QPop(nonemptyQ);
  }
  
  int top = QFront(nonemptyQ);
  QPop(nonemptyQ);
  return top;
}

//栈顶元素
int mystackTop(MYStack* obj)
{
	if(!QEmpty(&obj ->q1))
  {
  		return QBack(&obj ->q1);
  }
  else
  {
  		return QBack(&obj ->q2);
  }
}

//销毁
void mystackFree(MYStack* obj)
{
	QDestroy(&obj ->q1);
	QDestroy(&obj ->q2);
  
  free(obj);
}

至此，我们的代码已书写完毕！！为了各位好友，方便观看，特此附上带有色彩图样的代码，毕竟观感好啊！！