Stack
Concept and structure of stack
Stack: a special linear table that allows insertion and deletion of elements only at a fixed end. 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. The data elements in the stack follow the principle of Last In First Out LIFO (Last In First Out).
Generally, the open end of the stack is called the top of the stack; Accordingly, the sealing end is called the bottom of the stack. Therefore, the stack top element refers to the element closest to the stack top.
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 output data is also at the top of the stack.
Implementation of stack
Stack can generally be implemented by array or linked list. Relatively speaking, the structure of array is better. Because the cost of inserting data on the tail of the array is relatively small. Let's work together to realize the following operations of dynamically opening up the storage space stack.
//Stack initialization void InitStack(S* ps); //Stack void PushStack(S* ps, StackData x); //Out of stack void PopStack(S* ps); //Empty void ClearStack(S* ps);
Stack structure
typedef int StackData;
typedef struct Stack
{
StackData* a;
int size;//Number of stacked data
int capacity;//capacity
}S;Initialization and emptying of stack
The initialization and emptying operations of the stack are relatively simple, because there is no pressed data during initialization. You can set both size and capacity to 0 and a to NULL; When emptying, release the pointer and point to NULL. At the same time, set size and capacity to 0.
//Stack initialization
void InitStack(S* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
printf("Initialization succeeded.\n");
}
//empty
void ClearStack(S* ps)
{
free(ps->a);
ps->a = NULL;
ps->size = ps->capacity = 0;
printf("The stack has been emptied.\n");
}Stack in and stack out
For example, putting elements 1, 2, 3 and 4 on the stack in turn is equivalent to adding each element to the stack in turn by header insertion.
For the out of stack operation, if you want to take element 3 out of the stack, according to the principle of "first in, then out", you must first take element 4 out of the stack, that is, remove it from the stack, and then element 3 can be out of the stack:
The following code is used to realize the above operations:
//Push
void PushStack(S* ps, StackData x)
{
StackCheakCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
printf("Stack successfully.\n");
}
//Out of stack
void PopStack(S* ps)
{
if (ps->size == 0)
{
printf("Empty stack cannot be ejected.\n");
return;
}
printf("Pop up elements are:%d\n", ps->a[--ps->size]);
}It should be noted that both capacity and size are 0 during initialization, and then the stack may be full due to size=capacity. Here, we might as well check the capacity every time we insert it. If the stack is full, we will expand it. Generally, we will double it:
//Check whether the capacity is enough. If not, expand the capacity to twice.
void StackCheakCapacity(S* ps)
{
if (ps->size == ps->capacity)//When it is full, it will be expanded
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
StackData* tmp = (StackData*)realloc(ps->a, newcapacity * sizeof(StackData));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}Another small detail in this code is the definition of newcapacity. When the capacity value is not 0, you can directly start realloc operation to open up twice the capacity space. However, if the capacity is equal to 0, its double or 0 is equivalent to no open space. Therefore, if the capacity is 0, we give the initial value of 4.
queue
Concept and structure of queue
Queue, like stack, is also a linear storage structure with strict requirements for data "storage" and "retrieval". Different from stack structure, both ends of queue are "open", which requires that data can only enter from one end and exit from the other end. Queue has the nature of first in first out FIFO(First In First Out).
Enter queue: the end of the queue at which the insertion operation is performed is called the end of the queue
Out of queue: the end for deletion is called the queue head.
Implementation of queue
The queue can also be implemented in the structure of array and linked list. It is better to use the structure of linked list, because if the structure of array is used, the efficiency will be relatively low. Let's implement the following operations to dynamically open up the storage space queue.
//Queue initialization void QueueInit(Queue* pq); //Queue destruction void QueueDestroy(Queue* pq); //Join the team void QueuePush(Queue* pq, QDataType x); //Out of the team void QueuePop(Queue* pq);
Queue structure
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;Initialization and destruction of queues
It is similar to the initialization and destruction of the stack. Since the queue operation has not yet been performed, you may wish to point to NULL for both head and tail; When destroying, release the pointer and point to NULL.
//initialization
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
}
//Destroy
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur != NULL)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}Join and leave the team
//Join the team
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
//Out of the team
void QueuePop(Queue* pq)
{
assert(pq);
//if (pq->head == NULL)
// return;
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}