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

In this article, the editor introduces in detail "how to realize stack and queue in C language". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to implement stack and queue in C language" can help you solve your doubts. Let's follow the editor's ideas to learn new knowledge.

What is a stack?

Stack: a special linear table that only allows inserts and deletions of elements at a fixed end. One end of the data insertion and deletion 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 principle of first in, then out LIFO (Last In First Out).

Stack pressing: the insertion operation of the stack is called entering the stack / pressing the stack / entering the stack, and the input data is at the top of the stack.

Out-of-stack: the delete operation of the stack is called off-stack. The output data is also at the top of the stack.

Structure diagram of stack

Implementation of stack

Generally, the implementation of stack can be implemented by array or linked list, which is better than the structure of array. Because the cost of inserting data at the end of an array is relatively small.

Create the structure of the stack

When we use a stack to store data, we first need to implement a dynamically growing stack. So let's first create a stack structure.

Typedef int STDataType;typedef struct Stack {STDataType* a; int top; / / Top int capacity; / / capacity} Stack; initialization stack

There are many ways to initialize the stack, which we can choose according to different requirements. Write a regular one here.

Void StackInit (Stack* ps) {assert (ps); / / check whether the passed ps is empty ps- > a = NULL;// set the space identified by a to empty ps- > top = ps- > capacity = 0;} enter the stack

At first, top is 0 to identify the location of the top of the stack, so we need to put the data on the top of the stack first, and then let top go back one bit.

Void StackPush (Stack* ps, STDataType x) {assert (ps); / / check whether ps is empty / / if the space is full, we need to expand if (ps- > capacity = = ps- > top) / / the condition {int newCapacity = ps- > capacity = = 0? 4: ps- > capacity * 2 to determine whether the space is full / / specify the size of the new space ps- > a = (STDataType*) realloc (ps- > a, newCapacity*sizeof (STDataType)); / / expand if (ps- > a = = NULL) / / failed {printf ("realloc fail\ n"); exit (- 1) / / Terminator} ps- > capacity = newCapacity;// let it identify the size of the new space} ps- > a [PS-> top] = Xing Bang / put the data on the stack ps- > top++;//top step back} out of the stack void StackPop (Stack* ps) {assert (ps) If (ps- > top > 0) / / avoid that the data in the stack has been deleted, and the top is still reduced to negative {--ps- > top;}} to get the top element STDataType StackTop (Stack* ps) {assert (ps); assert (ps- > top > 0); / / ensure that the subscript is positive return ps- > a [PS-> top-1] / / return the elements at the top of the stack} to get the number of valid elements in the stack int StackSize (Stack* ps) {assert (ps); return ps- > top;} check whether the stack is empty

Check whether the stack is empty, return a non-zero result if empty, and return 0. 0 if it is not empty.

Bool StackEmpty (Stack* ps) {assert (ps); return ps- > top = = 0 True / return true if the condition is true, otherwise it will be false (not empty)} stack destroy void StackDestroy (Stack* ps) {assert (ps); free (ps- > a); / / release the opened space ps- > a = NULL; ps- > top = ps- > capacity = 0;} what is a queue?

Queue: a special linear table that only allows inserting data at one end and deleting data at the other end. The queue has first-in-first-out FIFO (First In First Out) into the queue: the end of the insert operation is called out of queue at the end of the queue and the end of the delete operation is called a peer.

Implementation of queues

Queues can also be implemented with array and linked list structures, and it is better to use linked list structures, because if you use an array structure, it is less efficient to put data out of the queue on the head of the array.

Create a queue structure

We use linked lists to implement queues, and we need to create a structure that stores queue information.

Typedef int QDataType;// chained structure: represents the structure of the queue typedef struct QueueNode {QDataType data; / / Storage data struct QueueNode* next; / / pointer Domain} QNode;// queue typedef struct Queue {QNode* head;// identifies the location of the head of the queue QNode* tail;// identifies the location of the end of the queue} Queue; initialization queue void QueueInit (Queue* pq) {assert (pq) Pq- > head = pq- > tail = NULL;// set two pointers to null} queue tail into queue

To get a data into the queue, we only need to use the linked list structure to implement the queue and insert the data at the end of the queue.

If the queue is empty, it needs to be handled separately.

Void QueuePush (Queue* pq, QDataType x) {assert (pq); QNode* newnode = (QNode*) malloc (sizeof (QNode)); / / apply for a new node assert (newnode); / / check whether the node has been successfully applied newnode- > data = xamp / newnode- > next = NULL If (pq- > tail = = NULL) / / if the queue is empty {assert (pq- > head==NULL); pq- > tail = pq- > head= newnode;} else// queue is not empty {pq- > tail- > next = newnode;// insert a new node pq- > tail = newnode / / position at the end of the update}} head of the line leaving the queue

When the queue is empty and there is no data stored, we cannot output the data. If there is only one node in the queue, then we need to deal with it separately, otherwise an error will occur.

Void QueuePop (Queue* pq) {assert (pq); assert (pq- > head & & pq- > tail); / / make sure there is data in the queue going down if (pq- > head- > next = = NULL) / / if there is only one data in the queue {free (pq- > head); / / release the queue head data pq- > head = pq- > tail = NULL / / set the header pointer and tail pointer of the queue to null} else {QNode* next = pq- > head- > next;// and let next point to the next node free (pq- > head) of the queue head node; / / release the queue head node pq- > head = next;// and let head point to the next node}} to get the queue header element

Check whether the queue is empty, and if not, return directly to the element pointed to by the queue header pointer.

QDataType QueueFront (Queue* pq) {assert (pq); assert (pq- > head); / / check whether the queue is empty return pq- > head- > data;// return queue header element} get the queue tail element

Check whether the queue is empty, and if not, directly return the element pointed to by the pointer at the end of the queue.

/ / get QDataType QueueBack (Queue* pq) {assert (pq); assert (pq- > tail); / / check whether the queue is empty return pq- > tail- > data;// return queue tail element} get the number of elements in the queue

You can traverse the queue to count the number of elements, and this method is inefficient if the queue is long. If we want to be efficient, we can add a size variable when defining the queue structure, count each data into the queue, and return directly when we need the number of elements in the queue.

Int QueueSize (Queue* pq) {assert (pq); QNode* cur = pq- > head;// lets cur point to the element at the head of the line, size_t size= 0bank / define an unsigned size variable to count while (cur) / / if cur is not empty, enter the loop and continue to execute {size++;//size=size+1 cur = cur- > next / / continue to traverse backwards} return size;// to return the number of valid elements} to check whether the queue is empty

Check whether the queue is empty, return a non-zero result if it is empty, and return 0 if it is not empty

Bool QueueEmpty (Queue* pq) {assert (pq); return (pq- > head = = NULL) & & (pq- > tail = = NULL);} destroy the queue

After using the queue, we should destroy it to prevent memory leaks.

Void QueueDestroy (Queue* pq) {assert (pq); QNode* cur = pq- > head; while (cur) {QNode* next = cur- > next;// define a next pointing to cur's next node free (cur); / / release cur cur = next;} pq- > head = pq- > tail = NULL / / leave both the head and tail pointers empty}. This article "how to implement Stack and queue in C language" has been introduced here. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. 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.