CHAPTER 3: DATA STRUCTURE IN C/C++
S e c t i o n 3 . 3 : Stack & Queue
COURSE: DATA STRUCTURE & ALGORITHM
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
⚬ A stack is a linear data structure, collection of
items of the same type.
⚬ In a stack, insertion and deletion of elements
happen at one endpoint.
⚬ Behavior: “Last In, First Out” (LIFO) - When an
element is “pushed” onto the stack, it becomes the
first item that will be “popped” out of the stack.
⚬ In order to reach the oldest entered item, you must
pop out all the previous items.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Structure & Operational Principles:
⚬ Top pointer: keep the track of the topmost item in the stack.
⚬ Push (add element): As elements are added to the stack, the position of top is updated.
⚬ Pop (delete element): As soon as elements are popped or deleted, the topmost element
is removed and the position of top is updated.
⚬ Implementation: Stacks can be represented using structures, pointers, arrays, or
linked lists.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Functions:
⚬ Empty: Check whether the stack is empty.
⚬ Size: Returns the size of the stack.
⚬ Top: Returns a reference to the top most element of the stack.
⚬ Push: Adds the element ‘g’ at the top of the stack.
⚬ Pop: Deletes the most recent entered element of the stack.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Implementation:
⚬ The most common way to implement a stack in In C is to use single linked list.
⚬ At each node:
The data contains the assigned value
The next points to the next item in the stack.
⚬ The head of the linked list is the topmost node in the stack.
⚬ Both the push() and pop() operations are carried out at the head of the linked list.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Implementation example:
#include <stdio.h>
// Creating a node
struct node {
int value;
struct node *next;
};
struct node *top = NULL;
struct node *temp = NULL;
int size = 0;
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->next = NULL;
top->value = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->next = top;
temp->value = data;
top = temp;
}
size++;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
int pop()
{
if (top == NULL) return -1;
else
{
struct node *top1;
top1 = top1->next;
int data = top->value;
free(top);
top = top1;
size--;
return data;
}
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Implementation: #include <stdio.h>
#include <iostream>
⚬ In C ++, to create a stack, we must include #include <stack>
the <stack> header file in our code. using namespace std;
⚬ Syntax of stack implementation in C++: int main()
{
stack <data_type> stack_name; // Creating a stack
stack<int> i_stack;
stack<float> f_stack;
return 0;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Stack functions in C++:
⚬ empty() – Returns whether the stack is empty
⚬ size() – Returns the size of the stack
⚬ top() – Returns a reference to the top most element of the stack
⚬ push(value) – Adds the element ‘value’ at the top of the stack
⚬ pop() – Deletes the most recent entered element of the stack
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
#include <stdio.h>
3.3.1 Stack in C/C++ #include <iostream>
Stack functions in C++: #include <stack>
using namespace std;
int main()
{
stack<int> stack;
[Link](1);
[Link](2);
[Link](3);
while (![Link]())
{
printf("%d --->",[Link]());
[Link]();
}
return 0;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.1 Stack in C/C++
Stack applications:
⚬ Function calls: To keep track of the return addresses of function calls.
⚬ Recursion: To store the local variables and return addresses of recursive function calls,
allowing the program to keep track of the current state of the recursion.
⚬ Expression evaluation: Evaluate expressions in postfix notation (Reverse Polish
Notation).
⚬ Syntax parsing: Stacks can be used to check the validity of syntax
⚬ Memory management: Stacks are used to allocate and manage memory in some
operating systems and programming languages.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
⚬ Queue data structure stores the data in a linear sequence.
⚬ Queue data structure follows the FIFO rule, i.e. first-in-first-out. It is similar to the
stack data structure, but it has two ends.
⚬ In a queue, insertion operations are performed from the rear (Enqueue method) and
deletion operations are performed from the front (Dequeue method).
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
Structure & Operational Principles:
⚬ Front pointer/ Rear pointer: keep the record of the first and last element in the
queue.
⚬ Enqueue (add element): increment the value of the Rear index by 1 and place the
element at the position of the Rear pointer variable.
⚬ Dequeue (delete element): remove and return the element at the position of the Front
pointer, and then increment the Front index value by 1.
⚬ Implementation: Stacks can be represented using structures, pointers, arrays, or
linked lists.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
Queue Functions in C++:
⚬ Enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
⚬ Dequeue(): Removes and returns an element that is at the front end of the queue.
⚬ Front(): Returns the element at the front end without removing it.
⚬ Rear(): Returns the element at the rear end without removing it.
⚬ Empty(): Check whether the queue is empty or not.
⚬ Size(): Returns the size of the queue i.e. the total number of elements it contains.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
Implementation:
⚬ In C, a queue can be built by using a single linked list.
⚬ The data of each node contains its value, and the next node’s pointer points to the next
item in the queue.
⚬ A queue consists of two pointers: front pointer and rear pointer that store the
address of the first element and the address of the last element of the queue.
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
Implementation:
#include <stdio.h>
// Creating a node
struct node {
int value;
struct node *next;
};
struct node *front = NULL;
struct node *rear = NULL;
struct node *temp = NULL;
int size = 0;
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
void enqueue(int data)
{
temp->value = data;
if (front == NULL)
{
front = temp; rear = temp;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = temp;
rear = temp;
rear -> next = NULL;
}
size++;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
int dequeue()
{
if (front == NULL) return -1;
else
{
int data = front->value;
temp = front;
front = front -> next;
free(temp);
size--;
return data;
}
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++ #include <stdio.h>
#include <iostream>
Implementation: #include <stack>
⚬ In C++, for creating a queue, we must include using namespace std;
the <queue> header file in our code. int main()
⚬ Syntax of stack implementation in C++: {
// Creating a queue
queue <data_type> queue_name; queue<int> i_queue;
queue<float> f_queue;
return 0;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
3.3. Stack & Queue
3.3.2 Queue in C/C++
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> queue;
[Link](1);
[Link](2);
[Link](3);
while (![Link]())
{
printf("%d --->",[Link]());
[Link]();
}
return 0;
}
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t
DATA STRUCTURE & ALGORITHMS
END OF Section 3 (Chapter 3)
M e c h a t ro n i c s – R o b o t & A I D e p a r t m e n t