A Brief Discussion on Stacks and Queues in Embedded Data Structures

Stack

1. Basic Concept of Stack

A stack (Stack) is a linear list that allows insertion or deletion only at one end. First, a stack is a type of linear list, but it restricts operations to only one end for insertion and deletion.

The end where insertion and deletion are not allowed is called the stack bottom (Bottom).

A Brief Discussion on Stacks and Queues in Embedded Data Structures

Stack top (top): The end of the linear list where insertion and deletion are allowed.
Stack bottom (bottom): The fixed end where insertion and deletion are not allowed.
Empty stack: A stack that contains no elements.

The top element of the stack is always the last one pushed onto the stack and is the first one to be popped off. The bottom element is the first one pushed onto the stack and the last one to be popped off. Therefore, the stack has a last-in, first-out (LIFO) characteristic, also known as a LIFO list.

2. Basic Operations of Stack

InitStack(&S): Initializes an empty stack S.

StackEmpty(S): Determines if a stack is empty; returns true if empty, otherwise returns false.

Push(&S, x): Pushes x onto the stack (insertion operation); if stack S is not full, x is added to become the new stack top.

Pop(&S, &x): Pops the top element from the stack (deletion operation); if stack S is not empty, the top element is popped and returned in x.

GetTop(S, &x): Reads the top element of the stack; if stack S is not empty, the top element is returned in x.

DestroyStack(&S): Destroys the stack and releases the storage space occupied by S (“&” indicates reference call).

3. Sequential Storage Structure of Stack and Implementation of Basic Operations

1) Sequential Storage Structure of Stack

A stack that uses sequential storage is called a sequential stack. It utilizes a group of contiguous storage units to store data elements from the bottom to the top of the stack, along with a pointer (top) indicating the position of the current top element.

If the length of the storage stack is StackSize, then the top position must be less than StackSize. When the stack contains one element, top equals 0, so the condition for an empty stack is typically defined as top equal to -1.

#define MaxSize 50// Define the maximum number of elements in the stack
typedef struct{
   ElemType data[MaxSize];// Store elements in the stack
   int top;// Stack top pointer
}SqStack;

2) Basic Operations of Stack

1. Initialization

void InitStack(SqStack &S){
S.top = -1;// Initialize stack top pointer
}

2. Check if Stack is Empty

bool StackEmpty(SqStack S){
if(S.top == -1)// Stack is empty
return true;
else// Stack is not empty
return false;
}

3. Push onto Stack

bool Push(SqStack &S, ElemType x){
if(S.top == MaxSize - 1)// Stack is full, error
return false;
S.data[++S.top] = x;// Pointer increments first, then push
return true;
}

4. Pop from Stack

bool Pop(SqStack &S, ElemType &x){
if(S.top == -1)// Stack is empty, error
return false;
    x = S.data[S.top--];// Pop first, then decrement pointer
return true;
}

5. Read Top Element of Stack

bool GetTop(SqStack S, ElemType &x){
if(S.top == -1)// Stack is empty, error
return false;
     x = S.data[S.top];// x records the top element
return true;
}

6. Shared Stack

A shared stack (Shared Stack) is a special data structure that allows two or more stacks to share the same array as storage space. In this array, the two stacks grow towards each other from both ends, which can be described as “growing from both heads”.

Specifically, suppose we have an array of length n, which is divided into two parts, serving as the storage space for two stacks. The left stack grows from index 0 of the array to the right, while the right stack grows from index n-1 to the left. When the top pointers of the two stacks meet, it indicates that the middle position of the array has been filled by both stacks, and at this point, the push operation can no longer continue.

The implementation of a shared stack is similar to that of a regular stack, but it requires attention to the following points:

A shared stack needs to additionally record the top pointers of the left and right stacks, topL and topR;

When the left stack grows and meets the right stack, i.e., topL = topR + 1, it indicates that the left stack is full;

When the right stack grows and meets the left stack, i.e., topR = topL – 1, it indicates that the right stack is full;

Push, pop, and other operations also need to use topL and topR to determine which stack to operate on.

Below is an example of implementing basic operations for a shared stack:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int topL;
    int topR;
} SharedStack;

void init(SharedStack* stack){
    stack->topL = -1;
    stack->topR = MAX_SIZE;
}

int is_empty_left(SharedStack* stack){
return stack->topL == -1;
}

int is_empty_right(SharedStack* stack){
return stack->topR == MAX_SIZE;
}

int is_full(SharedStack* stack){
return stack->topL == stack->topR - 1;
}

void push_left(SharedStack* stack, int item){
if(is_full(stack)){
printf("Stack overflow!\n");
return;
}
    stack->data[++stack->topL] = item;
}

void push_right(SharedStack* stack, int item){
if(is_full(stack)){
printf("Stack overflow!\n");
return;
}
    stack->data[--stack->topR] = item;
}

int pop_left(SharedStack* stack){
if(is_empty_left(stack)){
printf("Left stack underflow!\n");
return -1; // Can return an appropriate error code or take other actions as needed
}
return stack->data[stack->topL--];
}

int pop_right(SharedStack* stack){
if(is_empty_right(stack)){
printf("Right stack underflow!\n");
return -1; // Can return an appropriate error code or take other actions as needed
}
return stack->data[stack->topR++];
}

int main(){
    SharedStack stack;
init(&stack);
push_left(&stack, 1);
push_right(&stack, 2);
push_left(&stack, 3);
push_right(&stack, 4);

printf("%d\n", pop_left(&stack)); // Output: 3
printf("%d\n", pop_right(&stack)); // Output: 4
printf("%d\n", pop_left(&stack)); // Output: 1
printf("%d\n", pop_right(&stack)); // Output: 2

return 0;
}

In the above code, a shared stack data structure SharedStack is defined, which contains an integer array data as a container for storing stack elements, and uses topL and topR to represent the top pointers of the left and right stacks.

The code mainly includes the following functions:

The init function initializes the shared stack, setting the top pointers of the left and right stacks to -1 and MAX_SIZE.

The is_empty_left and is_empty_right functions are used to determine if the left and right stacks are empty.

The is_full function is used to determine if the shared stack is full.

The push_left and push_right functions are used to push elements onto the left and right stacks, respectively.

The pop_left and pop_right functions are used to pop elements from the left and right stacks and return the top elements.

In the main function, a variable of type SharedStack named stack is created, and it is initialized by calling the init function. Then, elements 1, 2, 3, and 4 are pushed onto the shared stack using the push_left and push_right functions. Finally, the elements are popped from the stack and the results are printed using consecutive calls to pop_left and pop_right.

Running the example code will output:

Queue

1. Basic Concept of Queue

A queue, abbreviated as queue, is a linear list with restricted operations, allowing insertion at one end and deletion at the other end. Inserting elements into the queue is called enqueueing; deleting elements is called dequeueing.

Front (front): The end where deletion is allowed, also known as the head of the queue.
Rear (rear): The end where insertion is allowed.
Empty queue: A queue that contains no elements.

2. Basic Operations of Queue

InitQueue(&Q): Initializes the queue, constructing an empty queue Q.

QueueEmpty(Q): Checks if the queue is empty; returns true if empty, otherwise returns false.

EnQueue(&Q, x): Enqueues x; if queue Q is not full, adds x to become the new rear.

DeQueue(&Q, &x): Dequeues; if queue Q is not empty, deletes the front element and returns it in x.

GetHead(Q, &x): Reads the front element of the queue; if queue Q is not empty, assigns the front element to x.

3. Sequential Storage Structure of Queue

1) Sequential Queue

The sequential storage type of the queue can be described as:

#define MAXSIZE 50// Define the maximum number of elements in the queue
typedef struct{
	ElemType data[MAXSIZE];// Store queue elements
	int front, rear;
}SqQueue;

Initial state (empty queue condition): Q->front == Q->rear == 0.

Enqueue operation: When the queue is not full, first send the value to the rear element, then increment the rear pointer.

Dequeue operation: When the queue is not empty, first take the value of the front element, then increment the front pointer.

In the figure, the queue appears to have an “overflow”, but it is not a true overflow; it is a “false overflow” phenomenon.

2) Circular Queue

The method to solve false overflow is to start from the beginning again when the end is full, which means the head and tail connect in a loop. This type of sequential storage structure of the queue is called a circular queue.

When the front pointer Q->front = MAXSIZE – 1, moving one position forward automatically goes to 0, which can be implemented using the modulo operation (%).

Initially: Q->front = Q->rear = 0

Incrementing the front pointer: Q->front = (Q->front + 1) % MAXSIZE

Incrementing the rear pointer: Q->rear = (Q->rear + 1) % MAXSIZE

Queue length: (Q->rear – Q->front + MAXSIZE) % MAXSIZE

Can a queue not implemented using a linked list be a dynamic queue? When there is no space, will it allocate space, and will it not produce false overflow?

This is indeed the case. When dynamically creating a queue, it simply continues to request memory space, and even if the previous dequeue operation releases the front space, the pointer will still move forward until it reaches the upper limit of the memory reserved for the program, which can be fatal for programs with very frequent queue operations. At this point, it is necessary to optimize the queue using a more efficient structure—a circular queue.

The thinking behind a circular queue is simple: given the size range of the queue, as long as the back of the queue is full, it will insert from the front of the queue to achieve the effect of reusing space. Since the design thinking of the circular queue resembles a ring, it is often represented with a circular diagram, but note that it is not a true ring; the circular queue is still linear.

So, what are the conditions for determining if a circular queue is empty or full?

Clearly, the condition for an empty queue is Q->front == Q->rear. If the speed of enqueueing elements is faster than that of dequeueing, the rear pointer will quickly catch up with the front pointer, and at this point, the condition for being full is also Q->front == Q->rear.

To distinguish between an empty and a full queue, there are three handling methods:

(1) Sacrifice one unit to distinguish between empty and full queues.

When enqueuing, use one less queue unit; this is a common practice, agreeing that “the front pointer being at the next position of the rear pointer indicates that the queue is full”.

Condition for full queue: (Q->rear + 1) % Maxsize == Q->front

Condition for empty queue remains: Q->front == Q->rear

Number of elements in the queue: (Q->rear – Q->front + Maxsize) % Maxsize

(2) Add a data member for the number of elements in the type.

Condition for empty queue: Q->size == 0;

Condition for full queue: Q->size == Maxsize.

Both situations have Q->front == Q->rear.

(3) Add a tag data member in the type to distinguish between full and empty queues.

When tag equals 0, if deletion causes Q->front == Q->rear, it is empty;

When tag equals 1, if insertion causes Q->front == Q->rear, it is full.

3) Basic Operations of Queue

1. Enqueue

When performing the enqueue (push) operation, we first need to check if the queue is empty. If the queue is empty, we need to point both the head and tail pointers to the first node, i.e., front = rear = n.

If the queue is not empty, we only need to move the tail node backward by continuously moving the next pointer to point to the new node to form the queue.

The code can be represented as:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void init(Queue* queue){
    queue->front = 0;
    queue->rear = 0;
}

int is_empty(Queue* queue){
return queue->front == queue->rear;
}

int is_full(Queue* queue){
return queue->rear == MAX_SIZE;
}

void enqueue(Queue* queue, int item){
if(is_full(queue)){
printf("Queue overflow!\n");
return;
}
    queue->data[queue->rear++] = item;
}

int dequeue(Queue* queue){
if(is_empty(queue)){
printf("Queue underflow!\n");
return -1; // Can return an appropriate error code or take other actions as needed
}
return queue->data[queue->front++];
}

int main(){
    Queue queue;
init(&queue);

enqueue(&queue, 1);
enqueue(&queue, 2);
enqueue(&queue, 3);

printf("%d\n", dequeue(&queue)); // Output: 1
printf("%d\n", dequeue(&queue)); // Output: 2
printf("%d\n", dequeue(&queue)); // Output: 3

return 0;
}

A queue data structure Queue is defined, which contains an integer array data as a container for storing queue elements, using front and rear to represent the front and rear pointers of the queue.

The code mainly includes the following functions:

The init function initializes the queue, setting both front and rear to 0.

The is_empty function checks if the queue is empty.

The is_full function checks if the queue is full.

The enqueue function adds elements to the end of the queue.

The dequeue function removes the front element from the queue and returns it.

In the main function, a variable of type Queue named queue is created, and it is initialized by calling the init function. Then, elements 1, 2, and 3 are enqueued into the queue using the enqueue function. Finally, the elements are dequeued from the queue and the results are printed using consecutive calls to dequeue.

Running the code will output:

1
2
3

Summary:

Stacks and queues are common and important data structures in computer science. A stack is a last-in, first-out (LIFO) data structure, with operations restricted to the top of the stack, suitable for function calls, expression evaluation, and other scenarios. A queue is a first-in, first-out (FIFO) data structure, with operations restricted to the front and rear, suitable for task scheduling, buffer management, and other scenarios. Mastering the principles and applications of stacks and queues is crucial for algorithm design and program development. They can improve code efficiency, readability, and solve various practical problems. Flexibly using stacks and queues can enhance algorithm quality and the ability to handle complex problems. Through learning and practice, we can better utilize stacks and queues to solve practical problems and develop efficient, robust software systems.