This article describes a stack data structure to write programs in C on various platforms using a single linked list data structure as a stack data store with examples of the array as storage and test the operation with the microcontroller board LGT8F328P, SAM-D21, ESP8266, ESP32 and ESP32-S2 as shown in Figures 1 and 2. In case of wanting to use with other platforms, you can still modify the code for use such as the same.
Stack data structure
A stack is a finite-member data structure that operates based on LIFO (Last-in-First-out) principles, or the first imported data is removed later or the later imported data is removed first. As shown in Figure 3, this can be used for executing subprograms/repetitions by remembering the executed memory location or being called to the next location for the processor to execute instructions in another position. It can also be applied to prefix mathematical expressions to convert infix expressions to prefixes to process results from prefixes using a queue structure (The C language queue data structure will be discussed in the next article, the Python language can be found in the Queue Data Structure article).
There are two components of a data stack structure:
- Storage node which can choose to use an array of data structures as storage or a linked list data structure
- A set of instructions for operating data structures under stack operations.
The stack operation consists of two commands:
- push(X) For importing x data to be stored in the stack as shown in Figure 4.
- export_value = pop() to export data from a stack where data is the last data imported last, as shown in Figure 5.
There are two working methods for importing:
- Import data into a stack that can still store data.
- Import data to a stack with a defined integer number of members which resulting in Stack Overflow
There are two types of ejection cases as well:
- Case of removal from the stack containing data.
- The case of data export with empty stack results in a problem called Stack Underflow.
Algorithm of push(x)
To import data into a stack data structure, follow these steps:
- Check the number of members
- If there are already full members, report Stack Overflow and exit.
- Put the data to the end of the stack.
- Increase the number of stack members counter by one.
Algorithm of pop()
There are steps for removing data from the stack:
- Check the number of members in the stack.
- If member count is 0, report Stack Underflow and exit.
- Remember the last member
- Decrease the number of stack members counter by 1 value.
- Return the member remembered from item 3.
array-based stack
You can use a stacked data structure to store data in an array variable by creating an array variable and a variable to store the number of members stored in the stack. Then write a function to perform push() and pop() functions as follows.
Data
The variable to store data and the number of members is written as follows.
const uint8_t stkMaxElm = 5;
uint8_t stkData[5];
uint8_t stkElmCounter = 0;
bool stkInit() {
stkElmCounter = 0;
return true;
}
push
bool stkPush( uint8_t x ) {
if (stkElmCounter == stkMaxElm) {
return false;
}
stkData[stkElmCounter] = x;
stkElmCounter += 1;
return true;
}pop
bool stkPop( uint8_t& x ) {
if (stkElmCounter == 0) {
return false;
}
x = stkData[stkElmCounter - 1];
stkElmCounter -= 1;
return true;
}
Example Code
An example program for testing stack functionality is as follows. The sample result is as shown in Figure 6.
const uint8_t stkMaxElm = 5;
uint8_t stkData[5];
uint8_t stkElmCounter = 0;
bool stkInit() {
stkElmCounter = 0;
return true;
}
bool stkPush( uint8_t x ) {
if (stkElmCounter == stkMaxElm) {
return false;
}
stkData[stkElmCounter] = x;
stkElmCounter += 1;
return true;
}
bool stkPop( uint8_t& x ) {
if (stkElmCounter == 0) {
return false;
}
x = stkData[stkElmCounter - 1];
stkElmCounter -= 1;
return true;
}
void stkShow() {
Serial.print("Stack data=[ ");
for (int i = 0; i < stkElmCounter; i++) {
Serial.print(stkData[i]);
Serial.print(" ");
}
Serial.println("]");
}
void setup() {
Serial.begin( 9600 );
stkInit();
stkShow();
for (int i = 0; i < 6; i++) {
Serial.print("push(");
Serial.print(i);
Serial.print(") ... ");
if (stkPush(i)) {
Serial.println("done.");
stkShow();
} else {
Serial.println(" Stack overflow!");
}
}
uint8_t data;
for (int i = 0; i < 6; i++) {
Serial.print("pop() ... ");
if (stkPop(data)) {
Serial.println(data);
stkShow();
} else {
Serial.println(" Stack underflow!");
}
}
}
void loop() {
}
Stack using a single link list.
The case of using a single link list instead of an array saves the program at startup because memory is not required to pre-empt the program before it starts. However, there may be problems with the number of stack members being less than intended when there is insufficient memory for reservation. However, experimenting with building a stack using a single link list is another option for practicing programming and experimenting with a different function from the array approach.
Data
The data or variables for a stack like this are the same as for creating a single link list: the node structure must be created. There is a pointer variable to the first node, the last node, and has reserved and unreserved for adding and removing nodes:
const uint8_t stkMaxElm = 5;
struct stkNode {
uint8_t data;
stkNode * next;
};
stkNode * stkRoot;
stkNode * stkCurrentNode;
stkNode * stkNewNode;
uint8_t stkElmCounter = 0;
bool stkInit() {
stkElmCounter = 0;
stkRoot = NULL;
stkCurrentNode = NULL;
stkNewNode = NULL;
return true;
}push
Push() or adding a node has more steps using arrays:
- If the number of members is reached, exit the function.
- Reserves the memory, If there is not enough, exit the function.
- Put the x value in the data.
- If it is the first node, define stkRoot and stkCurrentNode ooints to the node created from clause 2.
- Increase the number of members counter
bool stkPush( uint8_t x ) {
if (stkElmCounter == stkMaxElm) {
return false;
}
stkNewNode = (stkNode*)malloc( sizeof( stkNode ) );
if (stkNewNode == NULL) {
return false;
}
stkNewNode->next = NULL;
stkNewNode->data = x;
if (stkElmCounter == 0) {
stkRoot = stkNewNode;
} else {
stkCurrentNode->next = stkNewNode;
}
stkCurrentNode = stkNewNode;
stkElmCounter += 1;
return true;
}
pop
The pop() procedure works as follows.
- If the number of members is 0, exit the function.
- If there is only one node, delete the first node and set stkRoot and stkCurrentNode to NULL.
- In other cases, delete the last node.
- Decrease the number of members of the node by 1.
bool stkPop( uint8_t& x ) {
if (stkElmCounter == 0) {
return false;
}
if (stkRoot == stkCurrentNode) {
x = stkCurrentNode->data;
free(stkCurrentNode);
stkRoot = NULL;
stkCurrentNode = NULL;
} else {
x = stkCurrentNode->data;
stkNode * currentNode = stkRoot;
while (currentNode->next != stkCurrentNode) {
currentNode = currentNode->next;
}
currentNode->next = NULL;
free(stkCurrentNode);
stkCurrentNode = currentNode;
}
stkElmCounter -= 1;
return true;
}Example Code
An example program for using a single link list for a stacked data structure is as follows. The result of the work is the same as using the array in Figure 6.
const uint8_t stkMaxElm = 5;
struct stkNode {
uint8_t data;
stkNode * next;
};
stkNode * stkRoot;
stkNode * stkCurrentNode;
stkNode * stkNewNode;
uint8_t stkElmCounter = 0;
bool stkInit() {
stkElmCounter = 0;
stkRoot = NULL;
stkCurrentNode = NULL;
stkNewNode = NULL;
return true;
}
bool stkPush( uint8_t x ) {
if (stkElmCounter == stkMaxElm) {
return false;
}
stkNewNode = (stkNode*)malloc( sizeof( stkNode ) );
if (stkNewNode == NULL) {
return false;
}
stkNewNode->next = NULL;
stkNewNode->data = x;
if (stkElmCounter == 0) {
stkRoot = stkNewNode;
} else {
stkCurrentNode->next = stkNewNode;
}
stkCurrentNode = stkNewNode;
stkElmCounter += 1;
return true;
}
bool stkPop( uint8_t& x ) {
if (stkElmCounter == 0) {
return false;
}
if (stkRoot == stkCurrentNode) {
x = stkCurrentNode->data;
free(stkCurrentNode);
stkRoot = NULL;
stkCurrentNode = NULL;
} else {
x = stkCurrentNode->data;
stkNode * currentNode = stkRoot;
while (currentNode->next != stkCurrentNode) {
currentNode = currentNode->next;
}
currentNode->next = NULL;
free(stkCurrentNode);
stkCurrentNode = currentNode;
}
stkElmCounter -= 1;
return true;
}
void stkShow() {
Serial.print("Stack data=[ ");
stkNode * currentNode = stkRoot;
while (currentNode) {
Serial.print(currentNode->data);
Serial.print(" ");
currentNode = currentNode->next;
}
Serial.println("]");
}
void setup() {
Serial.begin( 9600 );
stkInit();
stkShow();
for (int i = 0; i < 6; i++) {
Serial.print("push(");
Serial.print(i);
Serial.print(") ... ");
if (stkPush(i)) {
Serial.println("done.");
stkShow();
} else {
Serial.println(" Stack overflow! or not enough memory!");
}
}
uint8_t data;
for (int i = 0; i < 6; i++) {
Serial.print("pop() ... ");
if (stkPop(data)) {
Serial.println(data);
stkShow();
} else {
Serial.println(" Stack underflow!");
}
}
}
void loop() {
}Conclusion
From this article, you will find that the working principle of a stacked data structure is that it has to work in a LIFO way, which takes the last imported data out of the stack first. Make the order of the data stored in and out of the stack swap. Therefore, it is a new method for returning data. It has also been applied to convert the form of an expression from an infix expression to a prefix or postfix. Finally, have fun with programming.
(C) 2022, By Jarut Busarathid and Danai Jedsadathitikul
Updated 2022-03-06