Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how C language stack and queue realize each other". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

I. the key points of this chapter

Implement the stack with two queues

Implement the queue with two stacks

Summary of ideas for solving problems

Second, queue implementation stack

We have two queues:

Stack data 1, 2, 3

Data can be queued to queue one or queue two.

How to get off the stack?

But out of the stack must be out of 1, what to do?

Step one:

Put one out of queue one to queue two.

Step 2:

The last element of pop queue one.

How do you get into the stack next?

Queue the element to a queue that is not empty.

How to judge the empty stack?

When queue one and queue two are empty, the stack is empty.

How to get the top element of the stack?

Fetch the tail element of the queue that is not empty.

In general, when you enter the stack, you insert the data into a queue that is not empty, and when you exit the stack, you import the first NMI data of the queue that is not empty into another queue, and then pop the last element.

Code implementation:

First we need to construct a stack.

This stack should contain two queues

Typedef struct {Queue Q1; Queue Q2;} MyStack

Before that, we need to prepare the general interface of the queue:

My queue here is built with a single linked list, and the specific interface implementation can be seen in my previous article.

Typedef int QTypeData;typedef struct QueueNode {struct QueueNode* next; QTypeData val;} QN; void QueueInit (Queue* pq) / / initialize queue size_t QueueSize (Queue* pq) / / count the number of queue elements int QueueBack (Queue* pq) / / fetch queue tail data void QueuePush (Queue* pq, QTypeData x) / / void QueuePop (Queue* pq) / / dequeue void QueueDestroy (Queue* pq) / / end queue

We will use queues to implement the interface of the stack:

First interface: create and initialize the stack

API 1: MyStack* myStackCreate ()

Is this all right?

MyStack* myStackCreate () {MyStack ms; QueueInit (& ms.q1); QueueInit (& ms.q2); return ms;}

Obviously, it is unwise to return the address of a local variable, because when the function returns, the space opened by ms will be handed back to the operating system, and it is illegal to access it again.

So we need to open up ms in the stack area.

Reference Code:

The second interface: enter the stack

Interface 2: void myStackPush (MyStack* obj, int x)

Getting into the stack is easy: just insert the data into a queue that is not empty.

Do we need to judge whether the queue is full before entering the stack?

No, because my queue is implemented in a single linked list and can be linked indefinitely.

If both queues are empty, which queue should be inserted?

We can do this, if queue 1 is empty, insert into queue 2, if not empty, insert queue 1.

Reference Code:

The third interface: de-stack

Interface 3: int myStackPop (MyStack* obj) / / unstack

Let's review how we got out of the stack again.

First of all, we have two queues

In the initial state, they are all empty.

Queue 1: empty

Queue two: empty

Stack 1, 2, 3, 4

After implementation

Queue 1: empty

Queue two: 1, 2, 3, 4

Out of the queue can only be out of 1, how to get out of 4?

Give 1, 2, 3 to queue one first.

After implementation

Queue 1: 1, 2, 3

Queue two: 4

Then record 4 as a variable and dequeue, and finally return the variable of record 4.

After implementation

Queue 1: 1, 2, 3

Queue two: empty.

Get out of the team with three axes

Step 1: put the first nmur1 element of the non-empty queue into the empty queue.

Step 2: record the remaining 1 element as a variable, and then dequeue the last element.

Step 3: return the element recorded with a variable.

It is important to note that if the stack is empty, false is returned.

Reference Code:

The fourth interface: take the top element of the stack

API 4: int myStackTop (MyStack* obj) / / fetch the top elements of the stack

Before taking the top element, we need to make sure that the stack is not empty.

Returns false if the stack is empty.

Fetch the top element of the stack, that is, the tail element of the queue that is not empty.

Reference Code:

The fifth interface: determine whether the stack is empty

API 5: bool myStackEmpty (MyStack* obj) / / determines whether the stack is empty

If both queues are empty, then the stack is empty.

One more thing here, how to find the number of elements in the stack?

The number of elements in the stack is the number of elements that are not empty queues.

Reference Code:

The sixth interface: destroy the stack

Interface 6: void myStackFree (MyStack* obj) / / end stack

Reference Code:

Void myStackFree (MyStack* obj) {QueueDestroy (& obj- > Q1); QueueDestroy (& obj- > Q2); free (obj);}

Finally, it is important to note that when calling an interface with an empty stack, declare it first!

Third, stack implementation queue

Join the team for the first time

Dequeue operation of data 1

Import all the data of stack 1 into stack 2

Then stack 2 carries out the stack operation.

Rejoin the team 5, 6, 7

Directly stack 5, 6, 7 to stack 1

In fact, our opponents and the end of the line are like this.

In general:

If you use two stacks to implement a queue, you have to put one stack into the queue and the other stack to make a queue. When it is implemented here, we use stack 1 to enter the queue stack and stack 2 to make the queue stack.

In other words, as long as the data into the queue, directly into the stack 1.

If stack 2 is empty, all the data of stack 1 will be imported into stack 2.

Structure of the queue:

Typedef struct {ST st1; ST st2;} MyQueue

We need to prepare the stack.

Typedef int STDataType;typedef struct Stack {STDataType* data; int top; int capacity;} ST

Here I use a stack implemented by a dynamic array.

The interface of the stack needs to be prepared in advance:

Void STInit (ST* p) void STDestroy (ST* p) void STPush (ST* pjournal STDatatype x) void STPop (ST* p) bool STEmpty (ST* p) int STSize (ST* p) STDataType STRear (ST* p)

First interface: create and initialize queues

MyQueue* myQueueCreate ()

Similarly, you need to open the queue in the stack area and initialize stack 1 and stack 2 at the same time.

Reference Code:

MyQueue* myQueueCreate () {MyQueue* mq= (MyQueue*) malloc (sizeof (MyQueue)); assert (mq); STInit (& mq- > st1); STInit (& mq- > st2); return mq;}

The second interface: join the team.

Void myQueuePush (MyQueue* obj, int x)

We put stack 1 into the queue stack and stack 2 to make the queue stack.

In other words, as long as the data into the queue, directly into the stack 1.

If stack 2 is empty, all the data of stack 1 will be imported into stack 2.

Reference Code:

Void myQueuePush (MyQueue* obj, int x) {STPush (& obj- > st1,x);}

The third interface: get out of the team

Int myQueuePop (MyQueue* obj)

The first step is to determine whether the queue is empty, and return false if the queue is empty.

Secondly, if stack 2 is empty, all the data of stack 1 is imported into stack 2.

Reference Code:

Int myQueuePop (MyQueue* obj) {if (myQueueEmpty (obj)) {return false;} if (STEmpty (& obj- > st2)) {int n=STSize (& obj- > st1); while (while) {STPush (& obj- > st2,STRear (& obj- > st1)); STPop (& obj- > st1);} int ret=STRear (& obj- > st2) STPop (& obj- > st2); return ret;}

The fourth interface: fetch the queue header element

Int myQueuePeek (MyQueue* obj)

Before fetching the queue header element, determine whether the queue is empty. If so, return false.

The line header element is the tail element of stack 2.

But what if stack 2 is empty?

The header element of the queue is the header element of stack 1.

Reference Code:

Int myQueuePeek (MyQueue* obj) {if (myQueueEmpty (obj)) {return false;} if (& obj- > st2) {return STFront (& obj- > st1);} return STRear (& obj- > st2);}

The fifth interface: determine whether the queue is empty

Bool myQueueEmpty (MyQueue* obj)

The queue is empty, requiring both stack 1 and stack 2 to be empty.

Reference Code:

Bool myQueueEmpty (MyQueue* obj) {return STEmpty (& obj- > st1) & & STEmpty (& obj- > st2);}

The sixth interface: destroy the queue

Void myQueueFree (MyQueue* obj)

Reference Code:

Void myQueueFree (MyQueue* obj) {STDestroy (& obj- > st1); STDestroy (& obj- > st2); free (obj);}

Note: when using an interface that determines whether the queue is empty, pay attention to whether it has been declared before.

IV. Summary of ideas for solving problems

1. Implement the stack with queues:

We need to implement the stack with two queues

The stack class is deleted at the end.

The queue is deleted by tail plug.

Enter the stack for the first time: both queues are empty and can be inserted into any queue.

The first time out of the stack: out of the stack is the tail data, the queue can only output header data, which can not be directly realized by the queue.

Then you need to import one piece of data in front of the non-empty queue into the empty queue, and then pop the last element.

Queue 1: 1, 2, 3, 4

Queue two: empty

So after import,

Queue 1: 4

Queue two: 1, 2, 3

Finally, the last element of pop

Queue 1: empty

Queue two: 1, 2, 3, 4

Insert the tail again: insert the tail into a queue that is not empty.

two。 Implementing queues with stacks

We have two stacks that require a general interface for implementing queues

Stack 1: empty

Stack 2: empty

Join the queue for the first time: enter the stack to stack one or stack two, and choose stack one here.

Suppose you join the team 1, 2, 3, 4

Stack 1: 1, 2, 3, 4

Stack 2: empty

Get out of the team: you have to go 1 first.

Import all stack one into stack two

Stack 1: empty

Stack 2: 4, 3, 2, 1

Then join the team and insert it into stack 1.

Pop stack two when you come out of the team.

This is the end of the content of "how C language stack and queue implement each other". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.