This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
The stack and queue
Stack and queue are two types of data structures, and stack and queue are also linear tables. In particular, there are restrictions on how they can operate.
1 stack
1.1 Definition and structure of stack
A stack is a special kind of linear table that allows only insertion and deletion of elements at its fixed end. The end where data is inserted or deleted is called the top of the stack, and the other end is called the bottom of the stack. The data elements in the stack follow the last in, first out principle.
Last In First Out, First In First Out.
Pushing: The operation of inserting a stack is called pushing, or pushing.
Ejection: The operation of inserting a stack is called ejection, or pop stack.
Data entry and exit are at the top of the stack, similar to the process of loading and firing bullets. Like bullets, the elements are pushed in and out of the clip one by one, and the clip is the stack.
Stack structure definition
Like linear tables, the stack structure can be implemented using array stacks and chain stacks. In contrast, the array stack has more structural advantages than the chain stack.
Dynamic array has a high efficiency of tail insertion and tail deletion and a high cache hit ratio, but the disadvantage is that dynamic capacity has a certain memory consumption. The linked stack needs to use bidirectional linked list, otherwise the efficiency of tail deletion is low, but the efficiency of plug deletion is higher when the head of the linked list is used as the top of the stack.
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
Copy the codeA refers to the space allocated to the stack, and top refers to the top of the stack, which corresponds to the size of the order table.
1.2 Implementation of stack
// Initialize the stack
void StackInit(ST* ps);
/ / into the stack
void StackPush(ST* ps, STDataType data);
/ / out of the stack
void StackPop(ST* ps);
// Get the top element of the stack
STDataType StackTop(ST* ps);
// Get the stack element number
int StackSize(ST* ps);
// Check for empty stacks
bool StackEmpty(ST* ps);
/ / destruction of stack
void StackDestroy(ST* ps);
Copy the codeStack initialization and destruction
void StackInit(ST* ps) {
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackDestroy(ST* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
Copy the codeTop can be initialized to 0 or -1.
- If is 0, then
topAlways the subscript of the element to be inserted, or the space below the top of the stack, whose value represents the stack element. - If set to -1, it represents the subscript of the current top of the stack, and its value plus 1 represents the number of elements.
Push and pop of the stack
void StackPush(ST* ps, STDataType data) {
assert(ps);
// Check the capacity
if (ps->capacity == ps->top) {
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* ptr = realloc(ps->a, sizeof(STDataType) * newCapacity);
if (ptr == NULL) {
perror("StackPush::realloc");
exit(- 1);
}
ps->a = ptr;
ps->capacity = newCapacity;
}
ps->a[ps->top] = data;
ps->top++;
}
void StackPop(ST* ps) { assert(ps); assert(! StackEmpty(ps)); ps->top--; }Copy the codeRemember to assign newCapacity to capacity at the end of the stack, and to expand the capacity by the size of the array element, not the structure.
Ensure that the stack is not empty before deleting data.
Gets the top of the stack element
STDataType StackTop(ST* ps) { assert(ps); assert(! StackEmpty(ps));return ps->a[ps->top - 1];
}
void test(a) {
while(! StackEmpty(&stack)) {
printf("%d ", StackTop(&stack));
StackPop(&stack); }}Copy the codeTop-1 is the index at the top of the current stack. Again, make sure the stack is not empty.
With this test function, you can realize the function of printing stack elements in a loop.
Other Basic Interfaces
// Get the stack element number
int StackSize(ST* ps) {
assert(ps);
return ps->top;
}
// Check for empty stacks
bool StackEmpty(ST* ps) {
assert(ps);
return! ps->top; }Copy the code! The value of top is exactly what indicates the state of the stack with or without elements. Of course then top has to be initialized to 0.
2 the queue
2.1 Definition and structure of queues
A queue is also a special type of linear table that, in contrast to a stack, allows only inserts at one end and deletions at the other. The end where data is inserted is called the end of the queue, and the end where data is deleted is called the end of the queue. The data elements in the queue are first-in, first-out.
In the queue, data is inserted at the end of the queue, while in the queue, data is deleted at the head of the queue.
First In, First Out, last In, last Out, that is the FIFO principle.
Queue structure definition
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
} QueueNode;
typedef struct Queue
{
struct QueueNode* head;
struct QueueNode* tail;
} Queue;
Copy the codeQueues require two Pointers to identify the head and tail of the queue to manage the elements of the queue. Queue elements, nodes, can be implemented as single-linked lists. The node is encapsulated into a structure, and the queue is encapsulated into a structure and stored in a pointer to the node structure.
The tail-queue pointer is designed because the queue object only inserts at the tail-queue. The original single linked list tail has two operations of insertion and deletion, so the definition of tail pointer is not meaningful, leaving the storage function to the bidirectional linked list to complete.
The definition of a Queue is flexible, and it is possible not to define the Queue structure or to encapsulate the Pointers to and from the Queue. Then the function needs to be defined as:
void QueueInit(QueueNode** pphead, QueueNode** pptail); Copy the codeObviously, encapsulation into structures is a good code style.
2.2 Implementation of queues
// Queue initialization
void QueueInit(Queue* pq);
// Queue destruction
void QueueDestroy(Queue* pq);
// enter the queue
void QueuePush(Queue* pq, QDataType x);
// Queue out
void QueuePop(Queue* pq);
// Get queue header data
QDataType QueueFront(Queue* pq);
// Get queue end data
QDataType QueueBack(Queue* pq);
// Get the number of queue elements
int QueueSize(Queue* pq);
// Check whether the queue is empty
bool QueueEmpty(Queue* pq);
Copy the codeQueue initialization and destruction
void QueueInit(Queue* pq) {
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
void QueueDestroy(Queue* pq) {
assert(pq);
QueueNode* cur = pq->head;
while (cur) {
QueueNode* next = cur->next;
free(cur); cur = next; }}Copy the codeInitialization and destruction do not pass secondary Pointers because the address of the structure is passed, and the two Pointers are encapsulated in the structure. The queue is created outside the function, so just pass its address and add an assertion to the pointer.
The end of the team and the head of the team
void QueuePush(Queue* pq, QDataType x) {//Enqueue
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) {
perror("Queue::malloc");
exit(- 1);
}
newNode->data = x;
newNode->next = NULL;
// The queue is empty
if (pq->head == NULL) {
pq->head = pq->tail = newNode;
}
else{ pq->tail->next = newNode; pq->tail = newNode; }}void QueuePop(Queue* pq) {//Dequeueassert(pq); assert(! QueueEmpty(pq)); QueueNode* next = pq->head->next;free(pq->head);
pq->head = next;
// If the list is empty, the tail pointer is null
if (pq->head == NULL) {
pq->tail = NULL; }}Copy the codeJoin a team by creating a new node at the end of the queue indicated by tail and attaching the tail pointer to the new node. A node can only be deleted at the head of the queue, i.e. the head pointer points to the next node and the previous node is released.
Head ->next To dereference the head pointer, we must ensure that head has next, that the list is not empty.
Gets the header and tail elements
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;
}
Copy the codeTail ->data; dereference the pointer; check whether the pointer is valid.
void test(a) {
/ /...
while(! QueueEmpty(&q)) {printf("%d ", QueueFront(&q)); QueuePop(&q); }}Copy the codeWith the above functions can be simulated to achieve circular queue.
Other Basic Interfaces
// Get the number of queue elements
int QueueSize(Queue* pq) {
assert(pq);
int count = 0;
QueueNode* cur = pq->head;
while (cur) {
count++;
cur = cur->next;
}
return count;
}
// Check whether the queue is empty
bool QueueEmpty(Queue* pq) {
assert(pq);
return! pq->head; }Copy the codeGet the number of queue elements. In addition to traversal counting, you can also define an integer variable to be placed in the node structure.
Stack and queue interview questions
Example 1 Check valid parentheses
Judge valid parenthesis
Given a string s containing only (,),{,},[,], determine whether the string is valid.
bool isValid(char* s) {
ST st;
StackInit(&st);
while (*s) {
if (*s == '(' || *s == '[' || *s == '{') {
StackPush(&st, *s);
}
else {
// The stack has no elements and cannot match the closing bracket
if (StackEmpty(&st)) {
StackDestroy(&st);
return false;
}
STDataType ret = StackTop(&st);
if ((ret == '('&& *s ! =') ') || (ret == '['&& *s ! ='] ') || (ret == '{'&& *s ! ='} ')) {
StackDestroy(&st);
return false;
}
else {
StackPop(&st);
}
}
s++;
}
if (StackEmpty(&st)) {
StackDestroy(&st);
return true;
}
else {
StackDestroy(&st);
return false; }}Copy the codeTake advantage of the advanced out of the stack, last in, first out characteristics.
- The string
sI’m going back and forth and I’m going to push all the open parentheses, - When a close parenthesis is encountered, the nearest open parenthesis can be compared to the close parenthesis using lifO.
- If the match is successful, the stack is pushed once, and the next time the previous open parenthesis is found to match the next close parenthesis.
Example 2 Queue implementation stack
Queue implementation stack
Implement a last-in, first-out stack with two queues and support all four operations of a normal stack (push, top, POP, and Empty)
Instead of an array with a linked list, use a queue for a stack. That is to use the structure of the queue and interface function, that is, the characteristics of the queue to achieve a structure, the structure has the characteristics of the stack.
/** * struct definition **/
typedef struct QueueNode {
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue {
struct QueueNode* head;
struct QueueNode* tail;
}Queue;
typedef struct {
Queue q1;
Queue q2;
} MyStack;
Copy the code
/** * interface function definition **/
MyStack* myStackCreate(a) {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
if (st == NULL) {
exit(- 1);
}
QueueInit(&st->q1);
QueueInit(&st->q2);
return st;
}
// Call the function to create the heap structure and return
void myStackPush(MyStack* obj, int x) {
assert(obj);
// Push to a non-empty queue
if(! QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); }else{ QueuePush(&obj->q2, x); }}int myStackPop(MyStack* obj) {
assert(obj);
// Define empty and non-empty queues
Queue* emptyQ = &obj->q1;
Queue* nonEmptyQ = &obj->q2;
if(! QueueEmpty(&obj->q1)) { nonEmptyQ = &obj->q1; emptyQ = &obj->q2; }// Push the first n-1 element of the non-empty queue to the empty queue
while (QueueSize(nonEmptyQ) > 1) {
QueuePush(emptyQ, QueueFront(nonEmptyQ));
QueuePop(nonEmptyQ);
}
//Pop the last element and return
int top = QueueFront(nonEmptyQ);
QueuePop(nonEmptyQ);
return top;
}
int myStackTop(MyStack* obj) {
assert(obj);
// Returns the element at the end of a queue that is not empty
if(! QueueEmpty(&obj->q1)) {return QueueBack(&obj->q1);
}
else {
returnQueueBack(&obj->q2); }}bool myStackEmpty(MyStack* obj) {
assert(obj);
// Both are empty
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
assert(obj);
// Release the queue node
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
// Release the structure
free(obj);
}
Copy the codePushSince both stack and queue are entered from the fixed end, the simulated push can be directly added to the non-empty queue.
PopWhen simulating out of the stack, we should consider the difference between the two and delete the front in the queue first
Element and put it into another empty queue. Until the first
Element and then delete it.
The first queue sends out data and the last queue sends in data, just inserting the NNN elements before the non-empty queue into the empty queue in the original order. The non-empty queue is reduced to the last element and then deleted. The queue is regarded as the stack after the stack, then the process of simulating the stack is realized.
Top, directly call the queue to read the last element of the interface function can be.
There is an empty queue and a non-empty queue after any operation. The non-empty queue can be treated as the object to be operated on. That is, every operation operates on a non-empty queue.
Example 3 Stack implementation queue
Stack implementation queue
Use two stacks to implement a first-in, first-out queue. Queues should support all operations supported by normal queues (push, POP, peek, EMPTY)
/** * struct definition **/
typedef int STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
typedef struct {
ST pushST;
ST popST;
} MyQueue;
Copy the code
/** * interface function definition **/
MyQueue* myQueueCreate(a) {
MyQueue* pq= (MyQueue*)malloc(sizeof(MyQueue));
if (pq == NULL) {
exit(- 1);
}
StackInit(&pq->pushST);
StackInit(&pq->popST);
return pq;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST, x);
}
int myQueuePop(MyQueue* obj) {
// If the stack is empty, all elements on the stack will be moved to the stack
if (StackEmpty(&obj->popST)) {
while (!StackEmpty(&obj->pushST)) {
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
// Remove the top of the stack, i.e. the header element
int front = StackTop(&obj->popST);
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {
// If the stack is empty, all elements on the stack will be moved to the stack
if (StackEmpty(&obj->popST)) {
while (!StackEmpty(&obj->pushST)) {
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);
}
}
// returns the top of the stack, the header element
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
free(&obj->pushST);
free(&obj->popST);
free(obj);
}
Copy the codeBecause of the last-in, first-out nature of the stack, moving an element from one stack to another creates the phenomenon of “inversion”. Inserting elements into a non-empty stack at this point results in an order error. PushST and popST are responsible for pushing and pushing, respectively.
Push, will insert elements directly into the one responsible for pushingpushSTIn the.
Pop.popSTIf it is empty, it willpushSTThe element moves topopST. Again frompopSTPushing off the stack equals deletingpushSTThe bottom element of the stack.
To move an element from “on” to “off” is to invert the element, which is already the same as the unqueued operation of the queue. Equivalent to the bottom of the stack from the bottom of the stack out of the stack, that is, from the first in, first out to first in, simulate the realization of the queue.
PushST and popST do not affect each other to complete the task of queue entry and queue exit respectively. As long as popST is empty, move the element from pushST in.
Example 4 implements the loop queue
Implementing circular queues
Circular queues can be implemented in both arrays, which loop through subscripts, and linked lists, which loop lists.
- A circular queue is also a queue, satisfying all the properties of a queue,
- Circular queue space size is fixed and reusable,
- One more element of space is needed for full judgment.
Tail ->next==head; tail==head; Array using subscript control. More space to judge.
Array implementation
/** * struct definition **/
typedef struct {
int* a;
int front;
int tail;
int k;
} MyCircularQueue;
/** * interface function definition **/
MyCircularQueue* myCircularQueueCreate(int k) {
// Create space for the structure
MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
// open an array
cq->a = (int*)malloc((k + 1) * sizeof(int));
cq->k = k;
cq->front = cq->tail = 0;
return cq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
// Insert judgment is not full
if (myCircularQueueIsFull(obj)) {
return false;
}
obj->a[obj->tail] = value;
obj->tail++;
// return to the corresponding position in the array
obj->tail %= obj->k + 1;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
// delete the judgment is not null
if (myCircularQueueIsEmpty(obj)) {
return false;
}
obj->front++;
obj->front %= obj->k + 1;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj)) {
return - 1;
}
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj)) {
return - 1;
}
/* if (obj->tail == 0) return obj->a[obj->k]; else return obj->a[obj->tail - 1]; * /
int i = (obj->tail + obj->k) % (obj->k + 1);
return obj->a[i];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
/* if (obj->tail == obj->k) return obj->front == 0; else return obj->tail + 1 == obj->front; * /
return obj->tail % (obj->k + 1) == obj->front;
//tail % (K + 1) + 1 == front
}
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
free(obj->a);
free(obj);
}
Copy the codeArray implementations must consider subscript overflow. When the subscript is in the array, the magnitude of the array length is not affected. When the subscript overflows, the magnitude of the array length is returned to the corresponding position in the array.
The subscript overflows by a few units, modulo equals the length of the array and returns to the number of digits in the array.
Linked list implementation
/** * struct definition **/
typedef int SLTDataType;
typedef struct SLTNode {
SLTDataType data;
struct SLTNode* next;
}SLTNode;
typedef struct {
SLTNode* head;
SLTNode* tail;
int k;
} MyCircularQueue;
/** * interface function definition **/
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
if (pq == NULL)
exit(- 1);
pq->k = k;
// create a linked list
pq->head = SListNewNode();
pq->tail = pq->head;
while (k--) {
pq->tail->next = SListNewNode();
pq->tail = pq->tail->next;
}
// end to end
pq->tail->next = pq->head;
// Initialize the pointer
pq->tail = pq->head;
return pq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if (myCircularQueueIsFull(obj)) {
return false;
}
SListInsert(obj->tail, value);
obj->tail = obj->tail->next;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj)) {
return false;
}
obj->head = obj->head->next;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj)) {
return - 1;
}
return obj->head->data;
}
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if (myCircularQueueIsEmpty(obj)) {
return - 1;
}
SLTNode* cur = obj->head;
while(cur->next ! = obj->tail) { cur = cur->next; }return cur->data;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
return obj->tail->next == obj->head;
}
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
SLTNode* cur = obj->head;
while(cur->next ! = obj->head) { SLTNode* next = cur->next;free(cur);
cur = next;
}
free(cur);
free(obj);
}
Copy the code