Basic operation of stack (implemented in C language)

The end of the term is finally over , Next, we will continue to update the content related to the data structure , This article brings the data structure —— Stack , To realize its basic functions .

The difficulty is low , Because we have implemented the sequence table before , Stack is just a special form of sequential table .

One 、 Concept and structure of stack

Concept ： Stack is a special linear table , It only allows insertion and deletion at the fixed end . The end for data insertion and deletion is To the top of the stack , The other end is At the bottom of the stack . Data elements in the stack comply with last in, first out (Last In First Out) Principles .

Pressing stack ： Stack insertion is called stack entry / Pressing stack / Push , That is, insert data from the top of the stack .

Out of the stack ： The deletion of the stack is called out of the stack , That is, delete data from the top of the stack .

---

Two 、 Framework Definition of stack

Stack implementation can use arrays and linked lists , Relatively speaking, the implementation of array structure is better , Because the cost of inserting data on the tail of the array is less , The characteristics of array are more consistent with the characteristics of stack .

Next, let's take a look at the type definition of our stack and the functions we want to implement this time .

#pragma once 
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;			// Identify the data at the top of the stack 
	int capacity;		// Dynamic    If there is not enough space, expand the capacity 
}ST;

void StackInit(ST* ps);            // Initialization of stack 
void StackDestory(ST* ps);         // Destruction of the stack 
void StackPush(ST* ps, STDateType x); // Stack insertion 
void StackPop(ST* ps);           // Delete data 
STDateType StackTop(ST* ps);	// Take the element at the top of the stack 
bool StackEmpty(ST* ps);		// Judge whether the stack is empty 
int StackSize(ST* ps);			// Know the stack size 

---

3、 ... and 、 Function implementation of stack

3.1 Initialization of stack

When we create a custom stack variable , The first thing is the initialization of variables .

// Initialization of stack 
void StackInit(ST* ps)
{
	assert(ps);       
	ps->a = NULL;        
	ps->top = 0;
	ps->capacity = 0;
}

3.2 Destruction of the stack

Stack destruction is equivalent to the release of stack space and the deletion of data , In fact, it is similar to initialization , Initialization is also implemented here .

// Destruction of the stack 
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.3 insert data

The key functions of the stack . First , Determine whether our stack needs to be expanded ; Then insert the data at the top of the stack ; Finally, move the top of the stack up .

There are two situations ：① Initial set stack top top by 0, namely Top=0, So we insert the data first , And then Top Move up .② If we initially set the top of the stack to -1, namely Top=-1, Then we should insert data first +1, Then put the data into . Here we use the first way . 

// insert data 
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	// If top Equal to the current capacity , Then expand the capacity 
	if (ps->capacity == ps->top)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* temp = (STDateType * )realloc(ps->a, sizeof(STDateType) * NewCapacity);
		if (temp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity = NewCapacity;
	}
    // Place the value on the stack .
	ps->a[ps->top] = x;
    //Top Move up 
	ps->top++;
}

3.4 Delete data

Deleting data is very simple , The natural advantage of arrays , Just move the top of the stack down one unit .

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

3.5 Take the top element of the stack

STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

3.6 Empty stack

We don't use here if Sentence judgment , Go straight back to ps->top==0 This code , Will automatically determine whether it is true or false . If top==0, Will directly return true, concise 、 convenient .

bool StackEmpty(ST* ps)
{
	assert(ps);
    // Return the expression directly .
	return ps->top == 0;
}

3.7 The size of the stack

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

---

Four 、 Function display

  Here we try to insert data and output it all , These will use all the functions above , To check whether these functions are successful .

  Pay attention here , The stack cannot be traversed , If we want to print the data in the stack , To print a stack top element , Then pop it up , Stop the operation until the stack is empty .

5、 ... and 、 summary

For the stack, we need to understand its functions and characteristics , Some of the details we don't have to worry about , What we care about is its structure and characteristics .

Stack is widely used , Here we use array to realize stack , It is because the characteristics of array are very helpful to realize the characteristics of stack , If you have implemented the sequence table before, you will find that the stack implementation is very similar to the sequence table , Because the stack itself is a special type of sequential table . If you have time, you can try to use the linked list to realize the stack , If you have implemented a single linked list before , It's not too hard .

---

well , That's the end of this article , Feel your reading , The next article will bring queue Basic function realization of , See you next time .