Implementation of stack stack

The basic concept and discussion of stack

The stack only allows data to be inserted or deleted at the fixed end of the table , This end is called the top of the stack , The opposite end is the bottom of the stack , The insertion of the top position of the stack is called pushing or pressing , Deletion is called out of stack . Such a data structure has a feature of last in first out LIFO(last in first off）, It can also be "first in, second out" , Stack can be implemented by array table or linked list , When implemented with an array, the end of the array is used as the top of the stack , Because the insertion and deletion at the end of the array only need O(1) Time for , Similarly, if it is implemented with a single linked list , Take one end of the head of the linked list as the top of the stack , It's also because O(1) Insert delete operation . There are many examples of stack applications , For example, it can be used by the compiler to determine whether the symbols are balanced , Function call . If the balance symbol traverses the symbols one by one from left to right , The last left parenthesis must match the right parenthesis first , The first left parenthesis must match the last right parenthesis . Generally, the last function called will be released first .

The realization of the stack

Here we use arrays to realize , Because stack is a fast structure , You need to stack in and out frequently , The linked list requires frequent application and free space , Relatively poor performance .

The basic idea

A variable record capacity , A variable records the position of the top of the stack , There is also a pointer to the array space .

Structure declaration and function declaration

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define MINSIZE (4)
typedef char DataType;
typedef struct StackRecord StackRecord;
typedef struct StackRecord* Stack;
struct StackRecord
{
	DataType* data;
	int capacity;
	int top;
};

Stack CreateStack(size_t size);
void StackPush(Stack s, DataType x);
void StackPop(Stack s);
DataType StackTop(Stack s);
size_t StackSize(Stack s);
void StackPrint(Stack s);
int IsEmpty(Stack s);
int IsFull(Stack s);

initialization ：

, There will be top Initialize to -1, Because there was no data at first , And some programmers will top Initialize to 0, Pay attention to this situation top Indicates the next position at the top of the stack .

Stack CreateStack(size_t size)
{
	Stack s = (Stack)malloc(sizeof(StackRecord));
	if (s == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	s->top = -1;
	s->capacity = size > MINSIZE ? size : MINSIZE;
	s->data = (DataType*)malloc(sizeof(DataType) * s->capacity);
	if (s->data == NULL)
	{
		printf("out of spaces!\n");
		exit(-1);
	}
	return s;
}

In and out of the stack ：

void StackPush(Stack s, DataType x)
{
	assert(s);
	if (IsFull(s))
	{
		s->capacity *= 2;
		DataType* tmp = (DataType*)realloc(s->data, sizeof(DataType) * s->capacity);
		if (tmp == NULL)
			printf("push failed!,out of spaces!\n");
		else
			s->data = tmp;
	}
	s->data[++s->top] = x;
}
void StackPop(Stack s)
{
	assert(s);
	if (!IsEmpty(s))
		s->top--;
}

Determine empty and full and return stack size ：

int IsEmpty(Stack s)
{
	return s->top == -1;
}
int IsFull(Stack s)
{
	return s->top + 1 == s->capacity;
}
size_t StackSize(Stack s)
{
	assert(s);
	return s->top + 1;
}

Returns the top of stack element and prints the top of stack ：

DataType StackTop(Stack s)
{
	assert(s);
	return s->data[s->top];
}
void StackPrint(Stack s)
{
	assert(s);
	while (!IsEmpty(s))
	{
		printf("%d", StackTop(s));
		StackPop(s);
	}
	printf("\n");
}

In fact, the basic operation required by the stack is only entering the stack and exiting the stack , When writing other operations you add , Follow the basic operation of the stack , Print as above , Users should only be able to access top stack elements , This is what the stack data structure requires , When the user wants to print the stack , You can only access the top element of the stack and exit the stack , Go print one by one . So you have to pay a price to print the stack , You need to stack all the elements .