Stack and Queue

Stack

Definition ：

1、 Linear tables that are only allowed to be inserted and deleted at one end

2、 The side that allows insertion and deletion is called To the top of the stack , The other end is called At the bottom of the stack .

characteristic ：

Last in, first out （LIFO）

 

Diagram of stack in and out

Here top Called top of stack pointer , But it's not really a pointer , It simply points to the element position of the array .

The stack entry operation is to put top++, Re embedded value

The stack out operation is to first fetch the current top Value pointing to position , After the top--.

 

 

Framework construction of sequence stack

#include<stdio.h>
#include<stdlib.h>
#define SIZE 10

enum ret_val{MALLOC_OK=100,MALLOC_NO,CREATE_OK,CREATE_NO,FULL_OK,FULL_NO,EMPTY_OK,EMPTY_NO,PUSH_OK,PUSH_NO,POP_OK,POP_NO};

struct stack_node
{
    int stack_data[SIZE];
    int top;
};

typedef struct stack_node Stack;

void create_stack(Stack ** stack)
{
    *stack=(Stack *)malloc(sizeof(Stack));

    if(MALLOC_OK==is_malloc_ok(Stack *stack))
    {
        return CREATE_OK;
    }
    return CREATE_NO;
}

void init_stack(Stack *stack)
{
    stack->top=-1;
}

int is_full(Stack * stack)
{
    if(stack->top>=SIZE-1)
    {
        return FULL_OK;
    }
    return FULL_NO;
}

int push_stack(Stack * stack,int num)
{
    if(FULL_NO==is_full(stack)&&CREATE_OK==create_stack(Stack *stack))
    {
        //stack->top++;
        stack->stack_data[++stack->top]=num;
        printf("%d ",stack->stack_data[stack->top]);
        return PUSH_OK;
    }
    printf("stack is full!\n");
    return PUSH_NO;
}

int is_empty(Stack * stack)
{
    if(stack->top<0)
    {
        return EMPTY_OK;
    }
        return EMPTY_NO;
}

int pop_stack(Stack * stack)
{
    if(EMPTY_NO==is_empty(stack))
    {
        return stack->stack_data[stack->top--];
    }
    printf("stack is empty!\n");
    return POP_NO;
}

int is_malloc_ok(Stack * stack)
{
    if(NULL==stack)
    {
        return MALLOC_NO;
    }
    return MALLOC_OK;
}

int main()
{
    Stack * stack=NULL;
    int i;
    int num=0;

    create_stack(&stack);
    init_stack(stack);

    for(i=0;i<10;i++)
    {
        if(PUSH_OK==push_stack(stack,i+1))
        {
            printf("push stack success!\n");
        }
        else
        {
            printf("push stack fail!\n");
        }
    }


    for(i=0;i<10;i++)
    {
        num=pop_stack(stack);

        if(POP_NO!=num)//pop_stack(stack)
        {
            printf("%d ",num);//pop_stack(stack)
            printf("pop stack success!\n");
        }
        else
        {
            printf("pop stack fail!\n");
        }
    }

    free(stack);

    return 0;
}

Chain stack

  There is no stack full problem in this kind of stack , Space expandable , Inserts and deletions are performed only at the top of the stack , The top of the stack is at the head of the chain , Suitable for multi stack operation .

queue

Definition ：

Queues are only allowed to be deleted at one end , The end of the linear table inserted at the other end that allows deletion is called the queue head , The end allowed to be inserted is called the end of the line .

characteristic ：

fifo （FIFO）

Queue in queue out queue operation

1.   When entering the team, the pointer at the end of the team is one  rear = rear + 1, Then press the new element rear Indicate where to add .
2.   When leaving the team, the leader of the team is one ahead front = front + 1, And then subscript front Take out the elements of .
3.   Entering the team when the team is full will overflow and make mistakes ;   When the team is empty, go out of the team and deal with it .
4.   One of the solutions ： Put the queue elements in the array, and connect the beginning and end of the array , Form a cycle ( ring ) queue .

  Circular queue

Queue storage arrays are treated as end-to-end tables .

Team head 、 End of line pointer plus 1 From the QueueSize -1 Go straight to 0, Modulo of available languages ( remainder ) Operation implementation .

1. Team leader pointer advance 1:  front = (front+1) % QueueSize;
2. At the end of the line 1:  rear = (rear+1) % QueueSize;
3. Queue initialization ：front = rear = 0;
4. Team air condition ：front == rear;
5. Team full conditions ：(rear+1) % QueueSize == front