Stack

What is a stack?

Stack is a kind of linear table.

It only allows the insertion and deletion of elements at the fixed end.

The one end for data insertion and deletion is called the top of the stack and the other end is called the bottom of the stack.

Therefore, the stack addition and deletion elements have what we often call last in first out:

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

Stack out: stack deletion is called stack out. The data is also at the top of the stack.

Implementation of stack

There are two options for the implementation of stack, one is sequential list and the other is linked list.

Here is a sequence table to achieve.

Why not use the linked list? The reasons are as follows:

1. The tail end of the sequence table is the top of the stack. Every time you enter or exit the stack, you will insert or delete the tail. It is relatively simple to implement, and the time complexity is O(1).
2. If the single linked list is selected for implementation, the operation of tail insertion or tail deletion is more complex, and the time complexity is O(N).
3. If the leading two-way circular linked list is selected, although the time complexity is also O(1), the structure is not as simple as the sequential list.

To sum up, the stack is implemented with a sequence table.

code implementation

Because the sequence table is dynamic and static,

Obviously, the dynamic version is more flexible,

Therefore, the following is the sequence table of dynamic expandable capacity.

Stack declaration

Like the normal sequence table,

Replace size,

It looks more intuitive.

data points to the array of subsequent dynamic development.

typedef int DataType;
typedef struct Stack
{
	DataType* data;
	int top;      //Stack top
	int capacity; //capacity
}Stack;

Initialization stack

At the beginning, four empty seats are given,

The subsequent expansion is not convenient enough.

The top of the stack is initialized to 0.

void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = (DataType*)malloc(sizeof(DataType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

Determine whether the stack is empty

To improve code readability,

Therefore, the return value is of boolean type.

Null returns true,

If it is not empty, false is returned.

bool StackEmpty(Stack* ps)
{
	return ps->top == 0;
}

Push

The stack operation is actually the tail insertion of the sequence table.

Before inserting data, first judge whether the stack is full,

When it is full, it will be expanded,

The capacity here is doubled.

Because the operation of stack only inserts data into the stack,

Therefore, capacity increase is only used in stack operation,

You don't need to take it out alone to make it into a function.

void StackPush(Stack* ps, DataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		DataType* tmp = (DataType*)realloc(ps->data, sizeof(DataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("StackPush");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity *= 2;
	}
	ps->data[ps->top] = x;
	ps->top++;
}

Out of stack

Out of the stack is the deletion of the end of the sequence table.

No need to manipulate data.

When the stack is empty, there is no need to delete it,

So use assert to assert whether it is not empty.

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

Returns the value of the top of the stack

You also need to determine whether the stack is empty.

DataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];
}

Gets the number of valid elements in the stack

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

Destroy stack

Because the array pointed to by data is developed dynamically,

So don't forget to release it at last.

void StackDestroy(Stack* ps)
{
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

queue

What is a queue?

The queue is actually very vivid. For example, the queue for nucleic acid is a queue. Those who queue up early do it first and those who come late do it later. Another example is hospital registration, which is early for consultation. Therefore, the principle of hospital registration machine is realized by relying on queue.

Therefore, compared with the stack, the stack is last in first out,

The queue is First In First Out (* First In First Out *).

Therefore, a queue is a special linear table that only allows inserting data at one end and deleting data at the other end.

Queues also have two basic operations:

1. Enter queue: the end of the queue at which the insertion operation is performed is called the end of the queue

2. Out of queue: the end of the deletion operation is called the queue head

Implementation of queue

That's the problem here,

Is the queue implemented by sequential list or linked list?

The linked list and single linked list are used here. The reason is very simple:

1. If the sequence table is used, the queue is equivalent to header deletion, which requires the subsequent elements to be covered forward, and the time complexity is O(N).
2. If the linked list is used, the time complexity of out of queue, that is, header deletion, is only O(N), and the single linked list itself is enough to realize the queue. There is no need to use the lead two-way circular linked list with more complex structure.

code implementation

Declaration of queue

A complete queue has a beginning and an end,

The head points to the head of the linked list,

Tail points to the tail of the linked list.

//struct Node 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

//queue
typedef struct Queue
{
	struct QueueNode* head;
	struct QueueNode* tail;
}Queue;

Queue initialization

The queue is initially empty,

So just leave the head and tail empty.

void QueueInit(Queue* pq)
{
	pq->head = NULL;
	pq->tail = NULL;
}

Judge whether the queue is empty

To improve the readability of the code,

The return value here is of boolean type.

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Tail in queue

Please pay attention to the following when entering the queue:

When the queue is empty,

Since both head and tail are null pointers,

Therefore, you need both head and tail to point to the new node.

If the queue is not empty,

Then directly move tail.

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
    
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
    
	if (QueueEmpty(pq))
		pq->head = pq->tail = newnode;
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

Queue leader out of queue

The precondition for the queue leader to leave the queue is that the queue is not empty,

So we need to assert it.

When the queue has only one element,

At this point, it becomes an empty queue after leaving the queue.

Therefore, when free turns around the head element, both head and tail become null pointers.

When the queue has two or more elements,

Directly delete the header.

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
    
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

Get the data of the team leader

Take the data of the queue header on the premise that the queue is not empty,

So I used assert to assert.

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

Get the data at the end of the queue

Take the data at the end of the queue if the queue is not empty,

So I used assert to assert.

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

Returns the number of data in the queue

This doesn't have to be judged empty,

Go through it directly.

int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

Destroy queue

The queue is a linked list,

It is a node developed dynamically,

So you need to traverse the linked list,

Release each node separately.

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}