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).

function	usage
s.empty()	Check whether the stack is empty, return 1 if not, return 0 if not
s.size()	Returns the number of elements in the stack
s.top()	Returns the element at the top of the stack, but does not delete it
s.pop()	Return the element at the top of the stack and delete it
s.push()	Insert the element onto the stack