Representation and implementation of stack (C language)

Catalog

The concept and structure of stack

The realization of the stack

Stack.h

Stack.c

main.c Test interface

---

The concept and structure of stack

   Concept

Stacks are a special kind of The linear table , It is only allowed in The fixed end Insert and delete elements .

   structure

The end that performs data insertion and deletion operations is called To the top of the stack , The other end is called the bottom of the stack .

The data elements in the stack follow Last in, first out Principles .

Pressing stack ： The insertion operation of the stack is called Into the stack / Pressing stack / Push , The input data is at the top of the stack .

Out of the stack ： The deletion of the stack calls out the stack . The output data is also at the top of the stack .

---

Exercises

  The problem is very simple , The data element rule of stack is LIFO , In this group of elements ,E It came in last, so it went out first , The second is the element D.                So choose B

The stack can be thought of as a pipe , You put something into the pipe through the mouth , After that, if you still want to put things, do you still need to put them in from the pipe mouth ？ Then the things you put in for the first time are closer to the inside , You must take something from the position near the pipe mouth before you take it .

When convenient for learning , It can also be regarded as a clip .

---

  The answer to this question is C.

A Middle order ：1 Into the --1 Out --234 In and out --4 Out --3 Out --2 Out

B Middle order ：12 Into the --2 Out --3 Into the --3 Out --4 Into the --4 Out --1 Out

D Middle order ：123 Into the --3 Out --4 Into the --4 Out --2 Out --1 Out

---

The realization of the stack

It is recommended to use array to realize stack

Let's see what specific requirements of the stack need to be implemented .

---

Stack.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps); // initialization 
void StackDestory(ST* ps); // The destruction 
void StackPush(ST* ps, STDataType x); // Push 
void StackPop(ST* ps);  // Out of the stack 

STDataType StackTop(ST* ps); // Back to top of stack element 

int StackSize(ST* ps); // Find the number of stack data 
bool StackEmpty(ST* ps); // Judge whether the stack is empty 

Some explanations ：

#pragma once It's precompiling

Header file assert Is the header file of type assertion , Assertion function assert(), The code below the program is executed only when it is judged to be true in parentheses

Defined structure ,top It's the top of the stack pointer ,capacity It's capacity （ When not enough, increase capacity ）

The following is the specific implementation of each interface

---

Stack.c

#include"Stack.h"

void StackInit(ST* ps) // initialization 
{
	assert(ps); // Structure pointer cannot be null 
	ps->a = malloc(sizeof(STDataType)*4); // Dynamic memory opens up space 
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0 ;  // If top to 0 It means that it points to the next element at the top of the stack  ; -1 Indicates the element pointing to the top of the stack 
}

void StackDestory(ST* ps) // The destruction 
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x) // Push 
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)  // Out of the stack 
{
	assert(ps);
	// The stack is empty , call Pop, Directly abort the program and report an error 
	assert(ps->top > 0);
	ps->top--;
}

STDataType StackTop(ST* ps) // Back to top of stack element 
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps) // Judge whether the stack is empty 
{
	assert(ps);
	return ps->top == 0;
}

---

main.c Test interface

#include<stdio.h>
#include"Stack.h"
int main()
{
	ST st; // Declare a structure variable 
	StackInit(&st);// Initialization stack 
	StackPush(&st, 1);  // Stack data 1,2,3,4,5
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	while (!StackEmpty(&st)) // If the stack is not empty , You can get the data 
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);   // Out of the stack 
	}
	printf("\n");


	StackDestory(&st);// Destroy the stack 
	return 0;
}

The test content can be changed by yourself .