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

In this article, the editor introduces in detail the "case analysis of C language stack and queue interview questions". The content is detailed, the steps are clear, and the details are handled properly. I hope this "C language stack and queue interview question example analysis" article can help you solve your doubts. Let's follow the editor's train of thought to learn new knowledge.

1. Parenthesis matching problem

Direct link to:

Valid parentheses

Title:

Train of thought:

Before doing the problem, we must first make clear what the solution is. It is more convenient to solve this problem with the idea of stack, which clearly points out that it is last-in-first-out. We can set it like this:

Encounter the left parenthesis "(", "[", "{", enter the stack.

Encounter the closing parenthesis ")", "]", "}", drop the stack, match with the left parenthesis, and report an error if it does not match.

The meaning of the first two sentences means that I go to traverse the string, if I encounter the left parenthesis, I enter the stack; if I encounter the right parenthesis, I go out of the top element of the stack, and determine whether the right parenthesis matches the top parenthesis of the stack, and returns false if it does not match. The match continues to traverse the string until the traversal is complete. After traversing, check whether the stack is empty, if it is empty, return true, and vice versa.

The code is as follows:

/ / create stack structure typedef char STDataType;typedef struct Stack {STDataType* a; / store data int top; / / position at the top of stack int capacity; / / capacity} ST;// initialize stack void StackInit (ST* ps); / / destroy stack void StackDestory (ST* ps); / / stack pressing void StackPush (ST* ps, STDataType x); / / off stack void StackPop (ST* ps); / / empty bool StackEmpty (ST* ps) / / access top data STDataType StackTop (ST* ps); / / number of valid elements int StackSize (ST* ps); / / definition: / / initialize stack void StackInit (ST* ps) {assert (ps); ps- > a = NULL; ps- > top = 0; ps- > capacity = 0;} / destroy stack void StackDestory (ST* ps) {assert (ps); free (ps- > a) Ps- > a = NULL; ps- > capacity = ps- > top = 0;} / / Stack void StackPush (ST* ps, STDataType x) {assert (ps); / / if the stack is full, consider expanding if (ps- > top = = ps- > capacity) {int newcapacity = ps- > capacity = = 0.4: ps- > capacity * 2 / / Detection capacity ps- > a = (STDataType*) realloc (ps- > a, newcapacity * sizeof (STDataType)); if (ps- > a = = NULL) {printf ("realloc fail\ n"); exit (- 1);} ps- > capacity = newcapacity / / Update capacity} ps- > a [PS-> top] = x position / push data into ps- > top++;// stack top move} / / unstack void StackPop (ST* ps) {assert (ps); assert (ps- > top > 0); ps- > top--;} / / Null bool StackEmpty (ST* ps) {assert (ps); return ps- > top = = 0 / / if top is 0, then it is true, that is, return} / / access the data at the top of the stack STDataType StackTop (ST* ps) {assert (ps); assert (ps- > top > 0); return ps- > a [PS-> top-1]; / / the position of top-1 is the number of elements at the top of the stack} / / the number of valid elements int StackSize (ST* ps) {assert (ps); return ps- > top } / / create a stack and start to implement bool isValid (char* s) {ST st;// first create a stack StackInit (& st); / / initialize stack while (* s) {if (* s = ='['| * s = ='{') {StackPush (& stack, * s); / / if it is a left parenthesis, enter the stack + + s } else {if (StackEmpty (& st)) {return false; / / indicates that there is no left parenthesis at all, which causes the stack to be empty and returns false} char top = StackTop (& st) directly; / / gets the top element StackPop (& stack) / / exit the element at the top of the stack, and then match if ((* s = =']'& & top! ='[') | (* s = =')'& top! ='(') | (* s = ='}'& & top! ='{')) {StackDestory (& st)) / / destroy before returning to prevent memory leak return false; / / if there is no match, return false} else {/ / match at this time, and continue to compare until the traversal ends + + s Empty stack indicates that all left parentheses match bool ret = StackEmpty (& st); StackDestory (& st); / / destroy before returning to prevent memory leak return ret;} 2. Implement stack with queue

Direct link to:

Implement the stack with queues

Title:

Train of thought:

Before you do the problem, let's make two more basic knowledge points clear.

Stack: last in, first out

Queue: first in, first out

In this problem, the first-in-first-out queue is used to implement the LIFO stack, and the basic interface of the queue is simulated.

Suppose we have a string of numbers, the order of entering queue An is 1 2 3 4, and then there is another queue B. at this time, we take the head data of queue An and import it into queue B. when queue An is the last one, we delete queue A to pop. Queue B is 1 2 3. Indirectness realizes the function of stack and the function of LIFO. When we need to reenter the data, we just need to list it to a team that is not empty. Come out again, just like that. In short, two sentences:

Stack: push data to a queue that is not empty.

Unstack: import the data from the non-empty queue into another empty queue, and then delete the last one.

Essence: keep one queue to store data, another queue is empty, and the empty queue is used to guide data when you want to get out of the stack.

The code is as follows:

/ / create a queue structure typedef int QDataType; / / facilitate subsequent changes to the storage data type. This article takes int as an example / / create a queue node typedef struct QueueNode {QDataType data; / / store data struct QueueNode* next; / / record the next node} QNode;// save the queue header and tail typedef struct Queue {QNode* head; / / head pointer QNode* tail; / / tail pointer} Queue / / initialize the queue void QueueInit (Queue* pq); / / destroy the queue void QueueDestory (Queue* pq); / / enter the queue void QueuePush (Queue* pq, QDataType x); / / dequeue void QueuePop (Queue* pq); / / determine the empty bool QueueEmpty (Queue* pq); / / get the number of valid elements size_t QueueSize (Queue* pq); / / get the queue head element QDataType QueueFront (Queue* pq); / / get the queue end element QDataType QueueBack (Queue* pq) / definition: / / initialize queue void QueueInit (Queue* pq) {assert (pq); pq- > head = pq- > tail = NULL;} / / destroy queue void QueueDestory (Queue* pq) {assert (pq); QNode* cur = pq- > head; while (cur) {QNode* next = cur- > next; free (cur) Cur = next;} pq- > head = pq- > tail = NULL;} / / queue void QueuePush (Queue* pq, QDataType x) {assert (pq); / / create a new node to store data QNode* newnode = (QNode*) malloc (sizeof (QNode)); / / brute force detection newnode, because assert (newnode) is detected in malloc. Newnode- > next = NULL; newnode- > data = x; / / if there is no data at first, if is empty (pq- > tail = = NULL) {assert (pq- > head = = NULL); pq- > head = pq- > tail = newnode;} else {pq- > tail- > next = newnode Pq- > tail = newnode;}} / / dequeued void QueuePop (Queue* pq) {assert (pq); assert (pq- > head & & pq- > tail); / / tail and head cannot be empty / / special: if (pq- > head- > next = = NULL) {free (pq- > head) when deleted to head=tail location Pq- > head = pq- > tail = NULL;} / / generally else {/ / Save the next node of head QNode* next = pq- > head- > next; free (pq- > head); pq- > head = next }} / / empty bool QueueEmpty (Queue* pq) {assert (pq); return pq- > head = = NULL;} / / get the number of valid elements size_t QueueSize (Queue* pq) {assert (pq); QNode* cur = pq- > head; size_t size = 0; while (cur) {size++; cur = cur- > next } return size;} / / get the header element QDataType QueueFront (Queue* pq) {assert (pq); assert (pq- > head); / / the header cannot be empty return pq- > head- > data;} / / get the tail element QDataType QueueBack (Queue* pq) {assert (pq); assert (pq- > tail); / / the tail cannot be empty return pq- > tail- > data } / * create the queue structure and start the body simulation implementation stack * / typedef struct {Queue Q1; / / queue Q1 Queue Q2; / / queue Q2} MyStack; MyStack* myStackCreate () {MyStack* pst = (MyStack*) malloc (sizeof (MyStack)); / / apply for a stack assert (pst) of MyStack type QueueInit (& pst- > Q1); / initialize queue 1 QueueInit (& pst- > Q2); / / initialize queue 2 return pst;} void myStackPush (MyStack* obj, int x) {assert (obj); if (! QueueEmpty (& obj- > Q1)) {QueuePush (& obj- > Q1, x) / / if Q1 is not empty, insert data} else {QueuePush (& obj- > Q2, x) into Q1; / / there is no need to know whether Q2 is empty, directly push}} int myStackPop (MyStack* obj) {assert (obj); Queue* emptyQ = & obj- > Q1; / / default Q1 is empty Queue* nonEmtpyQ = & obj- > Q2 / / default Q2 is not empty if (! QueueEmpty (& obj- > Q1)) {emptyQ = & obj- > Q2; / / if the assumption is wrong, Q2 is empty nonEmtpyQ = & obj- > Q1 nonEmtpyQ / then Q1 is empty} while (QueueSize (nonEmtpyQ) > 1) {QueuePush (emptyQ, QueueFront (nonEmtpyQ) / / transfer the non-empty queue data to the empty queue until there is only one QueuePop (nonEmtpyQ); / / delete the non-empty queue header data at this time to facilitate subsequent import data} int top = QueueFront (nonEmtpyQ); / / record the stack top data QueuePop (nonEmtpyQ) at this time; / / delete the stack top data to make the queue empty return top } int myStackTop (MyStack* obj) {assert (obj); if (! QueueEmpty (& obj- > Q1)) {return QueueBack (& obj- > Q1); / / if Q1 is not empty, return} else {return QueueBack (& obj- > Q2);} bool myStackEmpty (MyStack* obj) {assert (obj) / / if both queues are empty, empty return QueueEmpty (& obj- > Q1) & & QueueEmpty (& obj- > Q2);} void myStackFree (MyStack* obj) {assert (obj); QueueDestory (& obj- > Q1); / / release Q1 QueueDestory (& obj- > Q2); / / release Q2 free (obj);} 3. Implement the queue with stack

Direct link to:

Implementing queues with stacks

Title:

Train of thought:

Assuming that the order of entering the stack is 12-3-4, then according to the meaning of the question, we want to achieve the out-of-stack order of 1 2-3-4 in order to realize the queue.

This question is just the opposite of the previous one, using the stack to implement the queue. In the last question, we need to return the data to achieve the LIFO function of the stack, but this question does not need to be guided at all, only once.

Suppose we have two stacks, named pushST and popST. And put 4 pieces of data 1 2 3 4 into the stack pushST, and only get 4 according to the nature of the stack. At this time, we directly take down the 4 and import it into the stack popST, and continue to import the data in the pushST stack until the stack pushST data is empty. At this point, the popST data is 4-3-2-1, which is exactly the reverse.

According to the first-in-first-out rule of the queue, the data of the stack popST is known to be 4-3-2-1. When the data is deleted, it will be deleted one by one in the order of 1-2-4. It happens to make use of the nature of the stack to realize the first-in-first-out function of the queue. And it only needs to be guided once, and there is no need for many times.

The code is as follows:

/ / create stack structure typedef int STDataType;typedef struct Stack {STDataType* a; / store data int top; / / position at the top of stack int capacity; / / capacity} ST;// initialize stack void StackInit (ST* ps); / / destroy stack void StackDestory (ST* ps); / / stack pressing void StackPush (ST* ps, STDataType x); / / off stack void StackPop (ST* ps); / / empty bool StackEmpty (ST* ps) / / access top data STDataType StackTop (ST* ps); / / number of valid elements int StackSize (ST* ps); / / initialize stack void StackInit (ST* ps) {assert (ps); ps- > a = NULL; ps- > top = 0; ps- > capacity = 0;} / destroy stack void StackDestory (ST* ps) {assert (ps); free (ps- > a); ps- > a = NULL; ps- > capacity = ps- > top = 0 } / / stack void StackPush (ST* ps, STDataType x) {assert (ps); / / if the stack is full, consider expanding if (ps- > top = = ps- > capacity) {int newcapacity = ps- > capacity = = 0.4: ps- > capacity; / / detection capacity ps- > a = (STDataType*) realloc (ps- > a, newcapacity * sizeof (STDataType)) If (ps- > a = = NULL) {printf ("realloc fail\ n"); exit (- 1);} ps- > capacity = newcapacity; / / Update capacity} ps- > a [PS-> top] = x [PS-> top] = x Band / push data into ps- > top++;// stack top move up} / / off stack void StackPop (ST* ps) {assert (ps) Assert (ps- > top > 0); ps- > top--;} / / empty bool StackEmpty (ST* ps) {assert (ps); return ps- > top = = 0; / / if top is 0, it is true, that is, it returns} / / access the top stack data STDataType StackTop (ST* ps) {assert (ps); assert (ps- > top > 0); return ps- > aps [> top- 1] / / the position of top-1 is the number of valid elements at the top of the stack int StackSize (ST* ps) {assert (ps); return ps- > top;} / * create the stack structure and start the body * / typedef struct {ST pushST; / / insert data stack ST popST; / / delete data stack} MyQueue MyQueue* myQueueCreate () {MyQueue* obj = (MyQueue*) malloc (sizeof (MyQueue)); / / Application queue type assert (obj); StackInit (& obj- > pushST); / / initialize pushST StackInit (& obj- > popST); / / initialize popST return obj;} void myQueuePush (MyQueue* obj, int x) {assert (obj); StackPush (& obj- > pushST, x) / / insert} int myQueuePop (MyQueue* obj) {assert (obj); if (StackEmpty (& obj- > popST)) / / if the popST data is empty, you have to import data from pushST to delete {while (! StackEmpty (& obj- > pushST)) / / pushST data is not empty, then import data {StackPush (& obj- > popST, StackTop (& obj- > pushST)) into popST / / Import the top data of the pushST stack to popST StackPop (& obj- > pushST); / / delete the top element of the pushST stack after import, so as to facilitate subsequent guidance}} int front = StackTop (& obj- > popST); / / record the top element of the popST stack StackPop (& obj- > popST); / / delete the top element of the popST stack to achieve the queue FIFO return front / / return the data at the top of the stack} / / fetch the header data int myQueuePeek (MyQueue* obj) {assert (obj) / / if popST data is empty, you need to import data from pushST to get the line head data if (StackEmpty (& obj- > popST)) {while (! StackEmpty (& obj- > pushST)) / / pushST data is not empty, then import data {StackPush (& obj- > popST, StackTop (& obj- > pushST)) into popST all the time; / / Import pushST stack top data to StackPop (& obj- > pushST) in popST Delete the top element of the pushST stack after import, so that you can continue to guide}} return StackTop (& obj- > popST); / / return the top element} bool myQueueEmpty (MyQueue* obj) {return StackEmpty (& obj- > pushST) & & StackEmpty (& obj- > popST);} void myQueueFree (MyQueue* obj) {assert (obj); StackDestory (& obj- > pushST); StackDestory (& obj- > popST); free (obj) } 4. Design a circular queue

Direct link to:

Design cycle queue

Title:

Train of thought:

This problem can be implemented in arrays or linked lists, but it is actually more convenient to use arrays.

Array:

Suppose the head of the line front and the end of the line tail both point to the first data, insert the data at the end of the line, tail moves as the data is inserted, and tail is always the next location of the last data. To delete data, you only need to move the header front back. You do not need to delete and move the data like the pop in the previous queue, because it is a circular linked list and the data can be reused.

This analysis coupled with the drawing does not seem to have any defects, but there are two problems?

When is the array empty?

Under what circumstances is the array full?

Question 1:

When tail = front, the array is empty, which seems fine, but there are two cases of equality. Draw a picture first:

As you can see from the above figure, in the case, there is indeed no data in the array, and tail is also equal to front, which satisfies the condition that the array is empty, but in case 2, the data of the array is full, and the tail and front are also equal, where the array is not empty, but full, which shows that there is a problem.

Solution:

Here we can open an extra space without storing data, just to distinguish whether the array is empty or full. The principle is as follows: when the length of the array is 4, that is, it can actually store three valid data, and the other space is used to judge whether it is empty or full. The conditions for judging empty or full are as follows:

Empty when front = tail

When the next location of tail is front, it is full.

The code is as follows:

Typedef struct {int* a; / simulate ring queue int front;// header int tail; / / tail int k with array; / / indicate that the stored data length is k} MyCircularQueue; bool myCircularQueueIsFull (MyCircularQueue* obj); / / pre-declaration bool myCircularQueueIsEmpty (MyCircularQueue* obj); / / pre-declaration MyCircularQueue* myCircularQueueCreate (int k) {MyCircularQueue* obj = (MyCircularQueue*) malloc (sizeof (MyCircularQueue)) / / create a circular linked list structure assert (obj); obj- > a = (int*) malloc (sizeof (int) * (k + 1)); / / Open one more space to facilitate subsequent discrimination between empty and full obj- > front = obj- > tail = 0; obj- > k = k; / / queue stores valid data length k return obj;} bool myCircularQueueEnQueue (MyCircularQueue* obj, int value) {if (myCircularQueueIsFull (obj)) {return false / / the queue is full and cannot insert data} obj- > a [obj-> tail] = value; / / assigned if (obj- > tail = = obj- > k) {obj- > tail = 0; / / when tail comes to the end} else {obj- > tail++;} return true;} bool myCircularQueueDeQueue (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj)) {return false / / queue is empty and cannot delete} if (obj- > front = = obj- > k) {obj- > front = 0; / / when front goes to the end} else {obj- > front++;} return true;} / / fetch int myCircularQueueFront (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj)) {return-1 / / the queue is empty and cannot take} return obj- > a [obj-> front]; / / return to the head of the line} / / take the tail int myCircularQueueRear (MyCircularQueue* obj) {if (myCircularQueueIsEmpty (obj)) {return-1; / / the queue is empty and cannot take} if (obj- > tail = = 0) {return obj- > a [obj-> k] / / tail is 0, tail is at the last position of length} else {return obj- > a [obj-> tail-1];}} bool myCircularQueueIsEmpty (MyCircularQueue* obj) {return obj- > front== obj- > tail; / / front==tail is empty} bool myCircularQueueIsFull (MyCircularQueue* obj) {if (obj- > tail = = obj- > k & & obj- > front== 0) {return true / / full} else {return obj- > tail + 1 = = obj- > front; / / when the tail end of tail and front is at the head end, and full} void myCircularQueueFree (MyCircularQueue* obj) {free (obj- > a) when the next position of tail is front; free (obj) } after reading this, the article "example Analysis of C language Stack and queue interview questions" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, welcome to follow the industry information channel.

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.