A comprehensive summary of stacks

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

Learning Objectives:

• Grasp the characteristics of stack abstract data type, in the corresponding practical problems in the correct application of relevant code
• Master sequential stack, double stack, stack call

2. Basic concepts

• Definition: a linear table that allows insertion or deletion at only one end
• Top: The end of the stack that allows insertion or deletion
• Bottom: The end corresponding to the top of the stack
• 
• Features: Advanced after out

Three, stack representation and implementation

1. The stack sequence

• Definition: a group of contiguous storage cells that hold data elements from the bottom of the stack to the top of the stack

• Top: Indicates the position of the top element on the stack

  • Top ==-1 indicates an empty stack
  • Top ==NULL indicates that the stack does not exist
  • The top>stacksize element overflows

Structure definition:

#define n 500// Define the sequential stack size
struct stack
{
    int top;// Top of stack pointer
    int a[n];// Sequential stack array
}SeqStack;
Copy the code

2. The chain stack

Structure definition:

typedef struct node
{
    int data;// Define the data type
    struct node*next;// Define the stack

}ChaiinStack;
Copy the code

Features:

• There is no problem with full stack, and the size can be expanded at any time
• Insert and delete are performed at the top of the stack
• The top of a chain stack is at the head of the chain
• Consistent with single-linked list storage structure, consistent with sequential list logical structure

Fourth, the common algorithm of sequential stack

Dynamic graph:

​

Algorithm explanation:

• Push is pushed, and the pointer TOP moves up
• Pop exits the stack, and the pointer TOP moves down

1. Initialization

void InitStack(SeqStack *S)
{	/* Construct an empty stack S*/
  	S->top = - 1;
}
Copy the code

2. To empty

/* Sequential stack empty */
int IsEmpty(SeqStack *S)
 {     /* Return true if S is empty and false if S is empty
	 return(S->top==- 1? TRUE:FALSE); }Copy the code

3. The full

/* Order the stack to fill */
int IsFull(SeqStack *S)	
{   /* Return true if S is full and false if S is full
	return(S->top==Stack_Size- 1? TRUE:FALSE); }Copy the code

4. Stack the top elements in sequence

int GetTop(SeqStack *S,StackElementType *x)
{  	/* Pop the top element of stack S into the storage space indicated by x, but leave the top pointer unchanged */
	if(S->top == - 1)      /* Stack is empty */
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
  		return(TRUE); }}Copy the code

5. Stack them in sequence

/* Sequential stack */
int Pop(SeqStack *S,StackElementType *x)
{  
	/* Pop the top element of stack S into the storage space indicated by x */
	if(S->top == - 1)    /* Stack is empty */
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
		S->top++;    /* Change the top pointer */
  		return(TRUE); }}Copy the code

6. Stack out in sequence

/* Sequential stack */
int Pop(SeqStack *S,StackElementType *x)
{  
	/* Pop the top element of stack S into the storage space indicated by x */
	if(S->top == - 1)    /* Stack is empty */
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
		S->top--;    /* Change the top pointer */
  		return(TRUE); }}Copy the code

Five, double stack

Algorithm details:

• Two sequential stacks stack1,stack2
• Sequential stack 1 is pushed from left to right, top1++
• Sequential stack 1 is pushed from right to left, top2–
• Stack full condition: TOP1 +1== Top2

1. Dual-end sequential stack operation

/* Double-ended sequential stack operation. * /
int Push(DqStack *S, StackElementType x, int i)
{	/* Push the data element x onto the I stack */
	if(S->top[0] +1==S->top[1])    /* Stack is full */
		return(FALSE);
	switch(i)
	{
	case 0:
		S->top[0] + +; S->Stack[S->top[0]]=x;	break;
	case 1:
		S->top[1]--;	S->Stack[S->top[1]]=x;	break;
	default:  /* Parameter error */
        return(FALSE)
 	}
	return(TRUE);
}
Copy the code

2. Dual-end sequential stack removal

/* Double end sequential stack out operation. * /
int Pop(DqStack *S,StackElementType *x,int i)
{	/* Pops the top element from the I stack into x */
	switch(i)
	{
	case 0:
		if(S->top[0] = =- 1)  return(FALSE);
		*x=S->Stack[S->top[0]];   S->top[0]--;	break;
	case 1:
		if(S->top[1]==M)  return(FALSE);
		*x=S->Stack[S->top[1]];	S->top[1] + +;break;
	default:
		return(FALSE);
	}
	return(TRUE);
}
Copy the code

Sixth, summary and improvement

• For the use of C++ programming, the above sequence stack void, full, insert, delete and so on a series of code, you do not need to master, C++ STL standard library for you ready to call the function.

C++stack header

#include<stack>
//#include
      
        or universal header file
      
using namespace std;
Copy the code

C++stack:

• Use stack to define class s (you can define anything, just change s to the defined letter to call C++ functions).