I Stack
1. Basic concepts
- Also known as stack, both stack entry and stack exit are implemented at the top of the stack, requiring first in and then out.
- Initialization stack: initstack
- Stack function: push (& S, e) insert the element into the stack s as the element at the top of the stack
- Out of stack function: Pop (& S, & e) exits the top element of stack from stack s and assigns it to e
2. Sequential storage structure of stack
- Stack empty condition: top=-1
- Stack full condition: top=MaxSize-1
- Stack e operation: Top + +; Place e at the top
- Stack withdrawal: take out e, top from top--
#include<stdio.h>
#include<stdib.h>
#include<io.h>
#include<math.h>
#define OK 1
#define ERROR 0
#definr TRUE 1
#define FALSE 0
#define maxsize / / initial allocation of storage space
//Structure of sequential stack
typedef struct
{
selemtype data[maxsize];
int top;//Pointer for stack top
}sqstack;
status visit(selemtype c)
{
printf("%d",c);
return OK;
}
//Construct empty stack
stasus initstack(sqstacl *s)
{
s->top=-1;
return OK;
}
//Leave s blank
status clearstack(sqstack *s)
{
s->top=-1;
return ok;
}
//If stack s is an empty stack, it returns TRUE; otherwise, it returns FALSE
status stackempty(sqstack s)
{
if (s.top==-1)
return TRUE;
else
return FALSE;
}
//Returns the length of the s stack
int stscklength(sqstack s)
{
return s.top+1;
}
//If the stack is not empty, use e to return the top element of s and return OK; otherwise, return ERROR
ststus gettop(sqstack)
{
if(s.top==-1)
return ERROR;
else
*e=s.date[s.top];
return OK;
}
//Insert element e as the new stack top element
status push(sqstack *s,selemtype e)
{
if(s->top==maxsize-1) //If the stack is full, you cannot insert elements in the
{
return ERROR;
}
s->top++; //Stack top pointer increases by 1
s->data[s->top]=e;//Assign the newly inserted element to the stack top space
return OK;
}
//If the stack is not empty, delete the top element of s, return its value with e, and return OK; Otherwise, ERROR is returned
status pop(sqstack *s,selemtype *e)
{
if(s->top==-1)
return ERROR;
*e=s->data[s-]
}
//Each element in the stack is printed from the bottom of the stack to the top of the stack
status stacktraverse(sqstack s)
{
int i;
i=0;
while(i<=s.top)
{
visit(s.data[i++]);
}
printf("\n");
return OK;
}
int main()
{
int j;
sqstack s;
int e;
if(initstack(&s)==OK)
for(j=1;j<=10;j++)
push(&s,j);
printf("The elements in the stack are:");
stacktraverse(s);
pop(&s,&e);
printf("Stack top element e=%d\n",e);
printf("Stack empty No:%d(1:Null 0:no)\n",stackempty(s));
gettop(s,&e);
printf("Stack top element e=%d Stack length is%d\n",e,stacklength(s));
clearstack(&s);
printf("Empty stack after emptying stack No:%d(1:Null 0:no)\n",stackempty(s));
return 0;
}
3. Two stack shared space
The operating instructions are similar to those of a stack. The difference is that a space is divided into two stacks. The first stack starts from the beginning and the second stack starts from the end. When the two stacks meet, the stack is full (when it can no longer be inserted).
4. Chain storage structure of stack
The difference between chain stack and CIS stack is that the space of CIS stack is fixed and continuous, just like array; The chained stack does not require a piece of continuous storage space to store data. Therefore, in order to know the complete elements in the stack, two members need to be defined, one is the data idiom to store data, and the other is the pointer member, Store the address of the next element (the chained stack here is similar to a pointer); for ease of operation, the top of the stack is generally placed at the head of the single linked list. Generally, the head node is not required for the chained stack.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int EleType;
typedef struct StackNode {
EleType data;//Node data field
struct StackNode* next;//Node pointer field
}StackNode,* LinkStackPoi;
//Data structure of chain stack
typedef struct LinkStack {
LinkStackPoi top;//Stack top node
int count;//Number of elements
}LinkStack;
//initialization
Status InitLinkStack(LinkStack* stack)
{
if (!stack)
{
return ERROR;
}
stack->top = NULL;
stack->count = 0;
return OK;
}
//Clearing data and freeing node memory is actually all the data in pop
Status ClearLinkStack(LinkStack* stack)
{
if (!stack||!stack->count)
{
return ERROR;
}
while (stack->count)
{
StackNode* node = stack->top;
stack->top = node->next;
free(node);
stack->count--;
}
return OK;
}
//Judge whether the chain stack is empty
Status EmptyLinkStack(LinkStack* stack) {
if (!stack)
{
return ERROR;
}
return stack->count == 0 ? 1 : 0;
}
//Get the number of elements
int GetLengthLinkStack(LinkStack* stack)
{
if (!stack )
{
return -1;
}
return stack->count;
}
Status GetTop(LinkStack* stack, StackNode** stackNode)
{
if (!stack)
{
return ERROR;
}
*stackNode = stack->top;//Return the pointer of the top element of the stack to obtain the content pointing to the modifiable top element.
return OK;
}
/*
Bomb stack
The pointer at the top of the stack points to the front node of the element to be popped, then releases the memory space of the popped element, and then count-1
*/
Status pop(LinkStack* stack,EleType *e)
{
if (!stack && stack->count)
{
return ERROR;
}
StackNode* node = stack->top;
*e = node->data;
stack->top = node->next;//The stack top pointer points to the new stack top element
free(node);//Free element space
stack->count--;
return OK;
}
/*
Stack pressing
First put the pressed elements into the linked list, then point the pointer at the top of the stack to the pressed elements, and then count+1
*/
Status push(LinkStack* stack,EleType e)
{
if (!stack)
{
return ERROR;
}
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
node->next = stack->top;//Add elements to the linked list
node->data = e;
stack->top = node;//The stack top element points to the push in element
stack->count++;
return OK;
}
void PrintfLinkStack(LinkStack* stack)
{
if (!stack&&stack->count)
{
return;
}
StackNode* node = stack->top;
while (node)
{
printf("%d,", node->data);
node = node->next;
}
puts("");
return;
}
int main(int argc, char *argv[])
{
LinkStack stack;
InitLinkStack(&stack);//initialization
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
push(&stack, 4);
push(&stack, 5);
puts("Chain stack element:");
PrintfLinkStack(&stack);
printf("Number of chain stack elements:%d\n", GetLengthLinkStack(&stack));
EleType e1,e2;
pop(&stack, &e1);
printf("Pop up the first element:%d\n", e1);
pop(&stack, &e2);
printf("Pop up the second element:%d\n", e2);
puts("Chain stack element:");
PrintfLinkStack(&stack);
printf("Number of chain stack elements:%d", GetLengthLinkStack(&stack));
printf("\n");
return 0;
}5. Stack application --- recursion
In a narrow sense, recursion refers to the skill of a module program calling itself in Computer Science (that is, as everyone is familiar with). If we visualize this effect, it becomes the "drowster effect", that is, a part of the picture includes the picture itself.
Fibonacci sequence
Recursive implementation
int fibonacci(int num) {
if(num < 2)
return num == 0 ? 0 : 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}II queue
1. Basic concepts
A queue is a linear table that only allows insertion at one end and deletion at the other end. It is a collection type based on First In First Out (FIFO) policy. The end that allows insertion is called the tail of the queue, and the end that allows deletion is called the head of the queue
2. Sequential storage structure of queue
Different from the stack, the queue elements are dequeued at the queue head, which is 0 in the following table. In order to ensure that the queue head is not empty, all elements in the queue must move forward every time after leaving the queue. At this time, the time complexity is O(n). At this time, the implementation of queue is exactly the same as the sequential storage structure of linear table;
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 / * initial allocation of storage space*/
typedef int Status;
typedef int QElemType; /* QElemType The type depends on the actual situation. It is assumed to be int */
/* Sequential storage structure of circular queue */
typedef struct
{
QElemType data[MAXSIZE];
int front; /* Head pointer */
int rear; /* Tail pointer, if the queue is not empty, points to the next position of the tail element of the queue */
}SqQueue;
Status visit(QElemType c)
{
printf("%d ",c);
return OK;
}
/* Initialize an empty queue Q */
Status InitQueue(SqQueue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
/* Clear Q to empty queue */
Status ClearQueue(SqQueue *Q)
{
Q->front=Q->rear=0;
return OK;
}
/* If queue Q is an empty queue, it returns TRUE; otherwise, it returns FALSE */
Status QueueEmpty(SqQueue Q)
{
if(Q.front==Q.rear) /* Flag for empty queue */
return TRUE;
else
return FALSE;
}
/* Returns the number of elements of Q, that is, the current length of the queue */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
/* If the queue is not empty, use e to return the queue header element of Q and return OK; otherwise, return ERROR */
Status GetHead(SqQueue Q,QElemType *e)
{
if(Q.front==Q.rear) /* queue is empty */
return ERROR;
*e=Q.data[Q.front];
return OK;
}
/* If the queue is not full, insert a new tail element with element e as Q */
Status EnQueue(SqQueue *Q,QElemType e)
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* Queue full judgment */
return ERROR;
Q->data[Q->rear]=e; /* Assign the element e to the end of the queue */
Q->rear=(Q->rear+1)%MAXSIZE;/* rear Move the pointer back one position, */
/* If to the end, go to the array header */
return OK;
}
/* If the queue is not empty, delete the queue header element in Q and return its value with e */
Status DeQueue(SqQueue *Q,QElemType *e)
{
if (Q->front == Q->rear) /* Judgment of empty queue */
return ERROR;
*e=Q->data[Q->front]; /* Assign the team head element to e */
Q->front=(Q->front+1)%MAXSIZE; /* front Move the pointer back one position, */
/* If to the end, go to the array header */
return OK;
}
/* Each element in queue Q is output from the head of the queue to the tail of the queue */
Status QueueTraverse(SqQueue Q)
{
int i;
i=Q.front;
while((i+Q.front)!=Q.rear)
{
visit(Q.data[i]);
i=(i+1)%MAXSIZE;
}
printf("\n");
return OK;
}
int main()
{
Status j;
int i=0,l;
QElemType d;
SqQueue Q;
InitQueue(&Q);
printf("After initializing the queue, is the queue empty?%u(1:Null 0:no)\n",QueueEmpty(Q));
printf("Please enter an integer queue element(No more than%d individual),-1 Is an early terminator: ",MAXSIZE-1);
do
{
/* scanf("%d",&d); */
d=i+100;
if(d==-1)
break;
i++;
EnQueue(&Q,d);
}while(i<MAXSIZE-1);
printf("Queue length is: %d\n",QueueLength(Q));
printf("Is the queue empty now?%u(1:Null 0:no)\n",QueueEmpty(Q));
printf("continuity%d Delete element by team leader,Insert element at end of queue:\n",MAXSIZE);
for(l=1;l<=MAXSIZE;l++)
{
DeQueue(&Q,&d);
printf("The deleted element is%d,Inserted element:%d \n",d,l+1000);
/* scanf("%d",&d); */
d=l+1000;
EnQueue(&Q,d);
}
l=QueueLength(Q);
printf("Now the elements in the queue are: \n");
QueueTraverse(Q);
printf("We've inserted it at the end of the team%d Elements\n",i+MAXSIZE);
if(l-2>0)
printf("Now deleted by team leader%d Elements:\n",l-2);
while(QueueLength(Q)>2)
{
DeQueue(&Q,&d);
printf("The deleted element value is%d\n",d);
}
j=GetHead(Q,&d);
if(j)
printf("Now the team head element is: %d\n",d);
ClearQueue(&Q);
printf("After emptying the queue, Is the queue empty?%u(1:Null 0:no)\n",QueueEmpty(Q));
return 0;
}3. Chained storage space of queue
The chained storage structure of a queue is actually a single chained list of linear tables, but it can only end in and end out.
III summary
The stack limit can only be inserted and deleted at the top of the stack, while the queue limit can only be inserted at the end of the queue and deleted at the head of the queue. Both of them can be realized by sequential storage structure and chain storage structure. For stacks, if the data types of the two stacks are the same and the space requirements are opposite, the method of sharing array space can be used to improve the space utilization.
Reprint: http://blog.bools.cn/archives/999