[Data Structures] Stacks in Linear Tables (C — Sequential Table Implementation of Stacks)

=========================================================================

Relevant code gitee self retrieve：

C Learning Diary: Work Harder (gitee.com)

 =========================================================================

follow up on previous period：

Data Structure Beginner] IV. Chain Table in Linear Table (with head + bidirectional + cyclic chain table — C language implementation)_Tall Fatty’s Blog – Blogs

 =========================================================================

                     

1 . Stack

The concept and structure of a stack:

The concept of a stack

• one kind ofSpecial Linear TablesitsIt is only allowed in thesettled endcarry outstickandDelete Element Operation
                     
• carry outOne end of data insertion and deletion operations call sth (by a name)stack top (computing)，topcall sth (by a name)the bottom of a stack
                  
• Data elements in the stackcomply with
  come late and leave first（LIFO — Last In First Out(used for emphasis)formula — Elements that come in later will come out first

               

push on and off the stack

• Stack insertion operationsbe known aspush on/bonded warehouse/push on — Push
  data entryinstack top (computing)
                 
• Deletion operations on the stackbe known assend a package to a warehouse— Pop
  dispose of dataalso instack top (computing)

                    

The structure of a stack

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . Stack implementation

                   

utilizationorder list(arrays) orlinked list(chain structure) Both can realize the stack，

utilizationlinked listIf you do, you canutilization Tail Plug (Header Plug)andTail Deletion (Head Deletion)realization LIFO of the stacks.，

（ tail plug — bonded warehouse        ；      padded, sleeveless undergarment worn by men— send a package to a warehouse ）

utilizationorder listThe same can be done using the tail plugandpadded, sleeveless undergarment worn by men realization，

butorder listtheTail plug and tail delete operate more efficiently，Cache utilization is also higher when processing data，

the reason whyThe following sequence table is used(arrays)implementation stack：

               

(Detailed explanations are in the notes to the pictures, and the code subfile is placed under a heading)

               

Preparation for the realization of specific functions

• incorporateWe’ll need it later.header function
                             
• establishstack data type (computing) — a warehouseTypes of stored data
               
• establishstack structure (computing)(typology) — within a typeproperPointer to an element on the control stack、top-of-stack value、stack size (computing)

icon

            

            

———————————————————————————————

            

STInit function — initializes the stack type

• assertStack type pointer not null
             
• willPointer to control elements on the stackEmpty.，
  generalStack capacity (size)Set to 0，
  generaltop-of-stack valueDefined as 0

icon

            

            

———————————————————————————————

            

STDestroy function — destroys the stack type

• assertStack type pointer not null
             
• liberate (a prisoner)Pointer to control elements on the stackandbe empty，
  stack capacitySet to 0，
  top-of-stack valueSet to 0

icon

            

            

———————————————————————————————

            

STPush function — performs stack pressing

• assertStack type pointer not null
             
• warehouseOpening up dynamic spacesandcarry out an examination
               
• after opening up successfully，Pointer to control elements on the stackPointing to open space，
  retrievecapacity Stack capacity
                 
• willvalue of the stack（x）put into a stack
               
• alignTop of stack value “subscript” toptheposition

icon

            

            

———————————————————————————————

            

STPop function — performs a stack out

• assertStack type pointer not null，
  assertthe stack is not empty
             
• theMove the top of the stack down one unitcan immediately (do sth)Realization of “deletion”（send a package to a warehouse）

icon

            

            

———————————————————————————————

            

STTop function — get the top element of the stack

• assertStack type pointer not null，
  assertthe stack is not empty
             
• Returns the top element of the stack

icon

            

            

———————————————————————————————

            

STSize function — calculates the number of elements in the stack.

• assertStack type pointer not null
             
• Returns the topnamelyNumber of elements in the stack

icon

            

            

———————————————————————————————

            

STEmpty function — determines whether the stack is empty or not

• assertStack type pointer not null
             
• judgmenttopWhether or not it is empty，
  istheReturns true，notheReturns false

icon

            

            

———————————————————————————————

            

Overall test:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . Corresponding code

Stack.h — stack header file

#pragma once

// Include the header files needed afterward:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// Dynamic order table:

// Define the top data element of the stack:
typedef int STDataType;
  
// Define the stack type:
typedef struct Stack
{
	// Header pointer when opening dynamic space for the stack:
	// Pointer to control elements on the stack
	STDataType* a;

	// Top-of-stack value (used to define the top of the stack):
	int top;
	// Similar to array subscripts

	// Stack storage data capacity (size of the stack):
	int capacity;

}ST; // rename to ST


// Static order list:
//define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//};


// Initialize Stack Functions -- Initialize Stack Types
// Receive a pointer to the stack type
void STInit(ST* ps);

//Destroy Stack Functions -- Destroy Stack Types
// Receive a pointer to the stack type
void STDestroy(ST* ps);

// Because there are only stack press and stack out operations
// only operates on the top element of the stack, so there is no
// Header insertion (tail insertion) Header deletion (header deletion) and other operations

// Stacking function -- performs stacking
// Receive a pointer to the stack type（ps）、进行压栈的值（x）
void STPush(ST* ps, STDataType x);

// Stack out function -- performs a stack out
// Receive a pointer to the stack type
void STPop(ST* ps);

//Top-of-stack element function -- get top-of-stack element
// Receive a pointer to the stack type
STDataType STTop(ST* ps);

//Elements on Stack Function -- Calculates the number of elements on the stack.
// Receive a pointer to the stack type
int STSize(ST* ps);

// Empty function -- determine whether the stack is empty.
// Receive a pointer to the stack type
bool STEmpty(ST* ps);

            

            

———————————————————————————————

                

Stack.c — Stack function implementation file

#define _CRT_SECURE_NO_WARNINGS 1

// Include stack header files:
#include "Stack.h"

// Initialize Stack Functions -- Initialize Stack Types
// Receive a pointer to the stack type
void STInit(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);

	// Set the stack element control pointer to null:
	ps->a = NULL;
	// Set the stack capacity (size) to 0:
	ps->capacity = 0;
	// Define the top-of-stack value as 0:
	ps->top = 0;
}



//Destroy Stack Functions -- Destroy Stack Types
// Receive a pointer to the stack type
void STDestroy(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);

	// Release the element control pointer on the stack:
	free(ps->a);
	// and set it to null:
	ps->a = NULL;
	// Stack capacity is set to 0:
	ps->capacity = 0;
	//Top-of-stack value set to 0:
	ps->top = 0;
}



// Stacking function -- performs stacking
// Receive a pointer to the stack type（ps）、进行压栈的值（x）
void STPush(ST* ps, STDataType x)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);

	// Open up dynamic space for the stack:
	if (ps->top == ps->capacity)
		//Top-of-stack value equals stack size
		//Indicates that there is not enough space and needs to be expanded
	{
		//Only when the stack is pressed, the capacity will increase and may need to be expanded.
		// Only this function will perform the expansion operation, the
		// So there's no need to write a separate expansion function
		
		//Expansion.
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		// Because the stack capacity capacity is initialized to 0.
		// So it's possible to use the triple-eye operator for augmentation:
		//ps->capacity == 0 ? 4 : ps->capacity * 2
		// if 0 then directly increase capacity to 4, if not 0 then increase capacity 2 times
	
		// Open up dynamic space:
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity);
		// Here, realloc is used directly for dynamic space opening.
		// If the realloc function receives the header pointer (first argument) as null, the
		// Then it is equivalent to the malloc function

		//Checks on opening space:
		if (tmp == NULL)
			// Returns a null pointer and fails to open:
		{
			// Print the error message:
			perror("realloc fail");
			// Terminate the program:
			exit(-1);
		}

		// Upon successful opening.
		// The element control pointer inside the stack points to the open space:
		ps->a = tmp;
		
		// Reset the capacity stack:
		ps->capacity = newCapacity;
	}

	// Put the value of the press (x) on the stack:
	ps->a[ps->top] = x; 
	// The above opens a contiguous space starting with a.
	// So a can be seen as an array name using (?)
	//Put values through array subscripts
	
	//Adjust the "subscript" position of the top stack value again:
	ps->top++;
}



// Stack out function -- performs a stack out
// Receive a pointer to the stack type
void STPop(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);
	//assert asserts that the top of the stack can't continue out of the stack once the top of the stack reaches the bottom of the stack
	assert(ps->top > 0); // stack is not empty

	//Out as long as the top of the stack is--
	//Move the top of the stack down one unit to "delete" (out of the stack):
	--ps->top;
}



//Top-of-stack element function -- get top-of-stack element
// Receive a pointer to the stack type
STDataType STTop(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);
	//assert can't find the top element of the stack if it asserts that the stack is empty
	assert(ps->top > 0);

	// Returns the top element of the stack:
	return ps->a[ps->top - 1];
	//top is the number of elements in the stack:
	//top starts at 0, top++ after stacking, assignment then++
	//top is always at the next position of the top element of the stack
	// So to get the top element of the stack we need top-1 to the top element of the stack.
}



//Elements on Stack Function -- Calculates the number of elements on the stack.
// Receive a pointer to the stack type
int STSize(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);

	//top is the number of elements in the stack:
	//top starts at 0, top++ after stacking, assignment then++
	//top is always at the next position of the top element of the stack
	return ps->top;
}



// Empty function -- determine whether the stack is empty.
// Receive a pointer to the stack type
bool STEmpty(ST* ps)
{
	//assert asserts that the stack type pointer is not null:
	assert(ps != NULL);

	// If top is 0
	//States that there are no elements in the stack
	return ps->top == 0; 
	//top is 0 -> stack is empty -> return true
	//top not 0 -> stack not empty -> return false
}

            

            

———————————————————————————————

                

Test.c — stack test file

#define _CRT_SECURE_NO_WARNINGS 1

// Include stack header files:
#include "Stack.h"

// Test function:
void TestStack()
{
	// Create a stack type:
	ST st;
	// Initialize it:
	STInit(&st);
	// Add elements to the stack using a pressure stack:
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);
	//Elements larger than 4 are expanded again

	// Print the number of elements in the current stack:
	printf("The current number of elements on the stack is: %d\n", STSize(&st));
	// Line breaks:
	printf("\n");

	// Use a while loop:
	// Print the top element of the stack and exit the stack again, looping this operation:
	// Prove the LIFO principle for stacks
	while (!STEmpty(&st))
		// Continue the operation if the chain table is not empty:
	{
		// Print the current top stack element:
		printf("Top element of the stack before going out: %d\n", STTop(&st));

		// Perform a stack out:
		STPop(&st);
	}

	// Line breaks:
	printf("\n");
	// Print the number of elements in the current stack:
	printf("The current number of elements on the stack is: %d", STSize(&st));

	// Perform destruction:
	STDestroy(&st);
}

// Main function
int main()
{
	TestStack();

	return 0;
}