Of Stack

C++ stack structure establishment and operation detailed analysis

  • 2020-04-02 01:52:03
  • OfStack

What is a stack structure

Stack structure is classified from the operation of data, that is to say, the stack structure has a special operation rule, that is: last in first out.

We can think of the stack as a large warehouse, where the goods at the door (the top of the stack) are taken out first, and then the goods inside.

From the point of view of the logical structure of the data, the beginning of the stack structure is a linear structure.

If further divided from the storage structure of data, the stack structure consists of two types:
Sequence stack structure:

That is to use a set of address contiguous memory cells in order to save the data in the stack. In the program, you can define a structure array of specified size to be the stack, the element with the order number of 0 is the stack low, and you can define a variable top to hold the order number of the top of the stack.
Chain stack structure:

Store the values of each element in the stack in the form of a linked list. The top of the list (the element to which the head pointer points) is the top of the stack, and the bottom of the list (the address to which the pointer points is NULL) is the bottom of the stack.

In a stack structure, you can only operate at one end, which is called the top of the stack, and at the other end, which is called the bottom of the stack. That is, the data that is saved and retrieved can only be from one end of the stack structure. From the perspective of data operation, the stack structure deals with node data according to the principle of "last in, first out".

In the stack structure, only the top element of the stack is accessible, and the data operation of the stack structure is very simple. There are only two basic operations in the general stack structure:

Push: Save data to the top of the stack. Before the push operation, the top pointer of the stack is modified to move it up by an element position, and then the data is saved to the position indicated by the top pointer of the stack.

Push (Pop) : The operation of ejecting data from the top of the stack. Modify the top pointer to point to the next element in the stack.

Next, we use the C++ language to set up the sequential stack and complete the basic operation of the sequential stack structure
To prepare data

Prepare variables and data structures to be used in stack operations. 


#define MAXLEN 50
struct DATA
{
 string name;
 int age;
};
struct StackType
{
 DATA data[MAXLEN+1];
 int top;
};

Defines the length of the stack structure, MAXLEN, the DATA element type of the stack structure, and the StackType of the stack structure. In the data structure StackType, data is the data element and top is the ordinal number of the top of the stack. When top=0, the stack is empty, and when top=MAXLEN, the stack is full.

Array elements are filled with subscript 0 to start, here for the sake of explanation and understanding, we start from subscript 1 to record data nodes, subscript 0 position is not used.
Initializes the stack structure

Before using the stack structure, you first need to create an empty order stack, that is, initialize the order stack. The sequence stack initialization operation is as follows:

(1) request a memory space according to the specified size of the symbolic constant MAXLEN, which is used to store the data in the stack

(2) set the value of the pointer at the top of the stack to 0, indicating an empty stack.

The sample code is as follows: 


StackType *STInit()
{
 StackType *p;
 if(p=new StackType)   //Application stack space
 {
  p->top=0;     //Set the stack top to 0
  return p;     //Returns the pointer to the top of the stack
 } 
 return NULL; 
}

First, apply for memory with new, then set the top of the stack to 0, then return the first address of the applied memory, application failure returns NULL;

Determine the empty stack

Determine whether the stack structure is empty. If it is empty, it means there is no data in the stack structure. At this time, the push operation can be carried out, but the push operation cannot be carried out.

The sample code is as follows: 


int STIsEmpty(StackType *s)
{
 int t;
 t=(s->top==0);     //By the value at the top of the stack
 return t; 
}

The input parameter s is a pointer to the stack of operations. According to the stack top pointer top to determine whether the stack is 0, determine whether the stack is empty.

Determine the full stack

Determines if the stack structure is full. If the stack is full, there is no room in the stack structure to hold additional data. You cannot push at this point, but you can.

The sample code is as follows: 


int STIsFull(StackType *s)
{
 int t;
 t=(s->top==MAXLEN);
 return t; 
}

The input parameter s is a pointer to the stack of operations. According to the top pointer of the stack, determine whether the stack is equal to MAXLEN and whether the stack is full.

Empty stack

Clearing the stack is when all the data in the stack is cleared. The sample code is as follows: 


void STClear(StackType *s)
{
 s->top=0;
}

Set the stack top pointer top to 0 to perform the stack emptying operation. (this is just a logical way to empty the stack of data. In fact, I just set the top to 0, and adding data later will overwrite the original data.)

Release the space

The free space is the memory unit occupied by the free stack structure. Use delete to free the memory space applied with the new operator.

The sample code is as follows: 


void STFree(StackType *s)
{
 delete s;
}

Call the delete operator directly in the program to free up allocated memory space. This function is usually called when the stack structure is not needed, especially at the end of the program.

Into the stack

A Push is the basic operation of a stack structure, and the main operation is to save data elements to the stack structure. The specific steps of the push operation are as follows:

(1) first, determine the top of the stack. If top is greater than or equal to MAXLEN, overflow is indicated and error processing is conducted. Otherwise do the following.

(2) set top=top+1(add 1 to the top pointer to point to the push address)

(3) save the push U urea to the position pointed by top.

The sample code is as follows: 


int PushST(StackType *s,DATA data)
{
 if((s->top+1)>MAXLEN)
 {
  cout<<" Stack overflow "<<endl;
  return 0;
 }
 s->data[++s->top]=data;     //Push the element onto the stack
 return 1;
}

The input parameter s is a pointer to the operation stack, and the input parameter data is the data element that needs to be pushed. The program first determines whether the stack overflows, then gives a warning if the stack overflows, and does not carry out the push operation. Otherwise, it modifies the pointer at the top of the stack, that is, top first adds 1, and then puts the data into the data unit that top now points to.

Out of the stack

Pop is the basic operation that occupies the dog. The main operation is to Pop a data element from the top of the stack The steps are as follows:

(1) first, determine the top of the stack. If top equals 0, it indicates where the panic is and makes error handling. Otherwise do the following.

(2) return the element of the position to which the top of the stack pointer top points (actually the returned pointer)

(3) subtract 1 from top to point to the next element of the stack, and the original top element of the stack is popped up. 


DATA * PopST(StackType *s)
{
 if(s->top==0)
 {
  cout<<" Stack is empty, can no longer output! "<<endl;
  exit(0);
 }
 return &(s->data[s->top--]);
}

When there is DATA in the stack, the return value of this function is a pointer to DATA of type DATA.

Read point structure

Read point structure is to read the stack structure node data. Because the stack structure operates only at one end, a read operation here is essentially a read of the site's data.

It is important to note that the read node data operation is different from the stack operation. A read operation simply displays the contents of the data at the top of the stack, while a push operation pops the top of the stack.

The sample code is as follows: 


DATA *PeekST(StackType *s)
{
 if(s->top==0)
 {
  cout<<" The stack is empty "<<endl;
  exit(0);
 }
 return &(s->data[s->top]);
}

Comparing the stack sample code, it is not difficult to see that the read point structure also returns the address of the top node on the stack, but does not make top subtract 1.

Complete sample

Here is a complete example of the basic operation of the stack:

Program code: 


#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 50
struct DATA
{
 string name;
 int age;
};
struct StackType
{
 DATA data[MAXLEN+1];
 int top;
};
 
StackType *STInit()
{
 StackType *p;
 if(p=new StackType)   //Application stack space
 {
  p->top=0;     //Set the stack top to 0
  return p;     //Returns the pointer to the top of the stack
 } 
 return NULL; 
}

int STIsEmpty(StackType *s)
{
 int t;
 t=(s->top==0);     //By the value at the top of the stack
 return t; 
}

int STIsFull(StackType *s)
{
 int t;
 t=(s->top==MAXLEN);
 return t; 
}

void STClear(StackType *s)
{
 s->top=0;
} 

void STFree(StackType *s)
{
 delete s;
} 

int PushST(StackType *s,DATA data)
{
 if((s->top+1)>MAXLEN)
 {
  cout<<" Stack overflow "<<endl;
  return 0;
 }
 s->data[++s->top]=data;     //Push the element onto the stack
 return 1;
}

DATA * PopST(StackType *s)
{
 if(s->top==0)
 {
  cout<<" Stack is empty, can no longer output! "<<endl;
  exit(0);
 }
 return &(s->data[s->top--]);
} 

DATA *PeekST(StackType *s)
{
 if(s->top==0)
 {
  cout<<" The stack is empty "<<endl;
  exit(0);
 }
 return &(s->data[s->top]);
}

int main()
{
 StackType *stack;
 DATA data,*p_data;
 stack=STInit(); 
 cout<<"=============== Push operation: ============="<<endl;
 cout<<" Enter the name   , the age of the push operation: "<<endl;
 //Perform the push operation
 while(1)
 {
  cin>>data.name>>data.age;
  if(data.name=="0")
  {
   break;      //Exit input when name and age are both 0
  }else
  {
   PushST(stack,data);
  } 

 }
 p_data=PopST(stack);
 cout<<" Pops the top of the stack element "<<endl;
 cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
 p_data=PeekST(stack);
 cout<<" Output the top element of the stack "<<endl; 
 cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
 cout<<"================ Push all the data out: ============="<<endl;
 while(1)
 {
  p_data=PopST(stack);
  cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
 }
 STFree(stack);
 return 0;
}

Program operation interface:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/20130929005334437.png ">
Related articles: