数据结构——3道栈和队列OJ题(上）

2022-12-09 95

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 笔记

习题1 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

1.把有数据队列的内容，传到没数据的队列中，传一个之后，再原队列中删一个

2.等q1中剩一个元素的时候，让这个元素出队

这样就可以达到栈的效果，1，2，3，4，5，让5先出栈，之后再按照同样的方法把q1看作空（压栈的时候要往有元素的队里压），开始倒数据即可

队列的实现

typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode *head;
  QNode* tail;
  size_t size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue *pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
  QNode* del = cur;
  cur = cur->next;
  free(del);
  del = NULL;
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = pq->tail->next;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }//如果只剩一个节点，单独处理，防止tail变为野指针
  else
  {
  QNode* cur = pq->head;
  pq->head = pq->head->next;
  free(cur);
  cur = NULL;
  }
  pq->size--;
}
QDataType QueueFront(Queue* pq)//取头数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)//取尾数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head==NULL && pq->tail==NULL;
}
int QueueSize(Queue* pq)
{
  return pq->size;
}

通过队列实现栈

结构体的建立

typedef struct {
Queue q1; //建立俩个
Queue q2;
} MyStack;
//也可用Queue*，但是这样的话要用malloc给q1和q2开辟空间

初始化

MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
     QueueInit(&obj->q1);
      QueueInit(&obj->q2);
      return obj;
}//直接传参即可

压栈

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }//如果q1不是空，把元素压到q1
    else
    {
         QueuePush(&obj->q2,x);
    }
}

出栈

int myStackPop(MyStack* obj) {
   Queue *empty=&obj->q1;//假设q1为空
    Queue *noempty=&obj->q2;//假设q2不是空
    if(!QueueEmpty(&obj->q1))
    {
        noempty=&obj->q1;
        empty=&obj->q2;
 while(QueueSize(noempty)>1)         //将有元素的队列的数据，倒到只剩最后一个元素
 {
     QueuePush(empty,QueueFront(noempty));
     QueuePop(noempty);
 }
int top=QueueFront(noempty);//该元素就是栈顶
QueuePop(noempty);
return top;//返回栈顶
}

返回栈顶
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{ 
   return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}//直接调用返回队尾的函数即可

判断是否为空

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

销毁空间

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

这里不能直接free(obj)，因为q1和q2是链表，链表的内存不连续，如果释放掉boj,则q1和q2没有释放，会造成内存泄漏

用队列实现栈

232. 用栈实现队列 - 力扣（LeetCode）

若队列中是1 2 3 4 5，则按照栈的规则，此时出栈顺序应该是 5 4 3 2 1，我们可以用俩个队列来实现栈

1.把PushST里面的数据倒到PopST

2.出栈的时候，我们只需要出PopST里面的元素就可以，当有元素要填充时，填充到PushST就行

栈的实现

typedef int STDdtaTtype;
typedef struct Stcak
{
  STDdtaTtype* data;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDdtaTtype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDdtaTtype StackTop(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->data = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->data);
  ps->capacity = ps->top = 0;
  ps->data = NULL;
}
void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
  assert(ps);
  int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  if (ps->capacity == ps->top)//判断是否满了
  {
  STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    exit(-1);
  }
  ps->data = tmp;
  ps->capacity = newcapacity;
  }
  ps->data[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDdtaTtype StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->data[ps->top - 1];
}
bool StackEmpty(ST* ps)//判断是否为空栈
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

结构体创建

typedef struct {
ST PushST;
ST PopST;
} MyQueue;

结构体的初始化

MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->PushST);
StackInit(&obj->PopST);
return obj;
}