Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

How to implement the stack and queue of C++

2025-01-16 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >

Share

Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to realize the stack and queue of C++". In daily operation, I believe many people have doubts about how to realize the stack and queue of C++. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts about how to realize the stack and queue of C++. Next, please follow the editor to study!

Section 1: stack (Stack)

A stack is a linear table that restricts inserts and deletions at one end of the table. This end that allows insert and delete operations is called the top of the stack (Top), and the other fixed end is called the bottom of the stack.

For example, there are three elements in the stack, the order of entering the stack is A1, a2, a3, when you need to get out of the stack, the order is a3 ~ ~ a2 ~ ~ A1, so the stack is also called "last in, first out" or "first in, first out" linear table, referred to as "LIFO table" or "FILO table".

1.1: basic operation of stack:

(1) Stack initialization:

Init_Stack (s)

(2) the stack is empty:

Empty_Stack (s)

(3) Stack:

Push_Stack (Scrim x)

(4) Stack out:

Pop_Stack (s)

(5) read the elements at the top of the stack:

Top_Stack (s)

1.2 Storage structure and basic operation of stack

Because the stack is a linear table with limited operation (each element is stored in a set of consecutive address storage units in turn), the storage structure of the linear table is also suitable for the stack, but the operation is different.

(1) sequential stack

The stack implemented by sequential storage is called sequential stack. Similar to the definition of sequential table, the data elements in the stack are implemented with a preset one-dimensional array of sufficient length: datatype data [MAXSIZE]. The bottom position of the stack can be set at any end of the array, while the top of the stack changes with insertion and deletion. Int top is used as the pointer at the top of the stack to indicate the position of the top of the current stack. Data and top are also encapsulated in a structure. The type of sequential stack is described as follows:

Typedef struct {datatype data [MAXSIZE]; int top;} SeqStack

Defines a pointer to the sequential stack.

SeqStack * s

Usually, the 0 subscript end is set as the bottom of the stack, so when the index top=-1; at the top of the empty stack enters the stack, the pointer at the top of the stack is added by 1, that is, when s-> top++; goes out of the stack, the pointer at the top of the stack is minus 1, that is, s-> top--. The pointer at the top of the stack and the data elements in the stack are shown in the following figure:

The basic operations are implemented as follows:

1) empty the stack: first establish the stack space, and then initialize the top pointer of the stack.

SeqStack * Init_SeqStack () {SeqStack * s; s=malloc (sizeof (SeqStack)); s-> top =-1; return s;}

2) empty stack:

Int Empty_SeqStack (SeqStack * s) {if (s-> top = =-1) {return 1;} else {return 0;}}

3) Stack:

Int Push_SeqStack (SeqStack * s datatype x) {if (s-> top = = MAXSIZE-1) {/ / prevent space overflow-overflow return 0;} else {s-> top++; s-> data [s-> top] = x; return 1;}}

4) Stack out:

Int Pop_SeqStack (SeqStack * s Empty_SeqStack datatype * x) {if (Empty_SeqStack) (s) {return 0;} else {* x = s-> data [s-> top]; s-> top--; return 1;}}

5) take the top element of the stack:

Datatype Top_SeqStack (SeqStack * s) {if (Empty_SeqStack (s)) {return 0;} else {return (s-> data [s-> top]);}}

(2) chain stack

A stack implemented with a chain storage structure is called a chain stack. The stack is represented by a single linked list, so its node structure is the same as that of the single linked list. Here, it is expressed by LinkStack:

Typedef struck node {datatype data; struct node * next;} StackNode * LinkStack

The basic operations are as follows:

1) empty the stack:

LinkStack Init_LinkStack () {return NULL;}

Judge the stack is empty:

Int Empty_LinkStack (LinkStack top) {if (top==NULL) return 1; else return 0;}

3) Stack:

LinkStack Push_LinkStack (LinkStack top, datatype x) {StackNode * s; s = malloc (sizeof (StackNode)); s-> data=x; s-> next=top; top=s; return top;}

Out of the stack:

LinkStack Pop_LinkStack (LinkStack top, datatype * x) {StackNode * p; if (top= = NULL) return NULL; else * x = top- > data; p = top; top= top- > next; free (p); return top;} Section II: queue

2.1: definition and basic operations

Stack is about a first-in-first-out data structure, and in practical problems, we often use a "first-in, first-out" data structure: insert at one end of the table, and delete at the other end of the table, which is called Queue (queue [kju]). The end that allows insertion is called the end of the line (rear), and the side that is deleted is allowed to become the head of the line (front). If the order in which a team is included in the team is as follows: a _ 1, a _ 2, a _ 3, a _ 4, a _ 5, the order of leaving the team will still be a _ 1 _ x, a _ 2, a _ 3, a _ 4, a _ 5. It's like people waiting in line at the supermarket to check out.

Queue is also a linear table with limited operation, also known as first-in, first-out table, or "FIFO table" for short.

Basic operations:

(1) initialize:

Init_Queue (Q)

(2) team operation:

In_Queue (QBI x)

(3) team operation:

Out_Queue (QBI x)

(4) read the elements of the head of the line:

Front_Queue (QBI x)

(5) judging team empty operation:

Empty_Queue (Q)

2.2: storage structure and basic operations of queues

(1) sequence team

Sequentially stored queues are called sequential queues. Because the head and end of the queue are active, there are two pointers at the head and end of the queue in addition to the data area of the queue. Sequence teams are defined as follows:

Define MAXSIZE 100 typedef stuct {datatype data [MAXSIZE]; / Storage space int rear,font;// tail pointer} SeQueue; SeQueue * sq;// pointer sq = malloc (sizeof (SeQueue)); / / apply for storage space sq- > data [0] ~ sq- > data [MAXSIZE-1]; / / Storage area sq- > front / / queue head sq- > rear / / queue tail sq- > front = sq- > rear =-1; / empty / / sq- > rear++ / / sequence team sq- > rear = (sq- > rear+1)% MAXSIZE;// round robin team sq- > data [sq-> rear] = x; / join the queue / / sq- > front++;sq- > front = (sq- > front+1)% MAXSIZE;x=sq- > data [sq-> front]; / / out of line m = (sq- > rear)-(Q-> font); / / Captain

1) empty team:

Return SeQueue * Init_SeQueue () {Q = malloc (sizeof (c_SeQueue)); Q-> font = Q-> rear =-1; Q-> num = 0; return Q;}

2) join the team:

Int In_SeQueue (c_SeQueue * Q, datatype x) {if (num = = MAXSIZE) {return-1;} else {Q-> rear = (Q-> rear+1)% MAXSIZE: Q-> data [Q-> rear] = x; num++; return 1;}}

3) get out of the team:

Int Out_SeQueue (c_SeQueue * Q, datatype * x) {if (num = = 0) {return-1;} else {Q-> fornt = (Q-> front+1)% MAXSIZE; * x = Q-> front]; / / read num--; return 1;}}

4) empty judgment:

Int Empty_Sequeue (c_SeQueue * Q) {if (num==0) return 1; else return 0;}

(2) chain queue

Chained queues are called chained queues. Similar to the chain stack, the chain queue can be implemented with a single linked list. According to the team's FIFO principle, a head pointer and a tail pointer can be set for convenience.

Chain queues are defined as follows:

Typedef struct node {datatype data; struct node next;} QNode; typedef struct {QNode * front, * rear;} LQueue; LQueue * Q; / / define a pointer to the chain queue

1) create an empty queue with the lead node:

LQueue * Init_LQueue () {LQueue * Q front; Q = malloc (sizeof (LQueue)); / / Application head-tail pointer node p = malloc (sizeof (QNode)); / / Application chain head node p-> next = NULL; Q-> front = p; Q-> rear = p; return q;}

2) join the team:

Void In_LQueue (LQueue * Q, datatype x) {QNode * p; p = malloc (sizeof (QNode)); / / apply for a new node p-> data = x; p-> next = NULL; Q-> rear-> next = p; Q-> rear = p;}

3) judging the team empty:

Int Empty_LQueue (LQueue * Q) {if (Q-> front = = Q-> rear) return 0; else return 1;}

4) out of the team:

Int Out_LQueue (LQueue * Q, datatype * x) {QNode * p; if (Empty_Lqueue (Q)) {return 0;} else {pendant Q-> front- > next; Q-> front- > next=p- > next; * x = p-> data;// line head element in x free (p) If (Q-> front- > next = = NULL) {/ / when there is only one element, the queue is empty after leaving the queue Q-> rear = Q-> front; return 1;}} this ends the study of "how to implement the C++ stack and queue". I hope to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 0

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Internet Technology

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report