# Implementation of stack and queue related algorithms

In the process of learning data structure and algorithm, in order to better understand the implementation of the algorithm, this paper implements the algorithms of stack and queue in the course. This article only provides algorithm code reference. For detailed explanation of relevant algorithms, please refer to the video course of Mr. Wang Zhuo of Qingdao University: Data and structure of Qingdao University (Wang Zhuo)

# Implementation of stack

### Define identifier

```#include <cstdlib>
#include <iostream>
using namespace std;
// Function result status code
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
//Status is the type of function and its value is the result status code of the function
typedef int Status;
typedef int SElemType; // Define data element types
```

## Chain implementation of stack

### Define chain stack data structure

```// Define chain stack data structure
typedef struct StackNode {
SElemType data; // Data domain
struct StackNode* next; // Pointer field
```

### Initialize chain stack

```// Initialization of chain stack
S = NULL;
}
```

### Judge whether the chain stack is empty

```// Judge whether the chain stack is empty
if (S == NULL)return TRUE;
else return FALSE;
}
```

### Push

```// Input of chain stack
Status Push(LinkStack& S, SElemType e) {
LinkStack p = new StackNode; // Generate new node p
p->data = e; // Set the new node data field to e
p->next = S; // Insert the new node into the top of the stack
S = p; // Modify stack top pointer
return OK;
}
```

### Out of stack

```// Out of chain stack
Status Pop(LinkStack& S, SElemType& e) {
if (S == NULL)return ERROR;
e = S->data;
S = S->next;
delete p;
return OK;
}
```

### Access stack top element

```// Get stack top element
int GetTop(LinkStack S, SElemType &e) {
if (S != NULL) {
e = S->data;
return OK;
}
else {
e = -2;
return OVERFLOW;
}
}
```

### Test code and output results

##### Test code:

The input data field is [0, + ∞]. If the input data is - 1, the stack out operation will be executed.

```int main()
{
SElemType data;
int code;
InitStack(S);
for (int i = 0; i <= MAXSIZE; i++) {
cout << "Merge input data elements into stack:";
cin >> data;
if (data == -1) { // Enter - 1 to perform the queue out operation
cout << "Add stack top element:" << head_data << " Out of stack" << endl;
} // if
else {
cout << data << " Push " << endl;
Push(S, data);
} // else
cout << "At this time, the top element of the stack is:" << head_data << endl;
if (StackEmpty(S) == TRUE) {
cout << "All data has been out of the stack" << endl;
break;
} // if
} // for
system("pause");

return 0;
}
```

## Sequential implementation of stack

### Define sequential stack data structure

```typedef struct {
SElemType *base; // Stack bottom pointer
SElemType *top;  // Stack top pointer
int stacksize;   // Maximum available capacity of stack
}SqStack;

```

### Initialization sequence stack

```// Initialization stack
Status InitStack(SqStack& S) { // Construct an empty stack
S.base = new SElemType[MAXSIZE]; //or
if (!S.base)exit(OVERFLOW); // Storage allocation failed
S.top = S.base; // Stack top pointer equals stack bottom pointer
S.stacksize = MAXSIZE;
return OK;
}
```

### Destroy sequence stack

```// Destroy stack
Status DestroyStack(SqStack& S) {
if (S.base) {
delete S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}
```

### Empty sequence stack

```// Empty stack
Status ClearStack(SqStack S) {
if (S.base)S.top = S.base;
return OK;
}
```

### Judge whether the sequence stack is empty

```// Judge whether it is an empty stack
Status StackEmpty(SqStack S) {
// If the stack is empty, return true; Otherwise, false is returned
if (S.top == S.base)return TRUE;
else return FALSE;
}
```

### Find the length of sequential stack

```// Find the length of the stack
int StackLength(SqStack S) {
return S.top - S.base;
}
```

### Push

```// Stack operation
// Judge whether the stack is full. If it is full, an error (overflow) will be reported
// Push element e into the top of the stack
// Stack top pointer plus 1
Status Push(SqStack& S, SElemType e) {
if (S.top - S.base == S.stacksize)return ERROR; // Stack full
*S.top++ = e;
return OK;
}
```

### Out of stack

```// Stack out operation
// Judge whether the stack is empty. If it is empty, there will be an error (underflow)
// Get stack top element e
// Stack top pointer minus one
Status Pop(SqStack& S, SElemType& e) {
if (S.top == S.base)return ERROR;
e = *--S.top;
return OK;
}
```

### Access order stack top element

```// Get stack top element
int GetTop(SqStack S, SElemType& e) {
if (S.top == S.base) {
e = -2;
return OVERFLOW;
}
else {
e = *--S.top;
return OK;
}
}
```

### Test code and output results

##### Test code:

The input data field is [0, + ∞]. If the input data is - 1, the stack out operation will be executed.

```int main()
{
SElemType data;
SqStack S;
int code;
InitStack(S);
for (int i = 0; i <= MAXSIZE; i++) {
cout << "Merge input data elements into stack:";
cin >> data;
if (data == -1) { // Enter - 1 to perform the stack out operation
cout << "Add stack top element:" << head_data << " Out of stack" << endl;
} // if
else {
cout << data << " Push " << endl;
Push(S, data);
} // else
int Slen = StackLength(S);
cout << "At this time, the stack length is:" << Slen << "\t Stack top elements are:" << head_data << endl;
if (StackEmpty(S) == TRUE) {
cout << "All data has been out of the stack" << endl;
break;
} // if
} // for
system("pause");

return 0;
}
```

# Implementation of queue

### Define identifier

```#include <cstdlib>
#include <iostream>
using namespace std;
// Function result status code
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
#define MAXQSIZE 100 / / maximum queue length
//Status is the type of function and its value is the result status code of the function
typedef int Status;
typedef int QElemType; // Define data element types
```

## Chain implementation of queue

### Define chained queue data structure

#### Define data node structure

```typedef struct Qnode {
QElemType data; // Data domain
struct Qnode* next; // Pointer field
}Qnode,*QuenePtr;
```

#### Defines the head and tail pointer of a chained queue

```typedef struct {
QuenePtr front; // Queue head pointer
QuenePtr rear; // Tail pointer
```

### Initialize chained queue

```// Queue initialization
Q.front = Q.rear = new Qnode;
if (!Q.front)exit(OVERFLOW);
Q.front->next =NULL;
return OK;
}
```

### Destroy chain queue

```// Queue destruction
while (Q.front) {
QuenePtr p = Q.front->next;
delete Q.front;
Q.front = p;
}
return OK;
}
```

### Join the team

```// Queue up
Status EnQueue(LinkQueue& Q, QElemType e) {
QuenePtr p = new Qnode;
if (!p)exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
```

### Out of the team

```// Queue out
Status DeQueue(LinkQueue& Q, QElemType& e) {
if (Q.front == Q.rear)return ERROR;
QuenePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)Q.rear = Q.front;
delete p;
return OK;
}
```

```// Queue header element
if (Q.front == Q.rear) {
return OVERFLOW;
}// if
else {
e = Q.front->next->data;
return OK;
}
}
```

### Test code and output structure

##### Test code:

The input data field is [0, + ∞]. If the input data is - 1, the stack out operation will be executed.

```int main()
{
QElemType data;
int code;
InitQueue(Q);
for (int i = 0; i <= MAXQSIZE; i++) {
cout << "Enter data elements and join the team:";
cin >> data;
if (data == -1) { // Enter - 1 to perform the queue out operation
} // if
else {
cout << data << " Join the team" << endl;
EnQueue(Q, data);
} // else
if (code == -2) {
cout << "All data out of the queue,Perform the destroy queue operation" << endl;
DestroyQueue(Q);
cout << "Queue destroyed" << endl;
break;
} // if
} // for
system("pause");

return 0;
} // main
```

## Sequential implementation of queue

### Define sequential queue data structure (circular queue)

```// Define sequential queue data structure
typedef struct {
QElemType* base; //Initialize dynamic allocation of sequential space
int rear;  // Tail pointer
}SqQueue;
```

### Initialize sequential queue

```// Queue initialization
Status InitQueue(SqQueue& Q) {
Q.base = new QElemType[MAXQSIZE]; // Allocate array space
if (!Q.base)exit(OVERFLOW); // memory allocation failed
Q.front = Q.rear = 0; // The head pointer and tail pointer are set to 0 and the queue is empty
return OK;
}
```

### Get sequence queue length

```// Find the length of the queue
int QueueLength(SqQueue Q) {
return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
```

### Queue up (circular queue)

```// Queue up of circular queue
Status EnQueue(SqQueue& Q, QElemType e) {
if ((Q.rear + 1) % MAXQSIZE == Q.front)return ERROR; // Team full
Q.base[Q.rear] = e; // New elements added to the tail of the team
Q.rear = (Q.rear + 1) % MAXQSIZE; // Tail pointer + 1
return OK;
}
```

### Out of line (circular queue)

```// Out of queue of circular queue
Status DeQueue(SqQueue& Q, QElemType& e) {
if (Q.front == Q.rear)return ERROR; // Team air
e = Q.base[Q.front];  // Save queue header element
Q.front = (Q.front + 1) % MAXQSIZE; // Team leader pointer + 1
return OK;
}
```

```// Take the team head element
if (Q.front != Q.rear) {
return Q.base[Q.front]; // Return queue header element
}
else {
return OVERFLOW; // Return error code
}
}
```

### Test code and output structure

##### Test code:

The input data field is [0, + ∞]. If the input data is - 1, the stack out operation will be executed.

```int main()
{
QElemType data;
SqQueue Q;
InitQueue(Q);
for (int i = 0; i <= MAXQSIZE; i++) {
cout << "Enter data elements and join the team:";
cin >> data;
if (data == -1) { // Enter - 1 to perform the queue out operation
} // if
else {
cout << data << " Join the team" << endl;
EnQueue(Q, data);
} // else
int Qlen = QueueLength(Q);
cout << "At this time, the queue length is:" << Qlen << "\t The team head elements are:" << head_data << endl;
if (QueueLength(Q) == 0) {
cout << "All data are out of the queue" << endl;
break;
} // if
} // for
system("pause");

return 0;
} // main
```
##### Output result:

Keywords: C++ Algorithm data structure

Added by czambran on Thu, 10 Feb 2022 07:41:56 +0200