1. Use stack to implement queue
Design idea: Create two stacks, one is the enqueuing stack and the other is the dequeuing stack. When it is necessary to enter the queue, it is inserted to the end of the queue stack. When it is necessary to dequeue, it is necessary to determine whether the queue stack is empty. If it is empty, the elements of the queue stack need to be transferred to the queue stack.
Enqueue stack:
| 1 | 2 | 3 | 4 |
Dequeue stack:
According to the last-in-first-out principle of the stack and the first-in-first-out principle of the queue, if the queue is implemented through the stack, the bottom 1 in the stack needs to be popped. Then you need to store the enqueuing stack into the dequeuing stack according to the last-in-first-out principle of the stack, and then pop the top element of the stack.
The basic functional function code of the queue implemented through the stack is completed based on the original stack implementation code. The code is as follows:
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STdata;
//Declare the structure of the stack
typedef struct Stack
{
STdata* data;
int top;
int capacity;
}Stack;
//Initialize stack
void STInit(Stack* pst);
//Destroy the stack
void STDestory(Stack* pst);
//Short call
bool STEmpty(Stack* pst);
//Push to stack
void STPush(Stack* pst, STdata x);
//pop
void STPop(Stack* pst);
//Get the top element of the stack
STdata STTop(Stack* pst);
//Get the number of elements in the stack
int STSize(Stack* pst);
//Initialization implementation of stack
void STInit(Stack* pst)
{
assert(pst);
pst->data = NULL;
pst->top = 0;
pst->capacity = 0;
}
//Push implementation
void STPush(Stack* pst, STdata x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity + 4;
STdata* tmp = (STdata*)realloc(pst->data, sizeof(STdata) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->data = tmp;
pst->capacity = newcapacity;
}
pst->data[pst->top] = x;
pst->top + + ;
}
//Destroy stack implementation
void STDestory(Stack* pst)
{
assert(pst);
free(pst->data);
pst->data = NULL;
pst->top = 0;
pst->capacity = 0;
}
//Short call
bool STEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//pop
void STPop(Stack* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
//Get the top element of the stack
STdata STTop(Stack* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->data[pst->top - 1];
}
//Get the number of elements in the stack
int STSize(Stack* pst)
{
assert(pst);
return pst->top;
}
typedef struct {
Stack pushstack;
Stack popstack;
}MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
{
perror("malloc fail");
return NULL;
}
STInit( & amp;obj->pushstack);
STInit( & amp;obj->popstack);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush( & amp;obj->pushstack,x);
}
int myQueuePop(MyQueue* obj) {
int front=myQueuePeek(obj);
STPop( & amp;obj->popstack);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty( & amp;obj->popstack))
{
while(STEmpty( & amp;obj->pushstack)!=true)
{
STPush( & amp;obj->popstack,STTop( & amp;obj->pushstack));
STPop( & amp;obj->pushstack);
}
}
return STTop( & amp;obj->popstack);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty( & amp;obj->pushstack) & amp; & amp;STEmpty( & amp;obj->popstack);
}
void myQueueFree(MyQueue* obj) {
STDestory( & amp;obj->pushstack);
STDestory( & amp;obj->popstack);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
*MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/
First create the structure of the queue, which are the enqueue stack and the dequeue stack.
MyQueue* The myQueueCreate() function opens up space for the queue, initializes the two stacks, and returns the queue structure type pointer.
The void myQueuePush(MyQueue* obj, int x) function implements pushing the elements into the queue into the queue stack.
The function of int myQueuePeek(MyQueue* obj) function is to return the element at the beginning of the queue. Why implement this function first? Because the function to remove the head of the queue can directly use the function to return the head of the queue. First, determine whether the dequeuing stack is empty. If it is empty, all elements in the enqueuing stack must be moved to the dequeuing stack. At this time, the top element of the stack is the head element of the queue, and it can be returned.
The int myQueuePop(MyQueue* obj) function creates a temporary variable front to record the queue head element. Pop the top element in the dequeue stack to complete the deletion of the queue head element, and then return the temporary variable.
The bool myQueueEmpty(MyQueue* obj) function determines whether the queue is empty by checking whether the entry stack and the exit stack are both empty.
The void myQueueFree(MyQueue* obj) function destroys the queue. There are two things that need to be destroyed. The first is the queue entry stack and the queue exit stack, and the second is the queue structure. Because the sequence table in the stack structure also applies for space through the malloc function, the space also needs to be released.
2. Use queues to implement stacks
Design idea: The stack structure contains two queues. According to the first-in-first-out principle of the queue and the last-in-first-out principle of the stack, if it is pushed into the stack, the elements are directly added to the queue that is not empty. If both are empty, then among them Just one. When popping the stack, you need to first move the elements of the non-empty queue to another empty queue. When there is only one element left in the originally non-empty queue, the element is the top element of the stack. Delete it to complete the pop-up. stack. Returning the top element of the stack means returning the tail element among the elements that are not empty. Determine whether the stack is empty by looking at whether both queues are empty. If both queues are empty, the stack is empty. Finally, the stack is released. Since the structure stack is obtained by applying for space, the stack must be released. Secondly, the linked list of the data field in the structure queue is also applied for space, so it must also be destroyed.
code show as below:
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
//Queue node declaration
typedef int QData;
typedef struct QueueNode
{
struct QueueNode* next;
QData data;
}QN;
//Queue overall declaration
typedef struct Queue
{
QN*phead;
QN*ptail;
int size;
}Queue;
//Queue initialization statement
void QueueInit(Queue* pq);
//Queue destruction statement
void QueueDestory(Queue* pq);
//Queue empty statement
bool QueueEmpty(Queue* pq);
//Queue tail insertion statement
void QueuePush(Queue* pq, QData x);
//Queue head deletion statement
void QueuePop(Queue* pq);
//Return the head element of the queue
QData QueueFront(Queue* pq);
//Return the last element of the queue
QData QueueBack(Queue* pq);
//Return the number of queue elements
int QueueSize(Queue* pq);
//Queue initialization implementation
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//Queue destruction implementation
void QueueDestory(Queue* pq)
{
assert(pq);
QN* cur = pq->phead;
while (cur)
{
QN* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//Queue empty judgment implementation
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//Queue tail insertion implementation
void QueuePush(Queue* pq, QData x)
{
assert(pq);
QN* newnode = (QN*)malloc(sizeof(QN));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->data = x;
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size + + ;
}
//Queue head deletion implementation
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QN* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
//Return the head element of the queue
QData QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//Return the last element of the queue
QData QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//Return the number of queue elements
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
{
perror("malloc fail");
return NULL;
}
QueueInit( & amp;obj->q1);
QueueInit( & amp;obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty( & amp;obj->q1))
{
QueuePush( & amp;obj->q1,x);
}
else
{
QueuePush( & amp;obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
Queue* pqueueempty=QueueEmpty( & amp;obj->q1)? & amp;obj->q1: & amp;obj->q2;
Queue* pnoqueueempty=QueueEmpty( & amp;obj->q1)? & amp;obj->q2: & amp;obj->q1;
while(QueueSize(pnoqueueempty)>1)
{
QueuePush(pqueueempty,QueueFront(pnoqueueempty));
QueuePop(pnoqueueempty);
}
int top=QueueFront(pnoqueueempty);
QueuePop(pnoqueueempty);
return top;
}
int myStackTop(MyStack* obj) {
Queue* pqueueempty=QueueEmpty( & amp;obj->q1)? & amp;obj->q1: & amp;obj->q2;
Queue* pnoqueueempty=QueueEmpty( & amp;obj->q1)? & amp;obj->q2: & amp;obj->q1;
return QueueBack(pnoqueueempty);
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty( & amp;obj->q1) & amp; & amp;QueueEmpty( & amp;obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestory( & amp;obj->q1);
QueueDestory( & amp;obj->q2);
free(obj);
}
/**
* Your MyStack struct will be instantiated and called as such:
*MyStack* obj = myStackCreate();
* myStackPush(obj, x);
* int param_2 = myStackPop(obj);
* int param_3 = myStackTop(obj);
* bool param_4 = myStackEmpty(obj);
* myStackFree(obj);
*/
3. Circular queue problem
Design idea: The circular queue can also be implemented through a sequence list or a linked list, here it is implemented through a sequence list.
First, clarify the members contained in the structure circular queue. Since it is a circular queue, it needs to be judged whether it is empty or full, so the queue head and tail mark, the pointer variable of the data field, the data field is a sequence table, and a variable record is needed. Array length.
The basic functions of the circular queue are: 1. Initialization of the circular queue, 2. Determining the emptiness of the circular queue, 3. Determining the fullness of the circular queue, 4. Insertion of the circular queue, 5. Deletion of the circular queue, 6. Obtaining the head element of the queue. , 7. Get the tail element of the queue, 8. Destroy the circular queue.
typedef struct {
int front;
int rear;
int* data;
int k;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if(obj==NULL)
{
perror("malloc fail");
return NULL;
}
obj->data=(int*)malloc(sizeof(int)*(k + 1));
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;
}
obj->data[obj->rear]=value;
obj->rear=(obj->rear + 1)%(obj->k + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front=(obj->front + 1)%(obj->k + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->data[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->data[(obj->rear + obj->k)%(obj->k + 1)];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->front==obj->rear)
{
return true;
}
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear + 1)%(obj->k + 1)==obj->front)
{
return true;
}
return false;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->data);
free(obj);
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
MyCircularQueue* myCircularQueueCreate(int k) function is to create a circular queue, first open up space for the circular queue structure, and open a sequence table with a length of k + 1 for the data field in the circular queue structure, and put it in the circular queue Initialization of member variables. Why a sequence table with a length of k + 1 is opened will be explained in the following judgment of whether the circular queue is full.
The bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) function is used to insert elements. You need to first determine whether the circular queue can still insert data. If not, it will return false. If it is not full, modify the data field in the circular queue structure, that is, the sequence table. and tail of the line. First of all, the tail of the queue represents the next element of the last element in the sequence list, so you can directly assign a value to the array whose subscript is the tail of the queue. What needs attention is the change of the end of the queue. After many additions, deletions and changes, and because it is cyclic, the array subscript of the end of the queue will appear in front of the array subscript of the head of the queue, as shown in the following figure:
According to the demonstration in the above figure, the subscript will go back to the front, so the tail mark is equal to (obj->rear + 1)%(obj->k + 1).
The bool myCircularQueueDeQueue(MyCircularQueue* obj) function is used to delete the head element of the queue. It needs to be judged whether it is empty or not before it can be deleted. If it is not empty, you only need to modify the queue head mark. The principle of modifying the mark of the head of the queue is the same as that of the tail of the queue.
The int myCircularQueueFront(MyCircularQueue* obj) function returns the queue head element. Since the queue head mark points to the subscript of the queue head element, if it is not empty, it can directly return the element with the queue head mark as the subscript.
The int myCircularQueueRear(MyCircularQueue* obj) function returns the queue tail element. The queue tail mark is not the subscript of the queue tail element, but the subscript of the next element of the queue tail element, so special treatment is required. You cannot directly mark the tail of the queue by -1, because when the tail of the queue is marked as 0, the head of the queue is marked at the end of the queue, and it is not suitable to obtain the subscript of the tail element by marking the tail of the queue by -1.
The bool myCircularQueueIsEmpty(MyCircularQueue* obj) function determines whether the circular queue is empty by directly using the head and tail marks of the queue. If the head and tail marks of the queue are equal, it will be empty.
The bool myCircularQueueIsFull(MyCircularQueue* obj) function determines whether the circular queue is full. It cannot be judged by whether the first and last marks of the queue are equal. I don’t know whether it is empty or full at this time. There are two solutions: 1. Create an extra space in the array. If the queue tail mark + 1 is equal to the queue head, it is full. 2. Add a size variable to record the number of data.
The void myCircularQueueFree(MyCircularQueue* obj) function destroys the circular queue, destroys the circular queue body and the data fields in it.
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57509 people are learning the system