Shulou(Shulou.com)06/03 Report--

This article mainly introduces "detailed explanation of stack and queue of C language data structure". In daily operation, I believe that many people have doubts about the stack and queue of C language data structure. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the questions of "detailed interpretation of C language data structure stack and queue"! Next, please follow the editor to study!

Catalogue

Stack

Array implementation

Title full code

Stack_array.c

Stack_array.h

Initialize array stack

Expand capacity after full stack

Whether the stack is empty

Stack pressing and unstacking

Linked list implementation

Stack_chain.h

Stack_chain.c

The whole stack pressing process

The whole process of bomb stack

Out of stack situation

Queue

Implementation of queues

Queue_chain.h

Queue_chain.c

A structure type is used to maintain this queue

Concept flow chart

Implementation of queuing

Implementation of dequeuing

Whether the team is empty or not

Stack

Stack is a data structure in which objects are added or deleted sequentially in the order of LIFO.

Memorizing the stack vividly is like a pile of books or plates on a table. To take or save a plate, you can only operate on the top book or plate.

As far as the stack is concerned, only the bullet stack can get its data.

When we use C language to implement the stack data structure.

In fact, there are three ways to do this.

1, array

2, single linked list

3, two-way linked list

However, for a two-way linked list, the implementation stack is too complex.

You can choose an array or a single linked list.

The array implements initialization of all header codes Stack_array.c#include "Stack_array.h" void InitStack (STstack* st) / / stack {st- > top = 0; st- > arr = (STData*) malloc (CAP*sizeof (STData)); st- > capacity = CAP } void StackPush (STstack* st, STData n) / / element into the stack {if (st- > top = = st- > capacity) / / determine whether to expand {StackExpansion (st);} st- > arr [st-> top++] = n;} STData StackPop (STstack* st) / / element unstack {assert (st); assert (! StackEmpty (st)) / determine whether the stack is empty return st- > arr [--st- > top];} int StackEmpty (STstack* st) / / determine whether the stack is empty {if (st- > top = = 0) return 1; return 0;} void StackDestory (STstack* st) / / destroy the stack to prevent memory leaks {free (st- > arr); st- > arr = NULL } void StackExpansion (STstack* st) / / capacity expansion {STData* tmp = (STData*) realloc ((STData*) st- > arr, sizeof (STData) * (st- > capacity) * 2); if (tmp = = NULL) {printf ("Exparsion Error\ n"); exit (- 1);} st- > arr = tmp; st- > capacity * = 2 } void StackPrint (STstack* st) / / prints the elements of the stack, but only if you unwind the stack to get the element {while (st- > top) {STData ret = StackPop (st); printf ("% d", ret);}} Stack_array.h#pragma once#define _ CRT_SECURE_NO_WARNINGS#include # define CAP 4typedef int STData The typedef struct Stack// structure is used to maintain the capacity of the pointer int capacity;// stack marked at the top of the int top;// stack} STstack;void InitStack (STstack* st); / / initialization void StackPush of the stack (STstack* st, STData n); / / element on-stack STData StackPop (STstack* st); / / element unstack void StackExpansion (STstack* st); / expansion int StackEmpty (STstack* st) / / determine whether the stack is empty void StackDestory (STstack* st); / / destroy the stack to prevent memory leakage of void StackPrint (STstack* st); / / print the elements of the stack, but only if you unwind the stack to get the elements

For array implementations. Create a structure to maintain the entire stack. One of them is an array for link creation.

The typedef int STData;typedef struct Stack// structure is used to maintain the stack {the capacity of the pointer STData* arr;// stack marked at the top of the int top;// stack} STstack

As an array stack, you need a dynamic array. Then this requires a Capacity as a measure of the need for expansion. The top needs to be the location of the stack element.

When the value of top equals Capacity, it means that the stack is full. Because the array starts at 0.

Initialize array stack

During initialization, an array space should be opened dynamically, and the top should be set to 0. 0 when the data elements are not pushed into the stack. Make sure that there is a clearly specified space when you need to push the stack. At the same time, the position of the top should be the next subscript that is last pressed into the data.

Initialization of void InitStack (STstack* st) / / stack {st- > top = 0; st- > arr = (STData*) malloc (CAP*sizeof (STData)); st- > capacity = CAP;} expand capacity after full stack

Its Capacity should be used as a criterion to judge whether the stack is full or not. In addition, it is necessary to expand the capacity after the full stack (because it is a dynamic array).

Void StackExpansion (STstack* st) / / capacity expansion {STData* tmp = (STData*) realloc ((STData*) st- > arr, sizeof (STData) * (st- > capacity) * 2); if (tmp = = NULL) {printf ("Exparsion Error\ n"); exit (- 1);} st- > arr = tmp; st- > capacity * = 2;}

At the same time, the capacity of the stack should be changed each time as a standard for whether the stack is full next time.

Whether the stack is empty int StackEmpty (STstack* st) / / determines whether the stack is empty {if (st- > top = = 0) return 1; return 0;}

Whether it is empty. That is, the position of top is in the 0 subscript of the array.

Push and unstack void StackPush (STstack* st, STData n) / / elements into the stack {if (st- > top = = st- > capacity) / / determine whether to expand {StackExpansion (st);} st- > arr [st-> top++] = n;} STData StackPop (STstack* st) / / element unstack {assert (st); assert (! StackEmpty (st)) / / determine whether it is empty stack return st- > arr [--st- > top];}

Press the stack

Each time you press the stack, you need to judge whether the stack is full and decide whether to expand the capacity.

At the same time, when the assignment is made at the number position of the original top position. And then move the top back one position. Make sure to push the stack next time.

Unstack

Unstack returns the element in the previous position of the top. At the same time, top moves forward one position, does not need free, the next stack will be automatically overwritten.

The linked list implements stack_chain.h#include # include # define N 3typedef struct stackele {int n; int* point;} sta;sta* top;void initstack (sta* a); / / initializes the stack void pushstack (sta* aint num); / / stacks / / void printstack (sta* a); / / prints the stack / / void fullstack (sta* a); / / checks whether the stack is full void emptystack (sta* a) / / check whether the stack is empty int popstack (sta*a); / / stack_chain.c#include "stack_chain.h" void initstack (sta*a) / / initialize the stack {top= NULL;} void pushstack (sta*a, int num) / / enter the stack {sta* p = (sta*) malloc (sizeof (sta)); p-> n = num;// new node assignment p-> point = top; top= p } int popstack (sta* a) / / check whether the stack is empty int date; sta* des = top; top = top- > point; date = des- > n; free (des); des = NULL; return date } void emptystack (sta* a) / / check whether the stack is empty {if (top = = NULL) {printf ("Stack empty"); exit (0);}}

For a linked list implementation stack, it is actually similar to an array. It is not enough, each stack needs to dynamically open up a new node, and link into the stack. However, this is not an ordinary direct link. Instead, the head needs to be inserted into the stack.

In this way, the header is inserted into the stack so that you can find the previous element when you exit the stack. Pressing the stack does not require any order. Each stack node is the top node.

The whole stack pressing process

Void pushstack (sta* a, int num) / / stacks {sta* p = (sta*) malloc (sizeof (sta)); p-> n = num;// new node assignment p-> point = top; top = p;} the whole stack flow

Int popstack (sta* a) / / check whether the stack is empty int date; sta* des = top; top = top- > point; date = des- > n; free (des); des = NULL; return date;}

In particular, we should grasp one condition: empty stack

Because it is not an array, and the chain structure of the characteristics, there is no need for expansion. That is, there is no need to judge the situation of the full stack.

Only consider the condition of empty stack

Void emptystack (sta* a) / / check whether the stack is empty {if (top = = NULL) {printf ("Stack empty"); exit (0);}}

The condition for an empty stack here is that when the top pointer points to NULL, that is,

Why?

Because each time you hit the stack, you free the space that top points to and then let top point to the next node. Just keep moving. But my design initialization is top= NULL; and every stack push is p-> point = top;, so there is a standard to limit the empty stack.

For the stack, it is more like a recursive representation.

Queue

This data structure is like a number-taking machine at the bank counter.

Those who take the number first go to the counter first.

Always satisfy the concept of first-in, first-out

Implementation of the queue queue_chain.h#define _ CRT_SECURE_NO_WARNINGS#include # include # include typedef int QUData;typedef struct queue {QUData data; struct queue* next;} queue;typedef struct Queue// structure is used to maintain the queue {queue* Dequeue;// queue header pointer queue* Enqueue;// queue tail pointer} QUqueue;void InitQueue (QUqueue* qu); / / initialization void QueuePush of the stack (QUqueue* qu, QUData n) / / element QUData QueuePop (QUqueue* qu); / element dequeue int QueueEmpty (QUqueue* qu); / / determine whether the queue is empty void QueueDestory (QUqueue* qu); / / destroy the queue to prevent memory leaks void QueuePrint (QUqueue* qu) / / print the elements in the queue, but only if you leave the queue can you get the initialization of the element queue_chain.c#include "queue_chain.h" void InitQueue (QUqueue* qu) / / queue {qu- > Dequeue = qu- > Enqueue = NULL;} void QueuePush (QUqueue* qu, QUData n) / / element join the queue {queue* newcell = (QUData*) malloc (sizeof (QUData)); newcell- > data = n; newcell- > next = NULL If (qu- > Dequeue = = NULL) {qu- > Enqueue = qu- > Dequeue = newcell;} else {qu- > Enqueue- > next = newcell; qu- > Enqueue = newcell }} QUData QueuePop (QUqueue* qu) / / element dequeue {if (QueueEmpty (qu)) {printf ("Queue Is Empty"); exit (- 1);} QUData ret = qu- > Dequeue- > data; qu- > Dequeue = qu- > Dequeue- > next; return ret } int QueueEmpty (QUqueue* qu) / / determine whether the queue is empty {if (qu- > Dequeue = = qu- > Enqueue) return 1; return 0;} void QueueDestory (QUqueue* qu) / / destroy team to prevent memory leakage {queue* cur = qu- > Dequeue; while (cur) {queue* pnext = cur- > next; free (cur) Cur = pnext;} qu- > Dequeue = qu- > Enqueue = NULL;} void QueuePrint (QUqueue* qu) / / print queue element {queue* cur = qu- > Dequeue; while (cur) {printf ("% d", cur- > data); cur = cur- > next;}}

After all, the team is a first-in, first-out data structure.

So we need two pointers.

Qu- > Dequeue points to the head of the line

Qu- > Enqueue points to the end of the line

Otherwise, it would be a waste of time to find the end of the line every time.

A structure type is used to maintain the queue typedef int QUData;typedef struct queue// describes the elements of each team {QUData data; struct queue* next;} queue;typedef struct Queue// structure is used to maintain the queue {queue* Dequeue;// team head pointer queue* Enqueue;// team tail pointer} QUqueue

The team leader pointer is responsible for coming out of the team.

The pointer at the end of the line is responsible for joining the team.

Concept flow chart

Join the team

Queue implementation void QueuePush (QUqueue* qu, QUData n) / / elements join the queue {queue* newcell = (QUData*) malloc (sizeof (QUData)); newcell- > data = n; newcell- > next = NULL; if (qu- > Dequeue = = NULL) {qu- > Enqueue = qu- > Dequeue = newcell;} else {qu- > Enqueue- > next = newcell Qu- > Enqueue = newcell;}}

* * of course, at the beginning of the queue, the head and tail pointers are still pointing to NULL.

When you enter the first element, that element is both the first and the last element. You have to judge independently. * * this is a special case.

Get out of the team

Implementation QUData QueuePop (QUqueue* qu) / / element out of queue {if (QueueEmpty (qu)) {printf ("Queue Is Empty"); exit (- 1);} QUData ret = qu- > Dequeue- > data; qu- > Dequeue = qu- > Dequeue- > next; return ret;}

But every time you get out of the queue, you need to judge whether it is an empty team. If the empty team continues to leave the team, it will be equivalent to NULL- > next, which is a direct error.

So there is also a function to determine whether the team is empty.

Whether the queue is empty int QueueEmpty (QUqueue* qu) / / determine whether the queue is empty {if (qu- > Dequeue = = qu- > Enqueue) return 1; return 0;}

The empty team is equivalent to going back to the initialization situation.

Qu- > Dequeue = qu- > Enqueue = NULL

That is, both point to the same place, that is, NULL.

At this point, the study of "detailed explanation of stack and queue of C language data structure" is over. I hope to be able to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.