preface
This chapter begins part 2 of Data Structures, Stacks and queues: stacks:
- Stack storage structure
- Basic stack operations
Queue:
- The storage structure of queues
- Basic operations on queues
The stack
We have similar to the advanced after the cartridge data structure called the stack, the stack is limited only to insert and delete operation in the footer of the linear table, we allow the insertion and deletion of the end is called a stack, on the other side is called the bottom of the stack, does not contain any data element is called an empty stack, stack and said after the last in a linear list, referred to as “LIFO structure.
A stack is first and foremost a linear table, that is, the stack elements have a linear relationship, that is, a precursor and a successor relationship, but it is a special kind of linear table.
The special thing about the stack is that it restricts the insertion and deletion positions of this linear table, which always occur only at the top of the stack. So the bottom of the stack is fixed, and the most advanced stack is at the bottom of the stack.
The operation of inserting a stack is called pushing; Deleting a stack is called making a stack.
1. Storage structure of the stack
The data storage structure corresponding to the data elements used to store the stack is called the storage structure of the stack.
1.1 Sequential storage structure of stacks
The stack is a special case of the linear table, so the sequential storage structure of the stack is actually the abbreviation of the sequential storage structure of the linear table, which is called the sequential stack for short. Linear tables are implemented by arrays. For such linear tables as stacks, which can only be inserted and deleted at one end, it is appropriate to use one end of the array subscript 0 (the bottom of the stack remains the same, and only the top of the stack changes) as the bottom of the stack.
The sequential stack is defined as follows:
typedef struct
{
int data[maxsize]; // Define an array of maxsize to hold data elements in the stack
int top; // Top of stack pointer
}SqStack; // Sequence stack definition
Copy the code1.2 Chain storage structure of stack
The data structure in which a stack is stored by placing the top of the stack at the head of a single linked list is called a linked stack.
Stack nodes are defined as follows:
typedef struct LNode
{
int data; / / data domain
struct LNode *next; / / pointer field
}LNode; // stack node
Copy the code2. Stack operation
2.1 Operation of sequential stack
For the sequential stack, there are four elements, including two special states and two operations.
Special state: 1) Empty stack state: ST. top == -1, some use St. top = 0 to indicate empty stack, this time the top position of the stack is 0. 2) Full stack state: St. top == MAXsize -1 indicates full stack. Maxsize is the maximum number of elements in the stack. Maxsize -1 is the position of the top element in the array when the stack is full, since the array position starts from 0.
Operations: Sequential stack loading and unloading operations are performed at the top of the stack, so you only need to change the top position to achieve the purpose of loading and unloading.
1) Initialization stack:
void initStack(SqStack &st) // Initialize the stack
{
st.top = - 1; // Set the top pointer to -1
}
Copy the code2) Stack operation:
int push(SqStack &st,int x)
{
if(st.top == maxsize- 1) // Check whether the stack is full. If so, the stack cannot be pushed
return 0;
++(st.top); // Add 1 to the top of the stack
st.data[st.top] = x // put x in st.top
return 1;
}
Copy the code3) Out of the stack operation: out of the stack and into the stack are corresponding operations
int push(SqStack &st,int x)
{
if(st.top == - 1) // Check whether the stack is empty. If it is empty, the stack cannot be unloaded
return 0;
x = st.data[st.top] // Remove the top element from the stack
--(st.top); // The position of the top pointer on the stack is reduced by 1
return 1;
}
Copy the code4) Simplified version of the operation:
/* Initialize the stack */
int stack[maxsize];
int top = - 1;
/* element x is pushed */
stack[++top] = x
/* element x out of the stack */
x = stack[top--]
/* Note the difference between ++top and top++ */
top = 1
a = ++top
b = top++
a = 2
b = 1
Copy the code2.2 Operation of chain stack
A chain stack, as opposed to a sequential stack, has four elements, including two states and two operations.
Status: 1) Empty stack: LST -> next == NULL, that is, the stack is empty when there is no successor node. 2) Full stack: If the storage space is infinite, there will be no full stack.
Operation: the chain stack is the head plug method to establish the linked list insertion operation; Unstack is the operation of deleting a single linked list.
1) Stack initialization:
void initStack(LNode *&lst)
{
lst = (LNode*)malloc(sizeof(LNode)); // Create a header
lst -> next = NULL; // The initial header points to NULL
}
Copy the code2) into the stack:
void push(LNode *lst,int x)
{
LNode *p;
p = (LNode*)malloc(sizeof(LNode)); // Apply node space for the pushed element
p -> next =NULL; // The initialization node does not point to any element
/* push, equivalent to list header */
p -> data = x; // Assign x to the range of p
p -> next = lst -> next; // the p pointer points to the node that LST was pointing to
lst -> next = p; // LST points to node p
}
Copy the code3) the stack:
int pop(LNode *lst,int &x)
{
LNode *p;
if(lst -> next == NULL) // If the stack is empty, the stack cannot be unloaded. And the stack will not be full, so at the time of the stack did not make a judgment
return 0;
/* unstack, which is equivalent to the deletion of nodes */
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);
return 1;
}
Copy the code4) Simplified version operation:
/* The element (indicated by pointer P) is pushed */
/* Similar to the head insertion method to create a list */
p -> next = lst -> next; // point the head of the empty stack to p
lst -> next = p; // pointer p to the empty stack header
/* Unstack operation (the unstack element is stored in x) */
/* Similar to a singly linked list */
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);
Copy the codeQueue:
A queue is a linear table that only allows insertion at one end and deletion at the other end. A queue is a first-in, first-out linear table, or FIFO. The end that allows insertion is called Rear, and the end that allows deletion is called Front. Inserting an element into the team is called entering the team, and the new element becomes the new element at the end of the team. Removing an element from a team is called a team exit, and when an element exits, its successor becomes the new team head element.
1. Storage structure of queues
A data structure used to store queue data elements.
1.1 Sequential storage structure of queues:
When a sequence table is used to store queues, the queue element exits at the queue head (subscript 0). When an element exits, all the elements behind the queue element move forward to ensure that the queue head is always at the subscript 0, which greatly increases the time complexity.
The data structure that uses a sequential table to store queue elements is called the sequential storage structure of a queue and is defined as follows:
typedef struct
{
int data[maxsize]; // Define an array
int front; // queue head pointer
int rear; // end of queue pointer
}SqQuene; // Sequence queue definition
Copy the code1.2 Chain storage structure of queues:
The data structure that uses a linked list to store queue elements is called the chained storage structure of a queue and is defined as follows:
Queue node type definition:
typedef struct QNode
{
int data; / / data domain
struct QNode *next; / / pointer field
}QNode; // Queue node type definition
Copy the codeChain team type definition:
typedef struct
{
QNode *front; // queue head pointer
QNode *rear; // end of queue pointer
}LiQuene; // Chain team type definition
Copy the code2. Perform queue operations
2.1 Circular Queue
Since the time complexity of queue exit is high, problems always need to be solved. Why should queue head appear at subscript 0? So there is no restriction that the queue elements must be stored in the first n cells of the array, so that the queue head element does not have to be at subscript 0. However, as the queue element exits, the queue head pointer moves backwards. Assume that the queue tail pointer is already at maxsize-1. At this time, although there is still storage space in the queue, the queue tail cannot enter the queue, as shown in the following figure:
Although the index of 0 and 1 location and space, but the line has been unable to have the new elements into the team, we call it “false overflow”, in order to solve the problem of this kind of false overflow, it puts forward the concept of circular queue, let the end of the queue is linked together, the head tail to the order of the storage structure called a circular queue.
The loop queue needs to lose some white space so that front=rear only appears when the queue is empty.
Elements of the loop queue:
Two states: queue empty state:
qu.rear = qu.front
Copy the code
Full team status:
(qu. Rear +1) % maxsize = = qu. The front
Copy the code
Two operations: element x queue operation (move the queue pointer)
qu.rear = (qu.rear+1)%maxSize;
qu.data[qu.rear] = x;
Copy the codeElement X platoon operation (move queue head pointer)
qu.front = (qu.front+1)%maxSize;
x = qu.data[qu.front];
Copy the codeInitialization queue algorithm:
void initQueue(SqQueue &qu)
{
qu.front = qu.rear = 0; The head and tail Pointers overlap and point0
}
Copy the codeQueue entry algorithm:
int enQueue(SqQueue &qu,int x)
{
if ((qu.rear + 1) % maxSize == qu.front) // If a team is full, it cannot enter the team
return 0;
qu.rear = (qu.reat+1)%maxSize; // If the team is not satisfied, move the last pointer first
qu.data[qu.rear] = x; // element x enters the queue
return 1;
}
Copy the codeQueue selection algorithm:
int enQueue(SqQueue &qu,int &x)
{
if (qu.rear == qu.front) If the queue is empty, the queue cannot be cleared
return 0;
qu.front = (qu.front+1)%maxSize; // If the queue is not empty, move the queue pointer first
x = qu.data[qu.front] ; // Element x plays out
return 1;
}
Copy the code2.2 chain team:
Chain queue is the use of chain storage structure to store queues. Chain team four elements: team empty and team full, element in and out of the team operation.
Queue empty state:
lqu -> rear == NULL; or lqu -> front == NULL
Copy the codeFull state: Generally there is no full state, as long as the memory is large enough.
Element queue operation (pointer P points to queue element)
lqu -> rear -> next = p;
lqu -> rear = p;
Copy the codeElement out of queue operation (x stores element out of queue)
p = lqu -> front;
lqu -> front = p -> next;
x = p -> data;
free(p);
Copy the codeInitializes the queue algorithm
void initQueue(LiQuene *&lqu)
{
lqu = (LiQueue*)malloc(sizeof(LiQueue));
lqu -> front = lqu -> rear = NULL;
}
Copy the codeJudge the queue empty algorithm
int isQueueEmpty(LiQueue *lqu)
{
if(lqu -> rear == NULL || lqu -> front == NULL)
return 1;
else
return 0;
}
Copy the codeThe algorithm of entrance
void enQueue(LiQueue *lqu,int x)
{
QNode *p;
p = (QNode*)malloc(sizeof(QNode));
p -> data = x;
p -> next =NULL;
if(lqu -> rear == NULL)
lqu -> front = lqu -> rear = p; // If the queue is empty, the new node is both the end of the queue and the beginning of the queue
else
{
lqu -> rear -> next = p; // Link the new node to the end of the queue, rear pointing to that node
lqu -> rear = p;
}
}
Copy the codeDequeue algorithm
int deQueue(LiQueue *lqu,int &x)
{
QNode *p;
if(lqu -> rear == NULL) // Check whether the queue is empty
return 0;
else
p = lqu -> front;
if(lqu -> front == lqu -> rear) // Unqueue when there is only one node in the queue
lqu -> front = lqu -> rear =NULL
else
lqu -> front = lqu -> front -> next;
x = p -> data;
free(q);
return 1;
}
Copy the code