Realize queue with stack and stack with queue (C language \leetcode\u 232+225)

Stack and queue were implemented two days ago , Now do two classic examples to consolidate your knowledge .

Topic link ：

232. Using stack to realize queue - Power button （LeetCode）

225. Using queue to implement stack - Power button （LeetCode）

Catalog

One 、 Using stack to realize queue

Two 、 Using queue to implement stack

  3、 ... and 、 Source code

3.1 Stack --> queue   Source code

3.2 queue --> Stack   Source code

---

One 、 Using stack to realize queue

Ideas ：

① Build two stacks to realize the queue . A stack is input Stack , Only save data ; A stack is output Stack , Only responsible for data .

② When data comes out , First judge output Is the stack empty (StackEmpty(&output)), If it is empty , To put input Data in the stack Import all into output In the stack , And then there's output Top element of stack , Delete one more output Data in the stack .

At this time, let's analyze why output Data is inverted only when it is empty .

Pay attention ！ The stack is First in, then out Oh ！ Only when output Data can only be inverted when it is empty , If not, then the inserted data will disrupt the order of the stack .

Because we're using C Language to do this problem , We need to create our own stack , This is more troublesome , Fortunately, we implemented a stack two days ago , It can be used directly .

The source code is long , I put it at the end , You can jump through the directory .

---

Two 、 Using queue to implement stack

Ideas ：

① A queue holds the input data , A queue is exclusively empty , It is used to save data when exporting data . The two queues will switch functions every time they send data .

② When exporting data , To import the data in the queue storing data into the empty queue , Until only one data is left . Then output this data , If it is Pop type , After output, delete the data , If it is Top type , Then the data is output and inserted into the inverted data queue .

step ：

One 、 insert data

If q1 It's empty , be q1 It is a queue for reversing data , So put q2, vice versa ,q2 Insert for empty data q1.

Two 、 Take the data

1. Import all the remaining data except the last data into the inverted data queue , Then output the last data left .

2. If the requirement is Pop type , After output, delete the data ; If it is Top type , Then the data is output and inserted into the inverted data queue .

 

---

3、 ... and 、 Source code

because C Languages do not have libraries of these structures , We can only rub out the stack and queue by hand , Fortunately, we implemented stack and queue two days ago , At this time, we can copy it directly and apply it , So there is a little more code .

3.1 Stack --> queue   Source code

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

typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;			// Identify the data at the top of the stack 
	int capacity;		// Dynamic   Capacity expansion 
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDateType x);
void StackPop(ST* ps);
STDateType StackTop(ST* ps);	// Take the element at the top of the stack 
bool StackEmpty(ST* ps);		// Judge whether the stack is empty 
int StackSize(ST* ps);			// Know the stack size 



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->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* temp = (STDateType * )realloc(ps->a, sizeof(STDateType) * NewCapacity);
		if (temp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = NewCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[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 input;          //input Stack 
    ST output;         //output Stack 
} MyQueue;

// Create the queue   And back to 
MyQueue* myQueueCreate() {
      // Open up a space for structural variables 
      // Represents the structure we created ourselves   MyQueue
      MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue));
      // Be careful , Creating a MyQueue in , We created a stack , If we call a function of the stack , It is necessary to pass the address of the stack into the function to conform to its type 
      StackInit(&obj->input);
      StackInit(&obj->output);
      return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    // Put data into input Stack 
    StackPush(&obj->input,x);
}

int myQueuePop(MyQueue* obj) {
    // Pop up the data 
    // If output empty , It indicates that the data stack is empty , Import data 
    if(StackEmpty(&obj->output))
    {
        // until input It's empty 
        while(!StackEmpty(&obj->input))
        {
            // take input Data into output
            // Insert a   Pop One 
            StackPush(&obj->output,StackTop(&obj->input));
            StackPop(&obj->input);
        }
    }
    int ret=StackTop(&obj->output);
    StackPop(&obj->output);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    // Two stacks are empty , That is, the queue is empty 
    return (StackEmpty(&obj->input)&& StackEmpty(&obj->output));
}

int myQueuePeek(MyQueue* obj) {
    // If the queue is empty 
    if (myQueueEmpty(obj))
    {
        return -1;
    }
    if(StackEmpty(&obj->output))
    {
        while(!StackEmpty(&obj->input))
        {
            // take input Data into output
            StackPush(&obj->output,StackTop(&obj->input));
            StackPop(&obj->input);
        }
    }
    return StackTop(&obj->output);
}



void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->input);
    StackDestory(&obj->output);
    free(obj);
}

3.2 queue --> Stack   Source code

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


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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* Dest = pq->head;
	while (Dest)
	{
		QNode* temp = Dest->next;
		free(Dest);
		Dest = temp;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	// Create a node 
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	// Judge pq Is it an empty node 
	// If it is   Will newnode Set as the first node of the current queue 
	// If not    Will newnode link to pq Next position of 
	if (pq->tail == NULL)
	{   // Both nodes point to newnode  Indicates that there is only one element in the queue 
		pq->head = pq->tail = newnode;
	}
	else 
	{
		//1. take newnode link to tail Behind 
		pq->tail->next = newnode;
		//2. take newnode Replace with new tail
		pq->tail = newnode;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	// Make an extra judgment , Solve if there is only one node left ,pop Words lead to tail For the wild pointer 
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
QDataType QueueBck(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail ->data;
}

int QueueSize(Queue *pq)
{
	assert(pq);
	int count = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}


typedef struct {
    Queue q1;     // queue 1
    Queue q2;     // queue 2
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL)
    {
        return 0;
    }
    // Initialize these two queues 
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

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


void myStackPush(MyStack* obj, int x) {
    // If q1 It's empty , Then go q2 Put data in 
    if (QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2, x);
    }
    else
    {
        QueuePush(&obj->q1, x);
    }
}

int myStackPop(MyStack* obj) {
    // If q1 It's empty , It's from q2 Go to q1 Inside guide data 
    if (QueueEmpty(&obj->q1))
    {
        while (!((&obj->q2)->head->next == NULL))
        {
            QueuePush(&obj->q1, QueueFront(&obj->q2));
            QueuePop(&obj->q2);
        }
        int ret = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        return ret;
    }
    else
    {
        while (!((&obj->q1)->head->next == NULL))
        {
            QueuePush(&obj->q2, QueueFront(&obj->q1));
            QueuePop(&obj->q1);
        }
        int ret = QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        return ret;
    }
}

int myStackTop(MyStack* obj) {
    // If q1 It's empty , Is the location where the data except the top of the stack is stored 
    if (QueueEmpty(&obj->q1))
    {
        while (!((&obj->q2)->head->next == NULL))
        {
            QueuePush(&obj->q1, QueueFront(&obj->q2));
            QueuePop(&obj->q2);
        }
        int ret = QueueFront(&obj->q2);
        QueuePush(&obj->q1,ret);
        QueuePop(&obj->q2);
        return ret;
    }
    else
    {
        while (!((&obj->q1)->head->next == NULL))
        {
            QueuePush(&obj->q2, QueueFront(&obj->q1));
            QueuePop(&obj->q1);
        }
        int ret = QueueFront(&obj->q1);
        QueuePush(&obj->q2,ret);
        QueuePop(&obj->q1);
        return ret;
    }
}

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